Taming the infinite chase: query answering under expressive relational constraints
From MaRDI portal
Publication:2856474
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.
Recommendations
Cited in
(50)- Combining description logics, description graphs, and rules
- Preserving constraints with the stable chase
- scientific article; zbMATH DE number 7561477 (Why is no real title available?)
- Datalog: Bag Semantics via Set Semantics
- Foundations of ontology-based data access under bag semantics
- On the data complexity of consistent query answering
- Representing ontologies using description logics, description graphs, and rules
- A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
- scientific article; zbMATH DE number 7561661 (Why is no real title available?)
- 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}\)
- 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
- Converging to the chase -- a tool for finite controllability
- 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
- scientific article; zbMATH DE number 7471691 (Why is no real title available?)
- The notion of abstraction in ontology-based data management
- Acyclicity notions for existential rules and their application to query answering in ontologies
- Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
- Adding Metalogic Features to Knowledge Representation Languages*
- MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations
- A more general theory of static approximations for conjunctive queries
- Guarded Ontology-Mediated Queries
- The impact of active domain predicates on guarded existential rules
- scientific article; zbMATH DE number 1755626 (Why is no real title available?)
- Query answering under probabilistic uncertainty in Datalog\(+/-\) ontologies
- scientific article; zbMATH DE number 7566070 (Why is no real title available?)
- 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
- On the data complexity of consistent query answering over graph databases
- Reasoning on anonymity in Datalog
- Uniform Restricted Chase Termination
- Datalog and Its Extensions for Semantic Web Databases
- Polynomial combined first-order rewritings for linear and guarded existential rules
- On the interaction of existential rules and equality constraints in ontology querying
- Explanation-friendly query answering under uncertainty
- Preference-based inconsistency-tolerant query answering under existential rules
- Semantic acyclicity for conjunctive queries: approximations and constraints
- 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)
