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

Bounds on the Propagation of Selection into Logic Programs.

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226
@inproceedings{DBLP:conf/pods/BeeriKBR87,
  author    = {Catriel Beeri and
               Paris C. Kanellakis and
               Fran\c{c}ois Bancilhon and
               Raghu Ramakrishnan},
  title     = {Bounds on the Propagation of Selection into Logic Programs},
  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     = {214-226},
  ee        = {http://doi.acm.org/10.1145/28659.28683, db/conf/pods/BeeriKBR87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We consider the problem of propagating selections (i. e. , bindings of variables) into logic programs. In partucular, we study the class of binary chain programs and define selection propagation as the task of finding an equivalent program containing only unary derived predicates. We associate a context free grammarL(H) with every binary chain program H. We show that, given H propagating a selection involving some constant is possible if L(H) is regular, and therefore undecidable. We also show that propagating a selection of the form p(X,X) is possible if L(H) is finite, and therefore decidable. We demonstrate the connection of these two cases, respectively, with the weak monadic second order theory of one successor and with monadic generalized spectra. We further clarify the analogy between chain programs and languages from the point of view of program equivalence and selection propagation heuristics.

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.

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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. J. Comput. Syst. Sci. 41(2): 157-180(1990) BibTeX

References

[1]
Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 BibTeX
[2]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[3]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
[4]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[5]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[6]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[7]
Meera Blattner: The Unsolvability of the Equality Problem for Sentential Forms of Context-Free Grammars. J. Comput. Syst. Sci. 7(5): 463-468(1973) BibTeX
[8]
...
[9]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[10]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[11]
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
[12]
...
[13]
Michel de Rougemont: Uniform Definability on Finite Structures with Successor. STOC 1984: 409-417 BibTeX
[14]
Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989) BibTeX
[15]
...
[16]
...
[17]
...
[18]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[19]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[20]
...
[21]
...
[22]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[23]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[24]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[25]
James W. Thatcher, Jesse B. Wright: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Mathematical Systems Theory 2(1): 57-81(1968) BibTeX
[26]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[27]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[28]
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX

Referenced by

  1. Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133
  2. Jiawei Han: Chain-Split Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 261-273(1995)
  3. Irène Guessarian, Jean-Eric Pin: Linearizing Some Recursive Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 137-149(1995)
  4. Phokion G. Kolaitis: Combinatorial Games In Database Theory. PODS 1995: 231-232
  5. Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396
  6. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  7. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
  8. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  9. Foto N. Afrati: Bounded Arity Datalog (!=) Queries on Graphs. PODS 1994: 97-106
  10. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  11. Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384
  12. S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279
  13. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
  14. Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990)
  15. Michael Kifer, Eliezer L. Lozinskii: On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering. ACM Trans. Database Syst. 15(3): 385-426(1990)
  16. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  17. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  18. Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
  19. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  20. Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
  21. Irène Guessarian: Deciding Boundedness for Uniformly Connected Datalog Programs. ICDT 1990: 395-405
  22. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
  23. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
  24. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  25. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  26. Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
  27. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. DASFAA 1989: 285-292
  28. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  29. Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336
  30. Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319
  31. Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477
  32. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461
  33. Weining Zhang, Clement T. Yu: A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule. SIGMOD Conference 1987: 345-356
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:33:51 2009