Taming the infinite chase: query answering under expressive relational constraints
From MaRDI portal
Publication:2856474
DOI10.1613/JAIR.3873zbMATH Open1361.68221arXiv1212.3357OpenAlexW1824207140WikidataQ129489739 ScholiaQ129489739MaRDI QIDQ2856474FDOQ2856474
Authors: Andrea Calí, Georg Gottlob, Michael Kifer 
Publication date: 29 October 2013
Published in: The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)
Abstract: The chase algorithm is a fundamental tool for query evaluation and query containment under constraints, where the constraints are (sub-classes of) tuple-generating dependencies (TGDs) and equality generating depencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates, with some notable exceptions. In this paper we take a general approach, and we propose large classes of TGDs under which the chase does not always terminate. Our languages, in particular, are inspired by guarded logic: we show that by enforcing syntactic properties on the form of the TGDs, we are able to ensure decidability of the problem of answering conjunctive queries despite the non-terminating chase. We provide tight complexity bounds for the problem of conjunctive query evaluation for several classes of TGDs. We then introduce EGDs, and provide a condition under which EGDs do not interact with TGDs, and therefore do not take part in query answering. We show applications of our classes of constraints to the problem of answering conjunctive queries under F-Logic Lite, a recently introduced ontology language, and under prominent tractable Description Logics languages. All the results in this paper immediately extend to the problem of conjunctive query containment.
Full work available at URL: https://arxiv.org/abs/1212.3357
Recommendations
Cited In (50)
- Combining description logics, description graphs, and rules
- Preserving constraints with the stable chase
- Title not available (Why is that?)
- Datalog: Bag Semantics via Set Semantics
- Foundations of ontology-based data access under bag semantics
- A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
- Representing ontologies using description logics, description graphs, and rules
- On the data complexity of consistent query answering
- Title not available (Why is that?)
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- Finite Open-World Query Answering with Number Restrictions
- Recent advances in Datalog\(^\pm \)
- Tractable query answering and rewriting under description logic constraints
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- Converging to the chase -- a tool for finite controllability
- Semi-oblivious chase termination: the sticky case
- Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin
- Characterizing boundedness in chase variants
- On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
- Answer Counting under Guarded TGDs
- Query answering with transitive and linear-ordered data
- Title not available (Why is that?)
- The notion of abstraction in ontology-based data management
- Acyclicity notions for existential rules and their application to query answering in ontologies
- Adding Metalogic Features to Knowledge Representation Languages*
- Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
- MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations
- Guarded Ontology-Mediated Queries
- The impact of active domain predicates on guarded existential rules
- Title not available (Why is that?)
- A more general theory of static approximations for conjunctive queries
- Title not available (Why is that?)
- Query answering under probabilistic uncertainty in Datalog\(+/-\) ontologies
- Finite open-world query answering with number restrictions
- Query Answering in the Description Logic Horn- $\mathcal{SHIQ}$
- Rewriting guarded existential rules into small Datalog programs
- Reasoning on anonymity in Datalog
- Uniform Restricted Chase Termination
- On the data complexity of consistent query answering over graph databases
- Polynomial combined first-order rewritings for linear and guarded existential rules
- Datalog and Its Extensions for Semantic Web Databases
- On the interaction of existential rules and equality constraints in ontology querying
- Explanation-friendly query answering under uncertainty
- Semantic acyclicity for conjunctive queries: approximations and constraints
- Preference-based inconsistency-tolerant query answering under existential rules
- Inconsistency-tolerant query answering for existential rules
- Logic, languages, and rules for web data extraction and reasoning over data
- Generative Datalog with continuous distributions
- Finite model reasoning over existential rules
This page was built for publication: Taming the infinite chase: query answering under expressive relational constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2856474)
