ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Constraints and Redundancy in Datalog.

Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
@inproceedings{DBLP:conf/pods/LevyS92,
  author    = {Alon Y. Levy and
               Yehoshua Sagiv},
  title     = {Constraints and Redundancy in Datalog},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {67-80},
  ee        = {http://doi.acm.org/10.1145/137097.137111, db/conf/pods/LevyS92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Two types of redundancies in datalog programs are considered. Redundancy based on reachability eliminates rules and predicates that do not participate in any derivation tree of a fact for the query predicate. Redundancy based on irrelevance is similar, but considers only minimal derivation trees, that is, derivation trees having no pair of identical atoms, such that one is an ancestor of the other. Algorithms for detecting these redundancies are given, including the case of programs with constraint literals. These algorithms not only detect redundancies in the presence of constraints, but also push constraints from the given query and rules to the EDB predicates. Under certain assumptions discussed in the paper, the constraints are pushed to the EDB as tightly as possible.

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


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1210 KB]

References

[BK*89]
David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi: Propagating Constraints in Recusive Deduction Databases. NACLP 1989: 981-998 BibTeX
[BS91]
Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240 BibTeX
[Co91]
Bruno Courcelle: Recursive Queries and Context-free Graph Grammars. Theor. Comput. Sci. 78(1): 217-244(1991) BibTeX
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[Ki88]
Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX
[Kl88]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX
[MF*90]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330 BibTeX
[Sag88]
...
[Sar90]
Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73 BibTeX
[Sh87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[SS90]
Seppo Sippu, Eljas Soisalon-Soininen: Multiple SIP Strategies and Bottom-Up Adorning in Logic Query Optimization. ICDT 1990: 485-498 BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[VG90]
Allen Van Gelder: Deriving Constraints Among Argument Sizes in Logic Programs. PODS 1990: 47-60 BibTeX
[Va89]
Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92 BibTeX

Referenced by

  1. Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
  2. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  3. Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237
  4. Elisa Bertino, Barbara Catania: Static Analysis of Intensional Databases in U-Datalog. PODS 1996: 202-212
  5. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  6. Alexander Brodsky, Yoram Kornatzky: The LyriC Language: Querying Constraint Objects. SIGMOD Conference 1995: 35-46
  7. Alon Y. Levy, Yehoshua Sagiv: Semantic Query Optimization in Datalog Programs. PODS 1995: 163-173
  8. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  9. Raghu Ramakrishnan, Divesh Srivastava: Semantics and Optimization of Constraint Queries in Databases. IEEE Data Eng. Bull. 17(2): 14-17(1994)
  10. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
  11. Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67
  12. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
  13. Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
  14. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
  15. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:05 2009