Edinburgh Research Explorer

Semantic Acyclicity Under Constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=2902302
Original languageEnglish
Title of host publicationProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York, NY, USA
PublisherACM
Pages343-354
Number of pages12
ISBN (Print)978-1-4503-4191-2
DOIs
Publication statusPublished - 15 Jun 2016
Event35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016
http://sigmod2016.org/

Publication series

NamePODS '16
PublisherACM

Conference

Conference35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titleSIGMOD PODS 2016
CountryUnited States
CitySan Francisco
Period26/06/161/07/16
Internet address

Abstract

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 if we focus on keys over unary and binary predicates, then 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 the evaluation problem is tractable.

Event

35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

26/06/161/07/16

San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 31832734