7 papers · 1 filter
Non-Uniformly Terminating Chase: Size and Complexity
Marco Calautti, Georg Gottlob, Andreas Pieris
The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central…
Uniform Operational Consistent Query Answering
Marco Calautti, Ester Livshits, Andreas Pieris +1
Operational consistent query answering (CQA) is a recent framework for CQA, based on revised definitions of repairs and consistent answers, which opens up the possibility of effici…
First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
Pablo Barcelo, Gerald Berger, Carsten Lutz +1
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,…
When is Ontology-Mediated Querying Efficient?
Pablo Barcelo, Cristina Feier, Carsten Lutz +1
In ontology-mediated querying, description logic (DL) ontologies are used to enrich incomplete data with domain knowledge which results in more complete answers to queries. However…
The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
Pablo Barcelo, Victor Dalmau, Cristina Feier +2
Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-med…
All-Instances Restricted Chase Termination
Tomasz Gogacz, Jerzy Marcinkowski, Andreas Pieris
The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination:…