Projects per year
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.
|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|
|Number of pages||7|
|Publication status||Published - 2018|
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 contributionOpen AccessFile