ML p(r)ior | Semantic Acyclicity Under Constraints

Semantic Acyclicity Under Constraints

2016-02-03
A conjunctive query (CQ) is semantically acyclic if it is equivalent to an acyclic one. Semantic acyclicity has been studied in the constraint-free case, and deciding whether a query enjoys this property is NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (tgds) that can express, e.g., inclusion dependencies, or equality-generating dependencies (egds) that capture, e.g., functional dependencies, a CQ may turn out to be semantically acyclic under the constraints while not semantically acyclic in general. This opens avenues to new query optimization techniques. In this paper we initiate and develop the theory of semantic acyclicity under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically acyclic under the constraints, or, in other words, is the query equivalent to an acyclic one over all those databases that satisfy the set of constraints? We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not sufficient condition for the decidability of semantic acyclicity. In particular, we show that semantic acyclicity is undecidable in the presence of full tgds (i.e., Datalog rules). In view of this fact, we focus on the main classes of tgds for which CQ containment is decidable, and do not capture the class of full tgds, namely guarded, non-recursive and sticky tgds. For these classes we show that semantic acyclicity is decidable, and its complexity coincides with the complexity of CQ containment. In the case of egds, we show that for keys over unary and binary predicates semantic acyclicity is decidable (NP-complete). We finally consider the problem of evaluating a semantically acyclic query over a database that satisfies a set of constraints; for guarded tgds and functional dependencies this problem is tractable.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-06-03

Data integration systems allow users to access data sitting in multiple sources by means of queries … show more
PDF

Highlights - Most important sentences from the article

2018-08-14

We investigate parameterizations of both database instances and queries that make query evaluation f… show more
PDF

Highlights - Most important sentences from the article

2017-01-03

We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences… show more
PDF

Highlights - Most important sentences from the article

2019-02-13
1902.04960 | cs.CC

Conjunctive queries select and are expected to return certain tuples from a relational database. We … show more
PDF

Highlights - Most important sentences from the article

2019-04-01

Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hyp… show more
PDF

Highlights - Most important sentences from the article

2019-04-01

We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RP… show more
PDF

Highlights - Most important sentences from the article

2018-03-17

Duplicates in data management are common and problematic. In this work, we present a translation of … show more
PDF

Highlights - Most important sentences from the article

2019-01-12

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applicati… show more
PDF

Highlights - Most important sentences from the article

2018-04-19

In ontology-based data access (OBDA), the classical database is enhanced with an ontology in the for… show more
PDF

Highlights - Most important sentences from the article

2017-06-24
1706.07936 | cs.DB

We consider answering queries where the underlying data is available only over limited interfaces wh… show more
PDF

Highlights - Most important sentences from the article

2018-08-07

Rule-based temporal query languages provide the expressive power and flexibility required to capture… show more
PDF

Highlights - Most important sentences from the article

2018-09-27
1809.10286 | cs.DB

We propose a generic numerical measure of the inconsistency of a database with respect to a set of i… show more
PDF

Highlights - Most important sentences from the article

2018-09-16

Vadalog is a system for performing complex reasoning tasks such as those required in advanced knowle… show more
PDF

Highlights - Most important sentences from the article

2012-05-25

We study the expression complexity of two basic problems involving the comparison of primitive posit… show more
PDF

Highlights - Most important sentences from the article

2014-08-05
1408.0890 | cs.CC

Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are … show more
PDF

Highlights - Most important sentences from the article

2014-06-30

The containment problem of Datalog queries is well known to be undecidable. There are, however, seve… show more
PDF

Highlights - Most important