Safety and Correct Translation of Relational Calculus Formulas.

@inproceedings{DBLP:conf/pods/GelderT87,
  author    = {Allen Van Gelder and
               Rodney W. Topor},
  title     = {Safety and Correct Translation of Relational Calculus Formulas},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {313-327},
  ee        = {http://doi.acm.org/10.1145/28659.28693, db/conf/pods/GelderT87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 main 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 equivalentallowed 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.

Copyright © 1987 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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Journal Version

References

[Ack68]

...

[Dec86]

Hendrik Decker: Integrity Enforcement on Deductive Databases. Expert Database Conf. 1986: 381-395 BibTeX

[Dem82]

...

[DiP69]

Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969) BibTeX

[Fag80]

Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX

[Kuh67]

...

[LT84]

John W. Lloyd, Rodney W. Topor: Making Prolog more Expressive. J. Log. Program. 1(3): 225-240(1984) BibTeX

[Mak81]

Johann A. Makowsky: Characterizing Data Base Dependencies. ICALP 1981: 86-97 BibTeX

[Man74]

...

[MUVG86]

Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX

[ND82]

...

[Nic82]

Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX

[Top86]

Rodney W. Topor: Domain-Independent Formulas and Databases. Theor. Comput. Sci. 52: 281-306(1987) BibTeX

[Ull80]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

1. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
2. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
3. Allen Van Gelder, Rodney W. Topor: Safety and Translation of Relational Calculus Queries. ACM Trans. Database Syst. 16(2): 235-278(1991)
4. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
5. Kyu-Young Whang, Ashok Malhotra, Gary H. Sockut, Luanne M. Burns: Supporting Universal Quantification in a Two-Dimensional Database Query Language. ICDE 1990: 68-75
6. Gultekin Özsoyoglu, Victor Matos, Z. Meral Özsoyoglu: Query Processing Techniques in the Summary-Table-by-Example Database Query Language. ACM Trans. Database Syst. 14(4): 526-573(1989)
7. François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204
8. François Bry: Logic Programming as Constructivism: A Formalization and its Application to Databases. PODS 1989: 34-50
9. François Bry: Logical Rewritings for Improving the Evaluation of Quantified Queries. MFDBS 1989: 100-116
10. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
11. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163