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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems|Proc ACM SIGACT SIGMOD SIGART Symp Princ Database Syst |
| Editors | Anon |
| Place of Publication | New York, NY, United States |
| Publisher | Association for Computing Machinery |
| Pages | 244-253 |
| Number of pages | 9 |
| Publication status | Published - 1998 |
| Event | Proceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS - Seattle, WA, USA Duration: 1 Jul 1998 → … http://dblp.uni-trier.de/db/conf/pods/pods98.html#VorobyovV98http://dblp.uni-trier.de/rec/bibtex/conf/pods/VorobyovV98.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/pods/VorobyovV98 |
Conference
| Conference | Proceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS |
|---|---|
| City | Seattle, WA, USA |
| Period | 1/07/98 → … |
| Internet address |