Skip to main content
SpringerLink
Log in

Logical Approaches to Incomplete Information: A Survey

  • Chapter
Logics for Databases and Information Systems

Part of the book series: The Springer International Series in Engineering and Computer Science ((SECS,volume 436))

Abstract

The observation that it is frequently impossible to obtain complete information in the context of database applications has motivated a substantial literature seeking to extend the relational model. The paper surveys the literature on the modelling and processing of incomplete information (also known as indefinite information) using tools derived from classical logic and modal logic. The focus of the paper is on models in which query processing is decidable. Theories dealing with the quantification of indefiniteness, such as probabilistic or fuzzy models of uncertainty, are not discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. K.R. Apt and R.N. Bol. Logic Programming and Negation: A Survey. Journal of Logic Programming, 19/20:9–71, 1994.

    Article  MathSciNet  Google Scholar 

  2. K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufman, 1989.

    Google Scholar 

  3. P. Atzeni and V. de Antonellis. Relational Database Theory. Benjamin/Cummings, Redwood City, CA, 1993.

    MATH  Google Scholar 

  4. S. Abiteboul and G. Grahne. Update semantics for incomplete databases. In Proc. Int. Conf. on Very Large Data Bases,, pp. 1–12, Stockholm, Sweden, August 1985.

    Google Scholar 

  5. D. Alchouron, P. Gardenfors, and D. Makinson. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, 50:510–530, 1985.

    Article  MathSciNet  Google Scholar 

  6. S. Abiteboul, P. Kanellakis, and G. Grahne. On the Representation and Querying of Sets of Possible Worlds. Theoretical Computer Science, 78:159–187, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  7. P. Atzeni and N.M. Morfuni. Functional dependencies in relations with null values. Information Processing Letters, 18(4):233–238, 14 May 1984.

    Article  MathSciNet  MATH  Google Scholar 

  8. P. Atzeni and N.M. Morfuni. Functional Dependencies and Constraints on Null Values in Database Relations. Information and Control, 70(1):1–31, July 1986.

    Article  MathSciNet  MATH  Google Scholar 

  9. ANSI/X3/SPARC. Study Group on Database Management Systems. SIGMOD FDT Bulletin, 7(2), 1975.

    Google Scholar 

  10. P. Atzeni and R. Torlone. Approaches to Updates over Weak Instances. In Proc. First Symposium on Mathematical Fundamentals of Database Systems, pp. 12–23, Visegrad, Hungary, June 1989.

    Google Scholar 

  11. N. Bidoit. Negation in rule-based database languages: a survey. Theoretical Computer Science, 78(1):3–83, 21 January 1991.

    Article  MathSciNet  MATH  Google Scholar 

  12. J. Biskup. A Formal Approach to Null Values in Database Relations. In H. Gallaire, J. Minker, and J. Nicolas, editors, Advances in Data Base Theory, volume 1, pp. 299–341. Plenum Press, New York, 1981.

    Chapter  Google Scholar 

  13. J. Biskup. A Foundation Of Codd’s Relational Maybe-Operations. ACM Transactions on Database Systems, 8(4):608–636, December 1983.

    Article  MathSciNet  MATH  Google Scholar 

  14. J. Biskup. Extending the relational algebra for relations with maybe tuples and existential and universal null values. Fundamenta Informaticœ, VII(1):129–150, 1984.

    MathSciNet  Google Scholar 

  15. P. Buneman, A. Jung, and A. Ohori. Using powerdomains to generalize relational databases. Theoretical Computer Science, 91(1):23–55, 9 December 1991.

    Article  MathSciNet  MATH  Google Scholar 

  16. A.J. Bonner and M. Kifer. An Overview of Transaction Logic. Theoretical Computer Science, 133(2):205–265, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  17. A. Bonner and M. Kifer. Logic Programming for Database Transactions. In Chomicki and Saake [CS98], chapter 5, pp. 117–166.

    Google Scholar 

  18. A. Borgida. Description Logics in Data Management. IEEE Transactions on Knowledge and Data Management, 7(5):671–668, 1995.

    Article  Google Scholar 

  19. C.L. Chang. DEDUCE: A Deductive query language for Relational Data Bases. In C.H. Chen, editor, Pattern Recognition and Artificial Intelligence, pp. 108–134. Academic Press, New York, 1976.

    Google Scholar 

  20. E. Chan. A Possible World Semantics for Disjunctive Databases. IEEE Transactions on Data and Knowledge Engineering, 5(2):282–292, 1993.

    Article  Google Scholar 

  21. B. Chellas. Modal Logic. Cambridge University Press, 1980.

    Google Scholar 

  22. K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 293–322. Plenum Press, 1978.

    Google Scholar 

  23. A. Chandra and P. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases. In Proceedings of the ACM Symposium on the Theory of Computing, pp. 77–90. Association for Computing Machinery, 1976.

    Google Scholar 

  24. E.F. Codd. A relational model for large shared data banks. Communications of the ACM, 13(6):377–387, 1970.

    Article  MATH  Google Scholar 

  25. E.F. Codd. Relational completeness of data base sublanguages. In R. Rustin, editor, Data Base Systems, pp. 33–64. Prentice-Hall, Englewood Cliffs, New Jersey, 1972.

    Google Scholar 

  26. E.F. Codd. Extending the Database Relational Model to Capture More Meaning. ACM Transactions on Database Systems, 4(4):397–434, December 1979.

    Article  Google Scholar 

  27. J. Chomicki and G. Saake, editors. Logics for Databases and Information Systems. Kluwer Academic Publishers, Boston, 1998.

    MATH  Google Scholar 

  28. C.J. Date. Relational Database: Selected Writings, chapter 15: Null Values in Database Management, pp. 313–334. Addison-Wesley, Reading, MA, 1986.

    Google Scholar 

  29. C.J. Date. A guide to INGRES: a user’s guide to the INGRES product. Addison-Wesley, Reading, Mass, 1987.

    Google Scholar 

  30. C.J. Date. Relational Database Writings 1985 — 1989, chapter 13: EXISTS is Not ‘Exists’! (some logical flaws in SQL), pp. 339–356. Addison-Wesley, Reading, MA, 1989.

    Google Scholar 

  31. C.J. Date and H. Darwen. A Guide to The SQL Standard, 3rd ed. Addison-Wesley, Reading, MA, 1993.

    Google Scholar 

  32. F. Dong and L.V.S. Lakshmanan. Intuitionistic Interpretation of Deductive Databases with Incomplete Information. Theoretical Computer Science, 133(2):267–306, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  33. C.E. Dyreson and R.T. Snodgrass. Valid-Time Indeterminacy. In Proceedings of the International Conference on Data Engineering, pp. 335–343, Vienna, Austria, April 1993.

    Google Scholar 

  34. F. Dignum and R.P. van de Riet. Addition and removal of information for a knowledge base with incomplete information. Data & Knowledge Engineering, 8:293–307, 1992.

    Article  MATH  Google Scholar 

  35. T. Eiter and G. Gottlob. On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artificial Intelligence, 57(2-3):227–270, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  36. T. Eiter and G. Gottlob. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence, 15:289–323, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  37. T. Eiter and G. Gottlob. The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions. Journal of Computer and System Sciences, 53(3):497–512, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  38. T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Transactions on Database Systems, 22(3):364–418, 1997.

    Article  Google Scholar 

  39. C. Esculier. Non-Monotonic Knowledge Evolution in VLKDBs. In Proc. of the 16th Int. Conf. on Very Large Databases, Brisbane, Australia, 1990.

    Google Scholar 

  40. A. Furtado and M. Casanova. Updating relational views. In W. Kim, D. Reiner, and D. Batory, editors, Query Processing in Database Systems. Springer-Verlag, 1985.

    Google Scholar 

  41. R. Fagin, G. Kuper, J.D. Ullman, and M.Y. Vardi. Updating Logical Databases. In Advances in Computing Research, volume 3, pp. 1–18, 1986.

    Google Scholar 

  42. J. Fernandez and J. Minker. Bottom-up Evaluation of Hierarchical Disjunctive Deductive Databases. In K. Furukawa, editor, Logic Programming: Proceedings of the Eighth International Conference, pp. 660–675. The MIT Press, 1991.

    Google Scholar 

  43. R. Fagin, J.D. Ullman, and M.Y. Vardi. On the Semantics of Updates in Databases. In Proc. ACM Symp. on Principles of Database Systems, pp. 352–365, 1983.

    Google Scholar 

  44. D.M. Gabbay, editor. Handbook of Logic in Artificial Intelligence and Logic Programming, volume III: Nonmonotonic Reasoning and Uncertain Reasoning. Oxford University Press, Oxford, 1994.

    Google Scholar 

  45. J. Gallier. Logic for Computer Science: Foundations for Automatic Theorem Proving, chapter 9: SLD-Resolution and Logic Programming. Computer Science Series. Harper and Row, New York, 1986.

    Google Scholar 

  46. M. Gelfond. Logic Programming and Reasoning with Incomplete Information. Annals of Mathematics and Artificial Intelligence, 12:89–116, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  47. G.H. Gessert. Four Value Logic for Relational Database Systems. SIGMOD Record, 19(1):29–35, 1990.

    Article  Google Scholar 

  48. G.H. Gessert. Handling Missing Data by Using Stored Truth Values. SIGMOD Record, 20(3):30–42, September 1991.

    Article  Google Scholar 

  49. P. Godfrey, J. Grant, J. Gryz, and J. Minker. Integrity Constraints: Semantics and Applications. In Chomicki and Saake [CS98], chapter 9, pp. 265–306.

    Google Scholar 

  50. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

    MATH  Google Scholar 

  51. M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In R. Kowalski and K. Bowen, editors, Logic Programming: Proc. Fifth International Conference and Symposium, pp. 1070–1080. The MIT Press, 1988.

    Google Scholar 

  52. M. Gelfond and V. Lifschitz. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365–385, 1991.

    Article  Google Scholar 

  53. H. Gallaire and J. Minker. Logic and Data Bases. Plenum Press, New York, 1978.

    Book  MATH  Google Scholar 

  54. J. Grant and J. Minker. Answering queries in indefinite databases and the null value problem. In P. Kanellakis, editor, Advances in Computing Research, volume 3, pp. 247–267. JAI Press, London, 1986.

    Google Scholar 

  55. G. Grahne and A.O. Mendelzon. Updates and subjunctive queries. Information and Computation, 116:241–252, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  56. G. Grahne, A.O. Mendelzon, and P.Z. Revesz. Knowledgebase transformations. Journal of Computer and System Sciences, 54:98–112, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  57. S.K. Gadia, S.S. Nair, and Y.-C. Poon. Incomplete Information in Relational Temporal Databases. In Proc. Conf. on Very Large Databases, Vancouver, Canada, August 1992.

    Google Scholar 

  58. B. Goldstein. Constraints on Null Values in Relational Databases. In Proc. of the Int. Conf. on Very Large Databases, pp. 101–110, Cannes, France, September 1981.

    Google Scholar 

  59. P. Gardenfors and H. Rott. Belief Revision. In D. Gabbay, C.J. Hogger, and J.A. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume IV: Epistemic and Temporal Reasoning, pp. 35–132. Oxford University Press, 1995.

    Google Scholar 

  60. J. Grant. Null Values in a Relational Data Base. Information Processing Letters, 6(5):156–157, October 1977.

    Article  MathSciNet  MATH  Google Scholar 

  61. G. Grahne. The Problem of Incomplete Information in Relational Databases. Springer LNCS No. 554, 1991.

    Google Scholar 

  62. C. Green. Theorem-proving by Resolution as a Basis for Question Answering Systems. In B. Meltzer and D. Michie, editors, Machine Intelligence 4, pp. 183–205. American Elsevier Publishing Co., 1969.

    Google Scholar 

  63. A.V. Gelder, K.A. Ross, and J.S. Schlipf. The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620–650, 1991.

    MATH  Google Scholar 

  64. G. Gottlob and R. Zicari. Closed World Databases Opened Through Null Values. In Proc. Int. Conf. on Very Large Databases, pp. 50–61, Los Angeles, CA, 1988.

    Google Scholar 

  65. S. Hegner. Specification and implementation of programs for updating incomplete information databases. In Proc. ACM Symp. on Principles of Database Systems, San Diego, CA, March 1987.

    Google Scholar 

  66. T. Imielinski and W. Lipski, Jr. Incomplete Information and Dependencies in Relational Databases. In ACM SIGMOD International Conference on Management of Data, pp. 178–184, 1983.

    Google Scholar 

  67. T. Imielinski and W. Lipski, Jr. Incomplete Information in Relational Databases. Journal of the ACM, 31(4):761–791, 1984.

    Article  MathSciNet  MATH  Google Scholar 

  68. T. Imielinski and W. Lipski, Jr. Epilogue to ‘Incomplete Information in a Relational Database’. In M.L. Brodie and J. Mylopoulos, editors, Readings in Artificial Intelligence and Databases. Springer-Verlag, Berlin, 1989.

    Google Scholar 

  69. T. Imielinski. Incomplete Information in Logical Databases. IEEE Database Engineering Bulletin — Special Issue on Imprecision in Databases, 12(2):29–40, June 1989.

    Google Scholar 

  70. T. Imielinski. Abstraction in Query Processing. Journal of the ACM, 38(1):534–558, 1991.

    MATH  Google Scholar 

  71. T. Imielinski. Incomplete Deductive Databases. Annals of Mathematics and Artificial Intelligence, 3(2-4):259–293, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  72. T. Imielinski, R. Meyden, and K. Vadaparty. Complexity Tailored Design: A New Design Methodology for Databases with Incomplete Information. Journal of Computer and System Sciences, 51(3):405–432, Dec 1995.

    Article  MathSciNet  Google Scholar 

  73. T. Imielinski, S. Naqvi, and K. Vadaparty. Incomplete Objects—A Data Model for Design and Planning Applications. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 288–297, Denver, CO, May 1991.

    Google Scholar 

  74. T. Imielinski, S. Naqvi, and K. Vadaparty. Querying Design and Planning Databases. In Proc. Int. Conf. on Deductive and Object-Oriented Databases, Munich, Germany, December 1991.

    Google Scholar 

  75. Y. Jia, Z. Feng, and M. Miller. A Multivalued Approach to Handle Nulls in RDB. In Future Database ′92, Proceedings of the Second Far-East Workshop on Future Database Systems, pp. 71–76, Kyoto, Japan, April 1992.

    Google Scholar 

  76. J. Jaffar and J.-L. Lassez. Constraint Logic Programming. In Proc. ACM Symp. Principles of Programming Languages, pp. 111–119, 1987.

    Google Scholar 

  77. A. Jung, L. Libkin, and H. Puhlmann. Decomposition of Domains. In S. Brookes, M. Main, A. Melton, and M. Mislove, editors, Proc. of Mathematical Foundations of Programming Semantics. 7th Int. Conf, Pittsburgh, PA, USA, March 25-28, 1991: Proceedings, volume 598 of LNCS, pp. 235–258, Berlin, Germany, March 1992. Springer.

    Google Scholar 

  78. A. Jung and H. Puhlmann. Types, Logic, and Semantics for Nested Databases. In M. Main and S. Brookes, editors, 11th Conf. on Mathematical Foundations of Programming Semantics, volume 1 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers B.V., 1995.

    Google Scholar 

  79. P.C. Kanellakis. Elements of Relational Database Theory. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, pp. 1071–1156. MIT Press, Cambridge, Mass., 1990.

    Google Scholar 

  80. A.M. Keller. Set-theoretic Problems of Null Completion in Relational Databases. Information Processing Letters, 22(5):261–265, April 1986.

    Article  MathSciNet  MATH  Google Scholar 

  81. P.C. Kanellakis, G.M. Kuper, and P.Z. Revesz. Constraint Query Languages. Journal of Computer and System Sciences, 51(1):26–52, 1995.

    Article  MathSciNet  Google Scholar 

  82. H. Katsuno and A. Mendelzon. On the difference between updating a knowledge base and revising it. In P. Gardenfors, editor, Belief Revision, pp. 183–203. Cambridge University Press, Cambridge, 1992.

    Chapter  Google Scholar 

  83. M. Koubarakis. Database Models for Infinite and Indefinite Temporal Information. Information Systems, 19(2):141–173, 1994.

    Article  Google Scholar 

  84. M. Koubarakis. Foundations of Indefinite Constraint Databases. In A. Borning, editor, Proc. of the 2nd Int. Workshop on the Principles and Practice of Constraint Programming, Springer LNCS No. 874, pp. 266–280, 1994.

    Google Scholar 

  85. M. Koubarakis. The Complexity of Query Evaluation in Indefinite Temporal Constraint Databases. Theoretical Computer Science, 171(1-2):25–60, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  86. R.A. Kowalski. Predicate Logic as a Programming Language. In Proceedings IFIP Congress, pp. 569–574, Amsterdam, 1974. North Holland Publishing Co.

    Google Scholar 

  87. R.A. Kowalski. Logic for Data Description. In H.G.J. Minker, editor, Logic and Data Bases, pp. 77–103. Plenum Press, New York, 1978.

    Chapter  Google Scholar 

  88. A.M. Keller and M.W. Wilkins. Approaches for Updating Databases With Incomplete Information and Nulls. In Proc. of the Int. Conf. on Data Engineering, pp. 332–340, Los Angeles, CA, April 1984. IEEE Computer Society, IEEE Computer Society Press.

    Google Scholar 

  89. A.M. Keller and M.W. Wilkins. On the Use of an Extended Relational Model to Handle Changing Incomplete Information. IEEE Transactions on Software Engineering, 11(7):620–633, July 1985.

    Article  Google Scholar 

  90. K. Kwast. The Incomplete Database. In Proc. Int. Joint Conf. on Artificial Intelligence, pp. 897–902, 1991.

    Google Scholar 

  91. N. Lerat. Query Processing in Incomplete Logical Databases. In G. Ausiello and P. Atzeni, editors, Proc. of the Int. Conf. on Database Theory, pp. 260–277, Rome, Italy, September 1986. Springer-Verlag.

    Google Scholar 

  92. H.J. Levesque. The Logic of Incomplete Databases. In M. Brodie, J. Mylopoulos and J.W. Schmidt, editors, On Conceptual Modeling: Perspectives from Artificial Intelligence Databases and Programming Languages, pp. 165–186. Springer-Verlag, Berlin and New York, 1984.

    Google Scholar 

  93. M. Levene. The Nested Universal Relation Database Model. Springer LNCS No. 595, 1992.

    Google Scholar 

  94. A.Y. Levy. Obtaining Complete Answers from Incomplete Databases. In Proc. of the 22nd Int. Conf. on Very Large Databases, pp. 402–412, 1996.

    Google Scholar 

  95. L. Libkin and E. Gunter. OR-SML: A functional database programming language with support for disjunctive information. In D. Karagiannis, editor, Proc. 5th Int. Conf. on Database and Expert Systems Applications (DEXA), volume 856, pp. 641–650, Athens, Greece, September 1994. Springer-Verlag, Lecture Notes in Computer Science.

    Google Scholar 

  96. L. Libkin. A relational algebra for complex objects based on partial information. In B. Thalheim, editor, Proc. of the Symp. on Math. Fundamentals of Database Systems (MFDBS), volume 495, pp. 136–147, Rostock, Germany, May 1991. Springer-Verlag, Lecture Notes in Computer Science.

    Google Scholar 

  97. L. Libkin. Aspects of partial information in databases. PhD thesis, Computer and Information Science, University of Pennsylvania, 1994.

    Google Scholar 

  98. L. Libkin. Normalizing Incomplete Databases. In Proc. ACM Symp. on Principles of Database Systems, pp. 219–230, 1995.

    Google Scholar 

  99. W. Lipski, Jr. On Semantic Issues Connected with Incomplete Information Databases. ACM Transactions on Database Systems, 4(3):262–296, September 1979.

    Article  Google Scholar 

  100. W. Lipski, Jr. On Databases with Incomplete Information. Journal of the ACM, 28(1):41–70, 1981.

    Article  MathSciNet  MATH  Google Scholar 

  101. W. Lipski, Jr. On Relational Algebra with Marked Nulls. In Proc. ACM Symp. on Principles of Database Systems, pp. 201–203, Waterloo, Ontario, Canada, April 1984.

    Google Scholar 

  102. N. Lerat and W. Lipski, Jr. Nonapplicable Nulls. Theoretical Computer Science, 46:67–82, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  103. M. Levene and G. Loizou. The nested relation type model: An application of domain theory to databases. The Computer Journal, 33:19–30, 1990.

    Article  MathSciNet  Google Scholar 

  104. M. Levene and G. Loizou. Correction to Null Values in Nested Relational Databases by M.A. Roth, H.F. Korth, and A. Silberschatz. Acta Informatica, 28:603–605, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  105. J. Lloyd. Foundations of Logic Programming. Springer-Verlag, Berlin, second edition, 1987.

    Book  MATH  Google Scholar 

  106. J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, Cambridge, MA, 1992.

    Google Scholar 

  107. J.W. Lloyd and R. Topor. A Basis for Deductive Database Systems. Journal of Logic Programming, 2:93–109, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  108. L. Libkin and L. Wong. Semantic Representations and Query Languages for Or-Sets. Journal of Computer and System Sciences, 52(1):125–142, February 1996.

    Article  MathSciNet  MATH  Google Scholar 

  109. D. Maier. Discarding the Universal Instance Assumption: Preliminary Results. In XP1 Workshop on Relational Database Theory. SUNY at Stony Brook, NY, June-July 1980.

    Google Scholar 

  110. D. Maier. The Theory of Relational Databases, chapter 12: Null Values, Partial Information, and Database Semantics. Computer Science Press, Rockville, MD, 1983.

    Google Scholar 

  111. E. Mendelson. Introduction to Mathematical Logic. D. van Nostrand Co., New York, 1964.

    Google Scholar 

  112. R. Meyden. Recursively Indefinite Databases. Theoretical Computer Science, 116:151–194, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  113. R. Meyden. The Complexity of Querying Indefinite Data about Linearly Ordered Domains. Journal of Computer and System Sciences, 54(1):113–135, Feb 1997.

    Article  MathSciNet  MATH  Google Scholar 

  114. J. Minker. On Indefinite Databases and the Closed World Assumption. In 6th Conference on Automated Deduction, pp. 292–308. Springer LNCS No. 138, 1982.

    Google Scholar 

  115. R. Moore. Semantical Considerations on nonmonotonic logic. Artificial Intelligence, 25:75–91, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  116. A. Motro. Integrity = Validity + Completeness. ACM Transactions on Database Systems, 14(4):480–502, December 1989.

    Article  Google Scholar 

  117. J. Minker and D. Perlis. Applications of Protected Circumscription. In Proc. of the 7th Conference on Automated Deduction, pp. 414–425. Springer, 1984.

    Google Scholar 

  118. J. Minker and D. Perlis. Computing Protected Circumscription. Journal of Logic Programming, 2(4):235–249, December 1985.

    Article  MathSciNet  MATH  Google Scholar 

  119. A. Motro and P. Smets, editors. Uncertainty Management in Information Systems. Kluwer Academic Publishers, Boston, 1996.

    MATH  Google Scholar 

  120. V.W. Marek and M. Truszczynski. Autoepistemic Logic. Journal of the ACM, 38(3):588–619, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  121. L.T. McCarty and R. van der Meyden. Reasoning about Indefinite Actions. In Proc. 3rd Int. Conf. on Principles of Knowledge Representation and Reasoning, pp. 59–70. Morgan Kaufmann, 1992.

    Google Scholar 

  122. J.M. Nicholas and H. Gallaire. Data base: theory vs. interpretation. In H. Gallaire and J. Minker, editors, Logic and Databases, pp. 33–54. Plenum Press, New York, 1978.

    Google Scholar 

  123. A. Ohori. Orderings and Types in Databases. In F. Bancilhon and P. Buneman, editors, Advances in Database Programming Languages, pp. 97–116. ACM Press, 1990.

    Google Scholar 

  124. A. Ohori. Semantics of Types for Database Objects. Theoretical Computer Science, 76(1):53–91, 31 October 1990.

    Article  MathSciNet  MATH  Google Scholar 

  125. S. Osborn. Insertions in a Multi-relation Database with Nulls. In Proc. of C0MPSAC81: IEEE Computer Society’s Fifth Int. Computer Software and applications Conference, pp. 75–80, Chicago, IL, November 1981.

    Google Scholar 

  126. P. Ostermann. Modal Logic and Incomplete Information. In Proc. First Symposium on Mathematical Fundamentals of Database Systems, pp. 181–196, Dresden, GDR, January 1987.

    Google Scholar 

  127. C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

    Google Scholar 

  128. T. Przymusinski and H. Przymusinska. Semantic Issues in Deductive Databases and Logic Programs. In R. Banerji, editor, Formal Techniques in Artificial Intelligence. A Source-book, pp. 321–367. North Holland, 1990.

    Google Scholar 

  129. T. Przymusinski. On the Declarative Semantics of Deductive Databases and Logic Programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 193–216. Morgan Kaufman, 1989.

    Google Scholar 

  130. T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401–424, 1991.

    Article  Google Scholar 

  131. T. Przymusinski. Logic Programming and Non-Monotonic Reasoning. Journal of Logic Programming, 17:91–94, 1993. Special Issue on Non-Monotonic Reasoning.

    Article  Google Scholar 

  132. T. Przymusinski. Static Semantics for Normal and Disjunctive Logic Programs. Annals of Mathematics and Artificial Intelligence, 14:323–357, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  133. C.H. Papadimitriou and M. Yannakakis. On the Complexity of Database Queries. In Proc. ACM Symp. on Principles of Database Systems, 1997.

    Google Scholar 

  134. R. Reiter. Deductive Question Answering on relational databases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 149–178. Plenum, New York, 1978.

    Chapter  Google Scholar 

  135. R. Reiter. On Closed World Data Bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 55–76. Plenum, New York, 1978.

    Chapter  Google Scholar 

  136. R. Reiter. Towards a Logical Reconstruction of Relational Database Theory. In M. Brodie, J. Mylopoulos and J.W. Schmidt, editors, On Conceptual Modeling: Perspectives from Artificial Intelligence Databases and Programming Languages, pp. 191–238. Springer-Verlag, Berlin and New York, 1984.

    Google Scholar 

  137. R. Reiter. A Sound and Sometimes Complete Query Evaluation Algorithm for Relational Databases with Null Values. Journal of the ACM, 33(2):349–370, 1986.

    Article  MathSciNet  Google Scholar 

  138. R. Reiter. On Integrity Constraints. In M.Y. Vardi, editor, Proc. Conf. Theoretical Aspects of Reasoning about Knowledge, pp. 97–112, 1988.

    Google Scholar 

  139. P.Z. Revesz. On the Semantics of Theory Change: Arbitration between new and old information. In Proc. ACM Symp. on Principles of Database Systems, pp. 71–82, 1993.

    Google Scholar 

  140. M.A. Roth, H.F. Korth, and A. Silberschatz. Null Values in Nested Databases. Acta Informatica, 26:615–642, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  141. M.A. Roth, H.F. Korth, and A. Silberschatz. Addendum to Null Values in Nested Relational Databases. Acta Informatica, 28:607–610, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  142. A. Rajasekar, J. Lobo, and J. Minker. Weak Generalized Closed World Assumption. Journal of Automated Reasoning, 5:293–307, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  143. V. Royer. The Semantics of Incomplete Databases as an Expression of Preferences. Theoretical Computer Science, 78(1):113–136, January 1991.

    Article  MathSciNet  MATH  Google Scholar 

  144. K.A. Ross and R.W. Topor. Inferring negative information from disjunctive databases. Journal of Automated Reasoning, 4(2):397–424, 1988.

    Article  MathSciNet  MATH  Google Scholar 

  145. C. Sakama. Possible Model Semantics for Disjunctive Databases. In Proc. of the Int. Conf. on Deductive and Object-Oriented Databases (DOOD′90), Kyoto, Japan, December 1989.

    Google Scholar 

  146. E. Sciore. The Universal Instance and Database Design. PhD thesis, Princeton University, Princeton, NJ, 1980.

    Google Scholar 

  147. J. Shepherdson. Negation in Logic Programming. In J. Minker, editor, Deductive Databases and Logic Programming, pp. 19–88. Morgan Kaufmann, Los Altos, CA, 1988.

    Google Scholar 

  148. D. Srivastava, R. Ramakrishnan, and P.Z. Revesz. Constraint objects. In Proc. of the 2nd Int. Workshop on Principles and Practice of Constraint Programming, Springer LNCS No. 874, pp. 218–228, 1994.

    Google Scholar 

  149. M. Stonebraker, editor. The INGRES Papers: Anatomy of a Relational Database System. Addison-Wesley, Reading, Mass., 1986.

    MATH  Google Scholar 

  150. V.S. Subrahmanian. Paraconsistent Disjunctive Deductive Databases. In Proc. of the 20th Int. Symp. on Multiple-Valued Logic, pp. 339–346, Charlotte, NC, May 1990.

    Google Scholar 

  151. A.U. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, editors. Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings, Redwood City, Cal., 1993.

    Google Scholar 

  152. J. Ullman. Principles of Database and Knowledge Base Systems, volume I. Computer Science Press, 1988.

    Google Scholar 

  153. M.Y. Vardi. The complexity of relational query languages. In Proceedings of the ACM Symposium on the Theory of Computing, pp. 137–146, 1982.

    Google Scholar 

  154. M.Y. Vardi. On the integrity of databases with incomplete information. In Proc. ACM Symposium on Principles of Databases, pp. 252–266, 1986.

    Google Scholar 

  155. M.Y. Vardi. Querying Logical Databases. Journal of Computer and System Sciences, 33:142–160, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  156. M.Y. Vardi. On the complexity of bounded-variable queries. In Proc. ACM Symp. on Principles of Database Systems, pp. 266–276, May 1995.

    Google Scholar 

  157. Y. Vassiliou. Null values in database management: a denotational semantics approach. In Proc. of the 1979 ACM SIGMOD Int. Conf. on Management of Data, pp. 162–169, New York, May 1979. ACM Press.

    Google Scholar 

  158. Y. Vassiliou. Functional Dependencies and Incomplete Information. In Int. Conf. on Very Large Databases, pp. 260–269, October 1980.

    Google Scholar 

  159. M. Winslett. Updating Logical Databases. Cambridge University Press, Cambridge, 1990.

    Book  MATH  Google Scholar 

  160. Y. Yia, Z. Feng, and M. Miller. A Multivalued Approach to handle nulls in RDB. In Proc. 2nd Far-East Workshop on Future Database Systems, Kyoto, Japan, April 1992.

    Google Scholar 

  161. A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. Journal of Automated Reasoning, 1(2):141–160, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  162. K. Yue. A More General Model For Handling Missing Information In Relational DataBases Using A 3-Valued Logic. ACM SIGMOD Record, 20(3):43–49, September 1991.

    Article  Google Scholar 

  163. C. Zaniolo. Database Relations with Null Values. Journal of Computer and System Sciences, 28:142–166, 1984.

    Article  MathSciNet  MATH  Google Scholar 

  164. R. Zicari. Incomplete Information in Object-Oriented Databases. A CM SIGMOD Record, 19(3):5–16, September 1990.

    Article  Google Scholar 

  165. E. Zimanyi and A. Pirotte. Imperfect Knowledge in Relational Databases. In A. Motro and P. Smets, editors, Uncertainty Management in Information Systems. Kluwer Academic Publishers, Boston, 1996.

    Google Scholar 

Download references

Authors
  1. Ron van der Meyden
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Monmouth University, USA

    Jan Chomicki

  2. University of Magdeburg, Germany

    Gunter Saake

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer Science+Business Media New York

About this chapter

Cite this chapter

van der Meyden, R. (1998). Logical Approaches to Incomplete Information: A Survey. In: Chomicki, J., Saake, G. (eds) Logics for Databases and Information Systems. The Springer International Series in Engineering and Computer Science, vol 436. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-5643-5_10

Download citation

  • DOI: https://doi.org/10.1007/978-1-4615-5643-5_10

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4613-7582-1

  • Online ISBN: 978-1-4615-5643-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation