hide
Free keywords:
-
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.
