Complexity of Nonrecursive Logic Programs with Complex Values
Sergei G. Vorobyov, Andrei Voronkov
Full Paper (PDF)

Slides (PDF)

Abstract
We investigate complexity of the SUCCESS problem for logic query languages with complex values: check whether a query defines a nonempty set. The SUCCESS problem for recursive query languages with complex values is undecidable, so we study the complexity of nonrecursive queries. By complex values we understand values such as trees, finite sets, and multisets. Due to the well-known correspondence between relational query languages and datalog, our results can be considered as results about relational query languages with complex values. The paper gives a complete complexity classification of the SUCCESS problem for nonrecursive logic programs over trees depending on the underlying signature, presence of negation, and range restrictedness. We also prove several results about finite sets and multisets.

References

References, where available, link to the DBLP on the World Wide Web.

[1]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB Journal 4(4): 727-794(1995)
[2]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[3]
...
[4]
...
[5]
Krzysztof R. Apt, Howard A. Blair: Arithmetic Classification of Perfect Models of Stratified Programs. ICLP/SLP 1988: 765-779
[6]
...
[7]
Krzysztof R. Apt, Roland N. Bol: Logic Programming and Negation: A Survey. JLP 19/20: 9-71(1994)
[8]
...
[9]
Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. JLP 10(1/2/3&4): 181-232(1991)
[10]
Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98
[11]
Leonard Berman: Precise Bounds for Presburger Arithmetic and the Reals with Addition: Preliminary Report. FOCS 1977: 95-99
[12]
Leonard Berman: The Complexitiy of Logical Theories. TCS 11: 71-77(1980)
[13]
...
[14]
Anna R. Bruss, Albert R. Meyer: On Time-Space Classes and their Relation to the Theory of Real Addition. TCS 11: 59-69(1980)
[15]
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. JACM 28(1): 114-133(1981)
[16]
...
[17]
...
[18]
...
[19]
...
[20]
...
[21]
...
[22]
Agostino Dovier, Eugenio G. Omodeo, Enrico Pontelli, Gianfranco Rossi: A Language for Programming in Logic with Finite Sets. JLP 28(1): 1-44(1996)
[23]
Moreno Falaschi, Giorgio Levi, Catuscia Palamidessi, Maurizio Martelli: Declarative Modeling of the Operational Behavior of Logic Languages. TCS 69(3): 289-318(1989)
[24]
...
[25]
Jean H. Gallier, Stan Raatz: Extending SLD Resolution to Equational Horn Clauses using E-Unification. JLP 6(1&2): 3-43(1989)
[26]
...
[27]
...
[28]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359
[29]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. JCSS 43(1): 219-267(1991)
[30]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)
[31]
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987)
[32]
...
[33]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. JCSS 51(1): 26-52(1995)
[34]
Kenneth Kunen: Answer Sets and Negation-as-Failure. ICLP 1987: 219-228
[35]
Kenneth Kunen: Negation in Logic Programming. JLP 4(4): 289-308(1987)
[36]
Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. TCS 116(1&2): 33-57(1993)
[37]
Gabriel M. Kuper: Logic Programming with Sets. JCSS 41(1): 44-64(1990)
[38]
...
[39]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
[40]
Michael J. Maher: Complete Axiomatizations of the Algebras of Finite, Rational and Infinite Trees. LICS 1988: 348-357
[41]
Michael J. Maher: A CLP View of Logic Programming. ALP 1992: 364-383
[42]
Michael J. Maher: A Logic Programming View of CLP. ICLP 1993: 737-753
[43]
...
[44]
...
[45]
...
[46]
Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19
[47]
...
[48]
...
[49]
...
[50]
Oded Shmueli, Shalom Tsur, Carlo Zaniolo: Compilation of Set Terms in the Logic Data Language (LDL). JLP 12(1&2): 89-119(1992)
[51]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. TCS 3(1): 1-22(1976)
[52]
Larry J. Stockmeyer, Albert R. Meyer: Word Problems Requiring Exponential Time: Preliminary Report. STOC 1973: 1-9
[53]
...
[54]
...
[55]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146
[56]
Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995: 266-276
[57]
...
[58]
...
[59]
Hugo Volger: Turing Machines with Linear Alternation, Theories of Bounded Concatenation and the Decision Problem of First Order Theories. TCS 23: 333-337(1983)
[60]
Sergei G. Vorobyov: An Improved Lower Bound for the Elementary Theories of Trees. CADE 1996: 275-287
[61]
Sergei G. Vorobyov: The "Hardest" Natural Decidable Theory. LICS 1997: 294-305
[62]
...
BIBTEX

@inproceedings{DBLP:conf/pods/VorobyovV98,
author = {Sergei G. Vorobyov and
Andrei Voronkov},
title = {Complexity of Nonrecursive Logic Programs with Complex Values},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {244-253},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).