Safety and Translation of Relational Calculus Queries.

@article{DBLP:journals/tods/GelderT91,
  author    = {Allen Van Gelder and
               Rodney W. Topor},
  title     = {Safety and Translation of Relational Calculus Queries},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {2},
  year      = {1991},
  pages     = {235-278},
  ee        = {http://doi.acm.org/10.1145/114325.103712, db/journals/tods/GelderT91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Not all queries in relational calculus can be answered sensibly when disjunction, negation, and universal quantification are allowed. The class of relation 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 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 the class of evaluable formulas is the largest decidable subclass of the domain independent formulas that can be efficiently recognized.

Copyright © 1991 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

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

Conference Version

References

[1]

...

[2]

...

[3]

Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37 BibTeX

[4]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

[5]

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

[6]

Robert Demolombe: Syntactical Characterization of a Subset of Domain-Independent Formulas. J. ACM 39(1): 71-94(1992) BibTeX

[7]

Nachum Dershowitz, Zohar Manna: Proving Termination with Multiset Orderings. Commun. ACM 22(8): 465-476(1979) BibTeX

[8]

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

[9]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX

[10]

Patrick A. V. Hall, Peter Hitchcock, Stephen Todd: An Algebra of Relations for Machine Computation. POPL 1975: 225-232 BibTeX

[11]

Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX

[12]

...

[13]

Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20 BibTeX

[14]

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

[15]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[16]

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

[17]

...

[18]

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

[19]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[20]

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

[21]

...

[22]

...

[23]

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

[24]

Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX

[25]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[26]

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

[27]

Allen Van Gelder, Rodney W. Topor: Safety and Correct Translation of Relational Calculus Formulas. PODS 1987: 313-327 BibTeX

[28]

Moshe Y. Vardi: The Decision Problem for Database Dependencies. Inf. Process. Lett. 12(5): 251-254(1981) BibTeX

Referenced by

1. Lejla Rovcanin, John Murphy: Formal Specification of a Safe ALGEBRA - ``A''. ADBIS (Short Papers) 1999: 214-220
2. Weidong Chen, David Scott Warren: Computation of Stable Models and Its Integration with Logical Query Processing. IEEE Trans. Knowl. Data Eng. 8(5): 742-757(1996)
3. David Toman: Point vs. Interval-based Query Languages for Temporal Databases. PODS 1996: 58-67
4. Michael H. Böhlen, Jan Chomicki, Richard T. Snodgrass, David Toman: Querying TSQL2 Databases with Temporal Logic. EDBT 1996: 325-341
5. M. Tamer Özsu, Randal J. Peters, Duane Szafron, Boman Irani, Anna Lipka, Adriana Muñoz: TIGUKAT: A Uniform Behavioral Objectbase Management System. VLDB J. 4(3): 445-492(1995)
6. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
7. Weidong Chen: Query Evaluation in Deductive Databases with Alternating Fixpoint Semantics. ACM Trans. Database Syst. 20(3): 239-287(1995)
8. Weidong Chen: Declarative Updates of Relational Databases. ACM Trans. Database Syst. 20(1): 42-70(1995)
9. Jan Chomicki, David Toman: Implementing Temporal Integrity Constraints Using an Active DBMS. IEEE Trans. Knowl. Data Eng. 7(4): 566-582(1995)
10. Joonyeoub Sung, Lawrence J. Henschen: A New Recursive Subclass of Domain Independent Formulas Based on Subimplication. ICDE 1995: 475-484
11. Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12
12. M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196
13. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
14. Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Automatic Generation of Production Rules for Integrity Maintenance. ACM Trans. Database Syst. 19(3): 367-422(1994)
15. Aaron Watters: Interpreting a Reconstructed Relational Calculus (Extended Abstract). SIGMOD Conference 1993: 367-376
16. Ashish Gupta, Jennifer Widom: Local Verification of Global Integrity Constraints in Distributed Databases. SIGMOD Conference 1993: 49-58
17. Martha Escobar-Molano, Richard Hull, Dean Jacobs: Safety and Translation of Calculus Queries with Scalar Functions. PODS 1993: 253-264
18. Jan Chomicki: Real-Time Integrity Constraints. PODS 1992: 274-282
19. Richard Hull, Dean Jacobs: Language Constructs for Programming Active Databases. VLDB 1991: 455-467
20. Dean Jacobs, Richard Hull: Database Programming with Delayed Updates. DBPL 1991: 416-428