Projects per year
Abstract / Description of output
We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2EXPTIME-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
Original language | English |
---|---|
Title of host publication | Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018 |
Subtitle of host publication | July 13-19, 2018, Stockholm, Sweden |
Publisher | International Joint Conferences on Artificial Intelligence Organization |
Pages | 1707-1713 |
Number of pages | 7 |
ISBN (Electronic) | 978-0-9992411-2-7 |
DOIs | |
Publication status | Published - 2018 |
Fingerprint
Dive into the research topics of 'First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries'. Together they form a unique fingerprint.Projects
- 1 Finished
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research
Research output
- 1 Conference contribution
-
First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
Barceló, P., Berger, G., Lutz, C. & Pieris, A., 2018, Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management: Cali, Colombia, May 21-25, 2018. CEUR Workshop Proceedings (CEUR-WS.org), 4 p. (CEUR Workshop Proceedings; vol. 2100).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open AccessFile