Conference item icon

Conference item

Semantic acyclicity under constraints

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 acy...

Expand abstract
Publication status:
Published
Peer review status:
Reviewed (other)

Actions


Access Document


Publisher copy:
10.1145/2902251.2902302

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Journal:
35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems Journal website
Pages:
343-354
Host title:
35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Publication date:
2016-06-26
Acceptance date:
2016-03-05
Event location:
San Francisco, CA
Event start date:
2016-06-26T00:00:00Z
DOI:
Source identifiers:
617892
ISBN:
9781450341912
Keywords:
Pubs id:
pubs:617892
UUID:
uuid:3a6b32a4-75b7-4734-9a21-bd5c4f3b3232
Local pid:
pubs:617892
Deposit date:
2016-04-26

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP