Chasing Constrained Tuple-Generating Dependencies.

@inproceedings{DBLP:conf/pods/MaherS96,
  author    = {Michael J. Maher and
               Divesh Srivastava},
  title     = {Chasing Constrained Tuple-Generating Dependencies},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {128-138},
  ee        = {http://doi.acm.org/10.1145/237661.237693, db/conf/pods/MaherS96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the implication problem for constrained tuple-generating dependencies (CTGDs), the extension of tuple- and equality-generating dependencies that permits expression of semantic relations (constraints) on variables. The implication problem is central to identifying redundant integrity constraints, checking integrity constraints on constraint databases, detecting independence of queries and updates, and optimizing queries.

We provide two chase procedures for the implication problem. The first is cautious, generating tuples and constraints only when justified, whereas the second is speculative, generating tuples and constraints that have attached conditions about when they exist/hold. The cautious chase is more efficient, in some sense, but less powerful in demonstrating that a CTGD is implied. We demonstrate that, for constraint domains with Independence of Negative Constraints, the two chase procedures are equally powerful. The cautious chase is thus the chase of choice for such constraint domains, and can be used as a weak implication procedure for other constraint domains. We describe the conditions under which the chase procedures can be terminated early without weakening them. We develop a form of magic set optimization for making the chase procedures for CTGDs goal-directed; this is the first such use of magic sets in chase procedures.

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

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[2]

Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337 BibTeX

[3]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) BibTeX

[4]

Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX

[5]

...

[6]

...

[7]

Charles Elkan: A Decision Procedure for Conjunctive Query Disjointness. PODS 1989: 134-139 BibTeX

[8]

Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160 BibTeX

[9]

Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX

[10]

Joxan Jaffar, Michael J. Maher: Constraint Logic Programming: A Survey. J. Log. Program. 19/20: 503-581(1994) BibTeX

[11]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[12]

Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980) BibTeX

[13]

Jean-Louis Lassez, Ken McAloon: A Constraint Sequent Calculus. LICS 1990: 52-61 BibTeX

[14]

Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 BibTeX

[15]

Michael J. Maher: A Logic Programming View of CLP. ICLP 1993: 737-753 BibTeX

[16]

Michael J. Maher: Constrained Dependencies. CP 1995: 170-185 BibTeX

[17]

...

[18]

Xubo Zhang, Z. Meral Özsoyoglu: On Efficient Reasoning with Implication Constraints. DOOD 1993: 236-252 BibTeX