MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2017

2. Number - only D2

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.

  • MPI-I-97-2-010.ps
  • Attachement: ATTJEMVJ (450 KBytes)

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-2-010

Hide details for BibTeXBibTeX
@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.},
}