MPI-INF/SWS Research Reports 1991-2021
2. Number - All Departments
MPI-I-97-2-010
Complexity of nonrecursive logic programs with complex values
Vorobyov, Sergei and Voronkov, Andrei
November 1997, 46 pages.
.Status: available - back from printing
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.
Note:
Colby, L. ``Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database systems (PODS'98)', 1998, organization: ACM, June 1-3,
note: to appear.
-
- Attachement: ATTJEMVJ (450 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-2-010
BibTeX@TECHREPORT{VorobyovVoronkov97,
AUTHOR = {Vorobyov, Sergei and Voronkov, Andrei},
TITLE = {Complexity of nonrecursive logic programs with complex values},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-97-2-010},
MONTH = {November},
YEAR = {1997},
ISSN = {0946-011X},
NOTE = {Colby, L. ``Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database systems (PODS'98)', 1998, organization: ACM, June 1-3,
note: to appear.},
}