Conference item icon

Conference item

Tractability beyond β-acyclicity for conjunctive queries with negation

Abstract:

Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is β-acyclic. Despite the importance of many of these problems, there has been little success in generalizing these results beyond acyclicity. In this paper, we take on this challenge and propose nest-set width, a novel generalization of hypergraph β-acyclicity. We demonstrate that nest-set width has desirable properties and algorithmic s...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/3452021.3458308

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Pages:
355–369
Host title:
PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Publication date:
2021-06-20
Acceptance date:
2021-04-14
Event title:
ACM SIGMOD/PODS 2021: International Conference on Management of Data
Event location:
Virtual event (Xi'an, Shaanxi, China)
Event website:
https://2021.sigmod.org/
Event start date:
2021-06-20T00:00:00Z
Event end date:
2021-06-25T00:00:00Z
DOI:
ISBN:
9781450383813
Language:
English
Keywords:
Pubs id:
1172620
Local pid:
pubs:1172620
Deposit date:
2021-04-20

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