Safety and correct translation of relational calculus formulas

ABSTRACT

Not all queries in relational calculus can be answered “sensibly” once disjunction, negation, and universal quantification are allowed. The class of relational calculus queries, or formulas, that have “sensible” answers is called the domain independent class, which is known to be undecidable. Subsequent research has focused on identifying large decidable subclasses of domain independent formulas In this paper we investigate the properties of two such classes the evaluable formulas and the allowed formulas. Although both classes have been defined before, we give simplified definitions, present short proofs of their man properties, and describe a method to incorporate equality. Although evaluable queries have sensible answers, it is not straightforward to compute them efficiently or correctly. We introduce relational algebra normal form for formulas from which form the correct translation into relational algebra is trivial. We give algorithms to transform an evaluable formula into an equivalent allowed formula, and from there into relational algebra normal form. Our algorithms avoid use of the so-called Dom relation, consisting of all constants appearing in the database or the query. Finally, we describe a restriction under which every domain independent formula is evaluable, and argue that evaluable formulas may be the largest decidable subclass of the domain independent formulas that can be efficiently recognized.

REFERENCES

• Ack68: W Ackermann. Solvable Cases of the Decision Problem. North-Holland, Amsterdam, 1968
• Dec86: H Decker. lntegrity enforcement in deductive databases. In 1st lnt'l Conference on Expert Dalabase Systems, pages 271-285, 1986
• Dem82: R Demolombe. Syntactscal Characteriation of a Subset of Domain Independent Formulas. Techmcal Report, ONERA- CERT, 1982
• DiP69: Robert A. Di Paola, The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas, Journal of the ACM (JACM), v.16 n.2, p.324-327, April 1969 [doi>10.1145/321510.321524]
• Fag80: Ronald Fagin, Horn clauses and database dependencies (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.123-134, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804660]
• Kuh67: J L Kuhns. Answering Questions by Computer A Logtcal Study. Technlcal Report RM-5428-PR, Rand Corp, 1967
• LT84: J W Lloyd and R W Topor. Making Prolog more expressive. Journal of Logic Programming, 1(3) 225-240, 1984
• Mak81: Johann A. Makowsky, Characterizing Data Base Dependencies, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.86-97, July 13-17, 1981
• Man74: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• MUVG86: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• ND82: J -M Nicolas and R Demolombe. On the Stability of Relational Queries. Technical Report, ONERA-CERT, 1982
• Nic82: J-M Nicolas. Logic for improving integrity checking in relational databases. Acta Informatica, 18(3) 227-253, 1982
• Top86: R Topor. Domain Independent Formulas and Databases. Technical Report 86/11, Unniv of Melbourne, 1986 (To appear in Theoretical Computer Science)
• Ull80: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

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