More Web Proxy on the site http://driver.im/

article

Free access

Supporting valid-time indeterminacy

Editor: C. L. Liu Authors:

Curtis E. Dyreson,

Richard Thomas SnodgrassAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 23, Issue 1

Pages 1 - 57

https://doi.org/10.1145/288086.288087

Published: 01 March 1998 Publication History

Abstract

In valid-time indeterminacy it is known that an event stored in a database did in fact occur, but it is not known exactly when. In this paper we extend the SQL data model and query language to support valid-time indeterminacy. We represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. We also describe query language constructs to retrieve information in the presence of indeterminacy. These constructs enable users to specify their credibility in the underlying data and their plausibility in the relationships among that data. A denotational semantics for SQL's select statement with optional credibility and plausibility constructs is given. We show that this semantics is reliable, in that it never produces incorrect information, is maximal, in that if it were extended to be more informative, the results may not be reliable, and reduces to the previous semantics when there is no indeterminacy. Although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. A contribution of this paper is to demonstrate that our approach is useful and practical. An efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. The cost of support for indeterminacy is empirically measured, and is shown to be modest. Finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for SQL3.

References

[1]

ALLEN, J.F. 1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11 (Nov.), 832-843.

[2]

ARIAV, G. 1986. A temporally oriented data model. ACM Trans. Database Syst. 11, 4 (Dec.), 499-527.

[3]

BAIR, J., JENSEN, C. S., SNODGRASS, R. T., AND BOEHLEN, M. 1997. Notions of upward compatibility of temporal query languages. Bus. Inform. 39, 1 (Feb.), 25-34.

[4]

BARBAR, D., GARC A-MOLINA, H., AND PORTER, D. 1990. A probabilistic relational data model. In Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology (Venice, Italy, March 1990), 60-74.

[5]

BARBAR, D., GARC A-MOLINA, H., AND PORTER, D. 1992. The management of probabilistic data. IEEE Trans. Knowl. Data Eng. 4, 5 (Oct.), 487-502.

[6]

BELNAP, N. 1977. A useful four-valued logic. In Modern Uses of Many-valued Logic. G. Epstein and J. M. Dunn, Eds. D. Reidel Publishing Co., Inc., New York, NY., 8-37.

[7]

B HLEN, M. H., SNODGRASS, R. T., AND Soo, M.D. 1996. Coalescing in Temporal Databases. In Proceedings of the International Conference on Very Large Data Bases (Mumbia, India, Sept. 1996), 180-191

[8]

BRUSONI, V., CONSOLE, L., TERENZIANI, P., AND PERNICI, B. 1995. Extending temporal relational databases to deal with imprecise and qualitative temporal information. In Proceedings of the International Workshop on Recent Advances in Temporal Databases (Zurich, Switzerland, Sept. 1995), S. Clifford and A. Tuzhlin, Eds. Springer-Verlag, New York, NY, 3-22.

[9]

CAVALLO, R. AND PITTARELLI, M. 1987. The theory of probabilistic databases. In Proceedings of the International Conference on Very Large Data Bases (Brighton, England, Sept. 1987), P. Hammersley, Ed. IEEE Computer Society Press, Los Alamitos, CA, 71-81.

[10]

CLIFFORD, J., DYRESON, C. E., ISAKOWITZ, T, JENSEN, C. S., AND SNODGRASS, R.T. 1997. On the semantics of'Now' in databases. ACM Trans. Database Syst. 22, 2 (June), 215-254.

[11]

CLIFFORD, J. AND RAO, A. 1987. A simple, general structure for temporal domains. In Proceedings of the Conference on Temporal Aspects in Information Systems. Association Francaise pour la Cybernetique Economique et Technique, Montreuil, France, 23-30.

[12]

CODD, E. F. 1990. Missing Information. Addison-Wesley Publishing Co., Inc., Redwood City, CA.

[13]

DATE, C.J. 1986. Null Values in Database Management. Addison-Wesley Publishing Co., Reading, MA.

[14]

DEAN, T. AND BODDY, M. 1988. Reasoning about partially ordered events. Artif. Intell. 36, 3 (Oct.), 375-399.

[15]

DEWITT, D., NAUGHTON, J., AND SCHNEIDER, D. 1991. An evaluation of non-equijoin algorithms. In Proceedings of the International Conference on Very Large Data Bases. IEEE Computer Society Press, Los Alamitos, CA, 443-452.

[16]

DEY, D. AND SARKAR, S. 1996. A probabilistic relational model and algebra. ACM Trans. Database Syst. 21, 3 (Sept.), 339-369.

[17]

DUBOIS, D. AND PRADE, H. 1989. Processing fuzzy temporal knowledge. IEEE Trans. Syst. Man Cybern. 19, 4, 729-744.

[18]

DUBOIS, D., PRADE, H., AND TESTAMALE, C. 1988. Handling Incomplete or Uncertain Data and Vague Queries in Database Applications. Plenum Press, New York, NY.

[19]

DUTTA, S. 1989. Generalized events in temporal databases. In Proceedings of the Fifth International Conference on Data Engineering (Los Angeles, CA, Feb. 1989), 118-126.

[20]

DYRESON, C.E. 1994. Valid-time indeterminacy. PhD thesis. University of Arizona, Tucson, AZ.

[21]

DYRESON, C.E. 1997. A bibliography on uncertainty management in information systems. In Uncertainty Management in Information Systems: From Needs to Solutions, A. Motro, Ed. Kluwer Academic Publishers, Hingham, MA., 415-458.

[22]

DYRESON, C. E. AND SNODGRASS, R.T. 1993. Valid-time indeterminacy. In Proceedings of the International Conference on Data Engineering (Vienna, Austria, April 1993), 335-343.

[23]

DYRESON, C. E. AND SNODGRASS, R.T. 1995a. A timestamp representation. In The TSQL2 Temporal Query Language, R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA., 475-499.

[24]

DYRESON, C. E. AND SNODGRASS, R. 1995b. Temporal indeterminacy. In The TSQL2 Ternporal Query Language. R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA, 327-346.

[25]

DYRESON, C. E., Soo, M., AND SNODGRASS, R.T. 1995. The Data Model for Time. In The TSQL2 Temporal Query Language. R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA.

[26]

FUHR, N. 1990. A probabilistic framework for vague queries and imprecise information in databases. In Proceedings of the International Conference on Very Large Data Bases (Brisbane, Australia, August 13-16, 1990), D. McLeod, R. Sacks-Davis, and H. Schek, Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA, 696-707.

[27]

FUHR, N. AND R LLEKE, T.R. 1997. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans. Inf. Syst. 15, 1 (Jan.), 32-66.

[28]

GADIA, S. K., NAIR, S., AND POON, Y.-C. 1992. Incomplete information in relational temporal databases. In Proceedings of the International Conference on Very Large Data Bases (Vancouver, Canada, Aug. 1992). IEEE Computer Society Press, Los Alamitos, CA.

[29]

GELENBE, E. AND HEBRAIL, G. 1986. A probability model of uncertainty in data bases. In Proceedings of the International Conference on Data Engineering (Los Angeles, CA, Feb. 1986). IEEE Computer Society Press, Los Alamitos, CA, 328-333.

[30]

GOUDSMIT, S. AND CLAIRBORNE, R. 1966. Time. Times Books, New York, NY.

[31]

HERION, M. AND SUERMONDT, g. 1993. Probabilistic and Bayesian representations of uncertainty and information systems: A pragmatic introduction. In Proceedings of the Workshop on Uncertainty Management in Information Systems: From Needs to Solutions (Avalon, Santa Catalina, CA, April 1993), 71-90.

[32]

JENSEN, C. S., AND DYRESON, C. E., EDS. 1998. A consensus glossary of temporal database concepts, February 1998 version. In Temporal Databases--Research and Practice, O. Etzion, S. Jajodia, and S. Sripada, Eds. Springer-Verlag, Berlin, Germany, 367-405.

[33]

KORNATZKY, Y. AND SHIMONY, S. 1993a. A probabilistic object-oriented data model. Tech Rep. FC 93-04. Ben-Gurion University, Negev, Israel.

[34]

KORNATZKY, Y. AND SHIMONY, S. 1993b. A probabilistic spatial data model. In Proceedings of the DEXA Conference (Prague, Czech Republic, Sept. 1993).

[35]

KOUBARAKIS, M. 1993. Representation and querying in temporal databases: The power of temporal constraints. In Proceedings of the International Conference on Data Engineering (Vienna, Austria, April 1993), 327-334.

[36]

KOURAMAJIAN, V. AND ELMASRI, R. 1992. A generalized temporal model. Tech. Rep. University of Texas at Arlington, Arlington, TX.

[37]

KRAUS, S. AND SUBRAHMANIAN, V.S. 1994. Multiagent reasoning with probability, time and beliefs. Int. J. Intell. Syst. 10, 5, 459-499.

[38]

LAKSHMANAN, V. S., LEONE, N., ROSS, R., AND SUBRAHMANIAN, V.S. 1997. A flexible probabilistic database system. ACM Trans. Database Syst. 22, 3 (Sept.), 419-469.

[39]

LEE, S. K. 1992. An extended relational database model for uncertain and imprecise information. In Proceedings of the International Conference on Very Large Data Bases (Vancouver, Canada, Aug. 1992). IEEE Computer Society Press, Los Alamitos, CA.

[40]

LEUNG, T. Y. AND MUNTZ, R. 1991. Temporal query processing and optimization in multiprocessor database machines. Tech. Rep. CSD-910077. University of California at Los Angeles, Los Angeles, CA.

[41]

LIPSKI, g. 1979. On semantic issues connected with incomplete information databases. ACM Trans. Database Syst. 4, 3 (Sept.), 262-296.

[42]

LIU, K.-C. AND SUNDERRAMAN, R. 1990. Indefinite and maybe information in relational databases. ACM Trans. Database Syst. 15, 1 (Mar.), 1-39.

[43]

MELTON, J. 1996. SQL/Temporal. Tech. Rep. ISO/IEC JTC 1/SC 21/WG 3/DBL-MCI-012.

[44]

MELTON, J. AND SIMON, A.R. 1993. Understanding the New SQL: A Complete Guide. Morgan Kaufmann series in data management systems. Morgan Kaufmann Publishers Inc., San Francisco, CA.

[45]

MOTRO, A. 1990. Imprecision and incompleteness in relational databases: Survey. Inf. Softw. Technol. 32, 9 (Nov.), 579-588.

[46]

OLA, A. 1992. Relational databases with exclusive disjunctions. In Data Engineering (Tempe, AZ, Feb. 1992), 328-336.

[47]

PARSON, S. 1996. Current approaches to handling imperfect information in data and knowledge bases. IEEE Trans. Knowl. Data Eng. 8, 3, 353-372.

[48]

PELTEY, B. W. 1991. Time and frequency in fundamental metrology. Proc. IEEE 79, 9 (July), 1070-1077.

[49]

PRADE, H. 1993. Annotated bibliography on fuzzy information processing. In Readings on Fuzzy Sets in Intelligent Systems, H. Prade, D. Dubois, and R. Yager, Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA.

[50]

SCHIEL, U. 1987. Representation and retrieval of incomplete and temporal information. Tech. Rep. DSC-02/87. Universidade Federal Da Paraiba, Paraiba, Brazil.

[51]

SNODGRASS, R. T. 1982. Monitoring distributed systems: A relational approach. Ph.D. dissertation. Carnegie Mellon University, Pittsburgh, PA.

[52]

SNODGRASS, R. T., B HLEN, M. H., JENSEN, C. S., AND KLINE, N. 1996. Adding valid time to SQL/Temporal. Tech. Rep. Change Proposal ANSI X3H2-96-501r2, ISO/IEC JTC1/SC21/ WG3 DBL MAD-146r2.

[53]

SNODGRASS, R.T. 1995. The Temporal Query Language TSQL2. Kluwer Academic Publishers, Hingham, MA.

[54]

Soo, M. D., SNODGRASS, R., DYRESON, C., JENSEN, C. S., AND KLINE, N. 1992. Architectural extensions to support multiple calendars. Tech. Rep. 32. University of Arizona, Tucson, AZ.

[55]

SRIVASTAVA, A. AND EUSTACE, A. 1994. ATOM: A system for building customized program analysis tools. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Orlando, FL, June 20-24, 1994). ACM Press, New York, NY, 196-205.

[56]

TANSEL, A., CLIFFORD, J., GADIA, S., JAJODIA, S., SEGEV, A., AND SNODGRASS, R., Eds. 1993. Temporal Databases: Theory, Design, and Implementation. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA.

[57]

TSENG, F. S. C., CHEN, A. L. P., AND YANG, W.-P. 1993. Answering heterogeneous database queries with degrees of uncertainty. Distrib. Parallel Databases 1, 3 (July), 281-302.

[58]

VAN BEEK, P. 1991. Temporal query processing with indefinite information. Art. Intell. Med. 3, 6 (Dec.), 325-339.

[59]

VASANTHAKUMAR, S. R., COLLAN, J. P., AND CROFT, W.B. 1996. Integrating INQUIRY with an RDBMS to support text retrieval. IEEE Data Engineering 19, 1, 24-33.

[60]

VASSILIOU, Y. 1979. Null values in database management--a denotational semantics approach. In Proceedings of the ACM SIGMOD International Conference on the Management of Data (New York, May 1979). ACM Press, New York, NY, 162-169.

[61]

VITEK, M. 1983. Fuzzy information and fuzzy time. In Proceedings of the IFAC Symposium on Fuzzy Information, Knowledge Representation and Decision Analysis (Marseille, France, 1983), 159-162.

[62]

WONG, E. 1982. A statistical approach to incomplete information in database systerns. ACM Trans. Database Syst. 7, 3 (Sept.), 470-488.

[63]

