Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues

Mario Alviano, Wolfgang Faber, Nicola Leone, Marco Manna

Research output: Contribution to journalArticle

26 Citations (Scopus)

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, Datalog∃ 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 Datalog∃, called Datalog∃,˅, 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 Datalog∃,˅, and provide a notion of instantiation, which we prove to be adequate for Datalog∃,˅. A main issue of Datalog∃ and hence also of Datalog∃,˅ 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.
Original languageEnglish
Pages (from-to)701-718
Number of pages18
JournalTheory and Practice of Logic Programming
Volume12
Issue number4-5
DOIs
Publication statusPublished - 1 Jul 2012
Externally publishedYes

Fingerprint

Existential quantifier
Computability and decidability
Datalog
Decidability
Data integration
Semantics
Ontology
Knowledge representation
Semantic Web
Artificial intelligence
Planning
Quantification
Reasoning
Data Integration
Knowledge Representation and Reasoning
Complexity Analysis
Exponential time
Natural Extension
Language
Web Application

Cite this

Alviano, Mario ; Faber, Wolfgang ; Leone, Nicola ; Manna, Marco. / Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues. In: Theory and Practice of Logic Programming. 2012 ; Vol. 12, No. 4-5. pp. 701-718.
@article{c4067adb257948b2af35876e21a997ab,
title = "Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues",
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, Datalog∃ 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 Datalog∃, called Datalog∃,˅, 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 Datalog∃,˅, and provide a notion of instantiation, which we prove to be adequate for Datalog∃,˅. A main issue of Datalog∃ and hence also of Datalog∃,˅ 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.",
author = "Mario Alviano and Wolfgang Faber and Nicola Leone and Marco Manna",
year = "2012",
month = "7",
day = "1",
doi = "10.1017/S1471068412000257",
language = "English",
volume = "12",
pages = "701--718",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "4-5",

}

Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues. / Alviano, Mario; Faber, Wolfgang; Leone, Nicola; Manna, Marco.

In: Theory and Practice of Logic Programming, Vol. 12, No. 4-5, 01.07.2012, p. 701-718.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Disjunctive Datalog with Existential Quantifiers: Semantics, Decidability, and Complexity Issues

AU - Alviano, Mario

AU - Faber, Wolfgang

AU - Leone, Nicola

AU - Manna, Marco

PY - 2012/7/1

Y1 - 2012/7/1

N2 - 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, Datalog∃ 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 Datalog∃, called Datalog∃,˅, 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 Datalog∃,˅, and provide a notion of instantiation, which we prove to be adequate for Datalog∃,˅. A main issue of Datalog∃ and hence also of Datalog∃,˅ 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.

AB - 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, Datalog∃ 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 Datalog∃, called Datalog∃,˅, 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 Datalog∃,˅, and provide a notion of instantiation, which we prove to be adequate for Datalog∃,˅. A main issue of Datalog∃ and hence also of Datalog∃,˅ 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.

UR - https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming

U2 - 10.1017/S1471068412000257

DO - 10.1017/S1471068412000257

M3 - Article

VL - 12

SP - 701

EP - 718

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 4-5

ER -