ACM SIGMOD Anthology TODS dblp.uni-trier.de

On Semantic Issues Connected with Incomplete Information Databases.

Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979)
@article{DBLP:journals/tods/Lipski79,
  author    = {Witold Lipski Jr.},
  title     = {On Semantic Issues Connected with Incomplete Information Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {3},
  year      = {1979},
  pages     = {262-296},
  ee        = {http://doi.acm.org/10.1145/320083.320088, db/journals/tods/Lipski79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Various approaches to interpreting queries in a database with incomplete information are discussed. A simple model of a database is described, based on attributes which can take values in specified attribute domains. Information incompleteness means that instead of having a single value of an attribute, we have a subset of the attribute domain, which represents our knowledge that the actual value, though unknown, is one of the values in this subset. This extends the idea of Codd's null value, corresponding to the case when this subset is the whole attribute domain. A simple query language to communicate with such a system is described and its various semantics are precisely defined. We emphasize the distinction between two different interpretations of the query language - the external one, which refers the queries directly to the real world modeled in an incomplete way by the system, and the internal one, under which the queries refer to the system's information about this world, rather than to the world itself. Both external and internal interpretations are provided with the corresponding sets of axioms which serve as a basis for equivalent transformations of queries. The technique of equivalent transformations of queries is then extensively exploited for evaluating the interpretation of (i.e. the response to) a query.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
...
[2]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[3]
...
[4]
John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) BibTeX
[5]
...
[6]
...
[7]
...
[8]
...
[9]
...
[10]
...
[11]
Witold Lipski Jr.: On Databases with Incomplete Information. J. ACM 28(1): 41-70(1981) BibTeX
[12]
Witold Lipski Jr.: Informational Systems with Incomplete Information. ICALP 1976: 120-130 BibTeX
[13]
Witold Lipski Jr.: On the Logic of Incomplete Transformation. MFCS 1977: 374-381 BibTeX
[14]
...
[15]
...
[16]
...
[17]
Witold Lipski Jr., V. Wiktor Marek: Information systems: on queries involving cardinalities. Inf. Syst. 4(1): 241-246(1979) BibTeX
[18]
...
[19]
V. Wiktor Marek, Zdzislaw Pawlak: Information Storage and Retrieval Systems: Mathematical Foundations. Theor. Comput. Sci. 1(4): 331-354(1976) BibTeX
[20]
...
[21]
...

Referenced by

  1. Curtis E. Dyreson, Richard T. Snodgrass: Supporting Valid-Time Indeterminacy. ACM Trans. Database Syst. 23(1): 1-57(1998)
  2. James Clifford, Curtis E. Dyreson, Tomás Isakowitz, Christian S. Jensen, Richard T. Snodgrass: On the Semantics of ``Now'' in Databases. ACM Trans. Database Syst. 22(2): 171-214(1997)
  3. Debabrata Dey, Sumit Sarkar: A Probabilistic Relational Model and Algebra. ACM Trans. Database Syst. 21(3): 339-369(1996)
  4. Peter Buneman, Atsushi Ohori: Polymorphism and Type Inference in Database Programming. ACM Trans. Database Syst. 21(1): 30-76(1996)
  5. Simon Parsons: Current Approaches to Handling Imperfect Information in Data and Knowledge Bases. IEEE Trans. Knowl. Data Eng. 8(3): 353-372(1996)
  6. Arbee L. P. Chen, Jui-Shang Chiu, Frank Shou-Cheng Tseng: Evaluating Aggregate Operations Over Imprecise Data. IEEE Trans. Knowl. Data Eng. 8(2): 273-284(1996)
  7. I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995)
  8. Kumar V. Vadaparty, Shamim A. Naqvi: Using Constraints for Efficient Query Processing in Nondeterministic Databases. IEEE Trans. Knowl. Data Eng. 7(6): 850-864(1995)
  9. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
  10. Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424
  11. Janusz R. Getta, Leszek A. Maciaszek: Management of Inconsistent Information in Federated Systems. OOER 1995: 412-423
  12. Oliver Haase, Andreas Henrich: Error Propagation in Distributed Databases. CIKM 1995: 387-394
  13. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  14. Frank Shou-Cheng Tseng, Arbee L. P. Chen, Wei-Pang Yang: Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values. VLDB J. 2(4): 489-512(1993)
  15. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  16. Adegbeniga Ola, Gultekin Özsoyoglu: Incomplete Relational Database Models Based on Intervals. IEEE Trans. Knowl. Data Eng. 5(2): 293-308(1993)
  17. Roger S. Barga, Calton Pu: Accessing Imprecise Data: An Approach Based on Intervals. IEEE Data Eng. Bull. 16(2): 12-15(1993)
  18. Curtis E. Dyreson, Richard T. Snodgrass: Valid-time Indeterminancy. ICDE 1993: 335-343
  19. Daniel Barbará, Hector Garcia-Molina, Daryl Porter: The Management of Probabilistic Data. IEEE Trans. Knowl. Data Eng. 4(5): 487-502(1992)
  20. Suk Kyoon Lee: An Extended Relational Database Model for Uncertain and Imprecise Information. VLDB 1992: 211-220
  21. Suk Kyoon Lee: Imprecise and Uncertain Information in Databases: An Evidential Approach. ICDE 1992: 614-621
  22. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
  23. Fereidoon Sadri: Reliability of Answers to Queries in Relational Databases. IEEE Trans. Knowl. Data Eng. 3(2): 245-251(1991)
  24. Ken-Chih Liu, Rajshekhar Sunderraman: A Generalized Relational Model for Indefinite and Maybe Information. IEEE Trans. Knowl. Data Eng. 3(1): 65-77(1991)
  25. Wladyslaw Homenda: Databases with Alternative Information. IEEE Trans. Knowl. Data Eng. 3(3): 384-386(1991)
  26. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
  27. Nong Zhou: Representation and Processing of Uncertain Information in Relational Databases. ER 1991: 371-388
  28. Ken-Chih Liu, Rajshekhar Sunderraman: Indefinite and Maybe Information in Relational Databases. ACM Trans. Database Syst. 15(1): 1-39(1990)
  29. Norbert Fuhr: A Probabilistic Framework for Vague Queries and Imprecise Information in Databases. VLDB 1990: 696-707
  30. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases: A Generalization. ICDE 1990: 495-502
  31. Daniel Barbará, Hector Garcia-Molina, Daryl Porter: A Probalilistic Relational Data Model. EDBT 1990: 60-74
  32. Howard M. Dreizen, Shi-Kuo Chang: Imprecise Schema: A Rationale for Relations with Embedded Subrelations. ACM Trans. Database Syst. 14(4): 447-479(1989)
  33. Linda G. DeMichiel: Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains. IEEE Trans. Knowl. Data Eng. 1(4): 485-493(1989)
  34. Adegbemiga Ola, Gultekin Özsoyoglu: A Family of Incomplete Relational Database Models. VLDB 1989: 23-31
  35. Linda G. DeMichiel: Performing Operations over Mismatched Domains. ICDE 1989: 36-45
  36. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988)
  37. Georg Gottlob, Roberto Zicari: Closed World Databases Opened Through Null Values. VLDB 1988: 50-61
  38. Dominique Laurent, Nicolas Spyratos: Partition Semantics for Incomplete Information in Relational Databases. SIGMOD Conference 1988: 66-73
  39. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases. ICDE 1988: 250-257
  40. Tomasz Imielinski: Relative Knowledge in a Distributed Database. PODS 1987: 197-209
  41. Haim Mendelson, Aditya N. Saharia: Incomplete Information Costs and Database Design. ACM Trans. Database Syst. 11(2): 159-185(1986)
  42. Peter Buneman, Atsushi Ohori: A Domain Theoretic Approach to Higher-Order Relations. ICDT 1986: 91-104
  43. Arie Zvieli, Peter P. Chen: Entity-Relationship Modeling and Fuzzy Databases. ICDE 1986: 320-327
  44. Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984)
  45. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  46. Arthur M. Keller, Marianne Winslett: Approaches for Updating Databases With Incomplete Information and Nulls. ICDE 1984: 332-340
  47. Joachim Biskup: A Foundation of Codd's Relational Maybe-Operations. ACM Trans. Database Syst. 8(4): 608-636(1983)
  48. Manfred R. Klopprogge, Peter C. Lockemann: Modelling Information Preserving Databases: Consequences of the Concept of Time. VLDB 1983: 399-416
  49. Zbigniew Michalewicz: Statistical Databases: Their Model, Query Language and Security. SSDBM 1983: 391-402
  50. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  51. Eugene Wong: A Statistical Approach to Incomplete Information in Database Systems. ACM Trans. Database Syst. 7(3): 470-488(1982)
  52. Tomasz Imielinski, Witold Lipski Jr.: A Systematic Approach to Relational Database Theory. SIGMOD Conference 1982: 8-14
  53. Carlo Zaniolo: Database Relations with Null Values. PODS 1982: 27-33
  54. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9
  55. Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397
  56. Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
  57. Adrian Walker: On Retrieval from a Small Version of a Large Data Base. VLDB 1980: 47-54
  58. Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269
  59. E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:40 2008