ZANIOLO, C. 1984. Database relations with null values. J. Comput. Syst. Sci. 28, 142-166.

[64]

ZEMANKOVA, M. AND KANDEL, A. 1985. Implementing imprecision in information systems. Inf. Sci. 37, 107-141.

[65]

ZIM NYI, E. 1992. Incomplete and uncertain information in relational databases. Ph.D. dissertation. Editions de l'Universite de Bruxelles, Brussels, Belgium.

Cited By

Anselma LTerenziani P(2024)Preferences in Temporal Relational DatabasesIEEE Access10.1109/ACCESS.2024.339772412(65418-65427)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3397724
Anselma LCoviello ATerenziani P(2024)Evaluating a Temporal Relational Algebra Supporting Preferences in Temporal Relational DatabasesAdvances in Databases and Information Systems10.1007/978-3-031-70626-4_3(32-44)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-70626-4_3
Chehibi MFerchichi AFarah IHadjali A(2022)Managing Temporal Uncertainty-A short review2022 2nd International Conference of Smart Systems and Emerging Technologies (SMARTTECH)10.1109/SMARTTECH54121.2022.00023(1-6)Online publication date: May-2022
https://doi.org/10.1109/SMARTTECH54121.2022.00023
Show More Cited By

Index Terms

Supporting valid-time indeterminacy
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Valid-time indeterminacy
On the semantics of “now” in databases

Although “now” is expressed in SQL and CURRENT_TIMESTAMP within queries, this value cannot be stored in the database. How ever, this notion of an ever-increasing current-time value has been reflected in some temporal data models by inclusion of database-...
Efficient Processing of Nested Fuzzy SQL Queries
ICDE '95: Proceedings of the Eleventh International Conference on Data Engineering

Fuzzy databases have been introduced to deal with uncertain or incomplete information in many applications. The efficiency of processing fuzzy queries in fuzzy databases is a major concern. We provide techniques to unnest nested fuzzy queries of two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 23, Issue 1

March 1998

109 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/288086

Editor:
C. L. Liu
Univ. of Illinois, Urbana-Champagn, IL

Issue’s Table of Contents

Copyright © 1998 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1998

Published in TODS Volume 23, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

122
Total Citations
View Citations
849
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)18

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anselma LTerenziani P(2024)Preferences in Temporal Relational DatabasesIEEE Access10.1109/ACCESS.2024.339772412(65418-65427)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3397724
Anselma LCoviello ATerenziani P(2024)Evaluating a Temporal Relational Algebra Supporting Preferences in Temporal Relational DatabasesAdvances in Databases and Information Systems10.1007/978-3-031-70626-4_3(32-44)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-70626-4_3
Chehibi MFerchichi AFarah IHadjali A(2022)Managing Temporal Uncertainty-A short review2022 2nd International Conference of Smart Systems and Emerging Technologies (SMARTTECH)10.1109/SMARTTECH54121.2022.00023(1-6)Online publication date: May-2022
https://doi.org/10.1109/SMARTTECH54121.2022.00023
Chehibi MFerchichi AFarah I(2022)An Intelligent System for Managing Uncertain Temporal Flood EventsBelief Functions: Theory and Applications10.1007/978-3-031-17801-6_18(184-193)Online publication date: 26-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-17801-6_18
Song SHuang RCao YWang J(2021)Cleaning timestamps with temporal constraintsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-020-00641-630:3(425-446)Online publication date: 23-Feb-2021
https://dl.acm.org/doi/10.1007/s00778-020-00641-6
Anselma LPiovesan LTerenziani P(2019)Dealing with temporal indeterminacy in relational databasesAI Communications10.3233/AIC-19061932:3(207-221)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.3233/AIC-190619
Chountas PKodogiannis VPetrounias IKolev BAtanassov K(2019)On Probability, Null Values, Intuitionistic Fuzzy, & Value ImperfectionInternational Conference of Computational Methods in Sciences and Engineering 2004 (ICCMSE 2004)10.1201/9780429081385-290(1139-1143)Online publication date: 29-Apr-2019
https://doi.org/10.1201/9780429081385-290
Bavishi RLemieux CFox RSen KStoica I(2019)AutoPandas: neural-backed generators for program synthesisProceedings of the ACM on Programming Languages10.1145/33605943:OOPSLA(1-27)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360594
Salvaneschi GKöhler MSokolowski DHaller PErdweg SMezini M(2019)Language-integrated privacy-aware distributed queriesProceedings of the ACM on Programming Languages10.1145/33605933:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360593
Chatterjee KPavlogiannis AToman V(2019)Value-centric dynamic partial order reductionProceedings of the ACM on Programming Languages10.1145/33605503:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360550
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents