A sound and sometimes complete query evaluation algorithm for relational databases with null values

ABSTRACT

A sound and, in certain cases, complete method is described for evaluating queries in relational databases with null values where these nulls represent existing but unknown individuals. The soundness and completeness results are proved relative to a formalization of such databases as suitable theories of first-order logic. Because the algorithm conforms to the relational algebra, it may easily be incorporated into existing relational systems.

REFERENCES

• 1: BISKUP, J. Null values in database relations. In Advances in Data Base Theory, vol. 1, H. Gallaire, J. Minker, and J. M., Nicolas, Eds. Plenum Press, New York, 1981, pp. 299-341.
• 2: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 3: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 4: IMIF.LINSKI, T. On algebraic query processing in logical databases. In Advances in Database Theory, vol. 2, H. Gallaire, J. Minker, and J. M. Nicolas, Eds. Plenum Press, New York, 1984.
• 5: KING, J. QUIST: A system for semantic query optimization in relational databases. In Proceedings of the 7th Conference on Very Large Databases (Sept.). 1981, pp. 510-517.
• 6: LEVESQUE, H. J. A formal treatment of incomplete knowledge bases. FLAIR Tech. Rep. 3, Fairchild Laboratory for Artificial Intelligence Research, Palo Alto, Calif., Feb. 1982.
• 7: REIT~R, R. On closed world data bases. In Logic" and Data Bases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, 1978, pp. 55-76.
• 8: Raymond Reiter, Equality and Domain Closure in First-Order Databases, Journal of the ACM (JACM), v.27 n.2, p.235-249, April 1980 [doi>10.1145/322186.322189]
• 9: Raymond Reiter, Data bases: A logical perspective, Proceedings of the 1980 workshop on Data abstraction, databases and conceptual modeling, p.174-176, June 23-26, 1980, Pingree Park, Colorado, United States
• 10: RE~TER, R. Towards a logical reconstruction of relational database theory. In On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases, and Programming Languages. M. L. Brodie, J. Mylopoulos, and J. W. Schmidt, Eds. Springer-Verlag, New York, 1984, pp. 191-233.
• 11: Moshe Y. Vardi, Querying logical databases, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.57-65, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325413]
• 12: Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
• 13: WALKER, A. Time and space in a lattice of universal relations with blank entries. In XP1 Workshop on Relational Database Theory (Stony Brook, N.Y., June/July). 1980.
• 14: ZANIOLO, C. Relational views in a database system; Support for queries. In Proceedings of the IEEE Computer Applications and Software Conference (Chicago, Ill., Nov. 8-11 ). IEEE, New York, 1977, pp. 267-275.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Management, Performance, Theory, Verification