max planck institut
informatik
informatik
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): |
|---|---|
| 450 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX