Journal article icon

Journal article

Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity

Abstract:

We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ an...

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

Actions


Access Document


Files:
Publisher copy:
10.1145/3191832

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Department:
Unknown
Role:
Author
More from this funder
Grant:
Jeunes Chercheuses et Jeunes Chercheurs: 12-JS02-007-01
Publisher:
Association for Computing Machinery Publisher's website
Journal:
Journal of the ACM Journal website
Volume:
65
Issue:
5
Publication date:
2018-08-01
Acceptance date:
2018-03-01
DOI:
EISSN:
1557-735X
ISSN:
0004-5411
Source identifiers:
929664
Keywords:
Pubs id:
pubs:929664
UUID:
uuid:cf3a06ae-2384-48b5-99f8-bcc52804a5aa
Local pid:
pubs:929664
Deposit date:
2018-11-13

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