Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-97-2-010

Complexity of nonrecursive logic programs with complex values

Vorobyov, Sergei and Voronkov, Andrei

MPI-I-97-2-010. November 1997, 46 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-2-010.ps450 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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.},
}