Decidability and Expressiveness of Logic Queries.

@inproceedings{DBLP:conf/pods/Shmueli87,
  author    = {Oded Shmueli},
  title     = {Decidability and Expressiveness of Logic Queries},
  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     = {237-249},
  ee        = {http://doi.acm.org/10.1145/28659.28685, db/conf/pods/Shmueli87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper addresses some basic problems regarding logic programming based queries over relational databases. We re-examine the query classes H and YE⁺ defined by Chandra and Hare1 [2]. We defineH⁺ and YE⁺⁺ which differ from H and YE⁺ in that the use of equality (=) and inequality (#) is prohibited. We show that H⁺ is more expressive than YE⁺⁺ and that any H⁺ program can be transformed into an equivalent H⁺ program contaning a single recursive predicate without using the equality or inequality operators. As a corollary we obtain a fixpoint formula characterization of H⁺ queries.

We consider the problems of determining containment, equivalence, and satisfiability of logic based queries. The containment and equivalence problems addressed here extend the work of Aho, Sagiv and Ullman on relational queries [l] and Papadimitriou on Prolog [lo]. As corollaries we show that determining safety and literal redundancy are both undecidable problems.

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

Online Edition: ACM Digital Library

Journal Version

References

[1]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[2]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[3]

...

[4]

Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX

[5]

...

[6]

John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX

[7]

...

[8]

...

[9]

...

[10]

...

[11]

Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX

[12]

...

[13]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[14]

David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281 BibTeX

Referenced by

1. Foto N. Afrati, Manolis Gergatsoulis, Theodoros G. Kavalieros: Answering Queries Using Materialized Views with Disjunctions. ICDT 1999: 435-452
2. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263
3. Danilo Montesi, Elisa Bertino, Maurizio Martelli: Transactions and Updates in Deductive Databases. IEEE Trans. Knowl. Data Eng. 9(5): 784-797(1997)
4. Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116
5. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
6. Elisa Bertino, Barbara Catania: Static Analysis of Intensional Databases in U-Datalog. PODS 1996: 202-212
7. Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
8. Irène Guessarian, Jean-Eric Pin: Linearizing Some Recursive Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 137-149(1995)
9. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
10. Sergio Greco, Luigi Palopoli, Eugenio Spadafora: Datalog^A: Array Manipulations in a Deductive Database Language. DASFAA 1995: 180-188
11. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
12. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
13. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
14. Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55
15. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116
16. Foto N. Afrati: Bounded Arity Datalog (!=) Queries on Graphs. PODS 1994: 97-106
17. Ouri Wolfson, Aya Ozeri: Parallel and Distributed Processing of Rules by Data Reduction. IEEE Trans. Knowl. Data Eng. 5(3): 523-530(1993)
18. Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
19. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
20. Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han: Classification and Compilation of Linear Recursive Queries in Deductive Databases. IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
21. Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
22. Guozhu Dong: Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations. PODS 1992: 81-90
23. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
24. Stéphane Grumbach: A Paradox in Database Theory. ICDT 1992: 312-325
25. Tomás Feder, Yatin P. Saraiya: Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations. ICDT 1992: 297-311
26. Laks V. S. Lakshmanan, Rokia Missaoui: On Semantic Query Optimization in Deductive Databases. ICDE 1992: 368-375
27. Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101
28. Richard Hull, Masatoshi Yoshikawa: On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991: 328-340
29. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12
30. Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240
31. Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25
32. Ke Wang, Li-Yan Yuan: First-Order Logic Reducible Programs. ICDE 1991: 746-755
33. 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)
34. 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)
35. Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142
36. Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73
37. Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71
38. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
39. Mariano P. Consens, Alberto O. Mendelzon: GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990: 404-416
40. Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229
41. Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378
42. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
43. Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181
44. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
45. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
46. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
47. Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
48. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
49. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
50. 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
51. Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226