Disjunctive Datalog with existential quantifiers: semantics, decidability, and complexity issues
From MaRDI portal
Abstract: Datalog is one of the best-known rule-based languages, and extensions of it are used in a wide context of applications. An important Datalog extension is Disjunctive Datalog, which significantly increases the expressivity of the basic language. Disjunctive Datalog is useful in a wide range of applications, ranging from Databases (e.g., Data Integration) to Artificial Intelligence (e.g., diagnosis and planning under incomplete knowledge). However, in recent years an important shortcoming of Datalog-based languages became evident, e.g. in the context of data-integration (consistent query-answering, ontology-based data access) and Semantic Web applications: The language does not permit any generation of and reasoning with unnamed individuals in an obvious way. In general, it is weak in supporting many cases of existential quantification. To overcome this problem, Datalogex has recently been proposed, which extends traditional Datalog by existential quantification in rule heads. In this work, we propose a natural extension of Disjunctive Datalog and Datalogex, called Datalogexor, which allows both disjunctions and existential quantification in rule heads and is therefore an attractive language for knowledge representation and reasoning, especially in domains where ontology-based reasoning is needed. We formally define syntax and semantics of the language Datalogexor, and provide a notion of instantiation, which we prove to be adequate for Datalogexor. A main issue of Datalogex and hence also of Datalogexor is that decidability is no longer guaranteed for typical reasoning tasks. In order to address this issue, we identify many decidable fragments of the language, which extend, in a natural way, analog classes defined in the non-disjunctive case. Moreover, we carry out an in-depth complexity analysis, deriving interesting results which range from Logarithmic Space to Exponential Time.
Recommendations
Cites work
- A logic programming approach to knowledge-state planning, semantics and complexity
- Conjunctive query containment revisited
- Data exchange: semantics and query answering
- Modal languages and bounded fragments of predicate logic
- On the Restraining Power of Guards
- Stable models and circumscription
- Testing containment of conjunctive queries under functional and inclusion dependencies
- Tractable reasoning and efficient query answering in description logics: The DL-Lite family
Cited in
(17)- Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin
- Domain expansion for ASP-programs with external sources
- Querying incomplete information in RDF with SPARQL
- On the complexity of ontological reasoning under disjunctive existential rules
- Recent advances in Datalog^
- More on tractable disjunctive Datalog
- An abductive framework for Datalog\(^\pm\) ontologies
- Reasoning on Datalog^ ontologies with abductive logic programming
- The Complexity and Expressive Power of Limit Datalog
- Fast query answering over existential rules
- Reasoning on anonymity in Datalog+/--
- Disjunctive logic programs with existential quantification in rule heads
- Combining decidability paradigms for existential rules
- Logic, languages, and rules for web data extraction and reasoning over data
- Query languages for data exchange: beyond unions of conjunctive queries
- On rules with existential variables: walking the decidability line
- A propositional encoding for first-order clausal entailment over infinitely many constants
This page was built for publication: Disjunctive Datalog with existential quantifiers: semantics, decidability, and complexity issues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4911144)
