Datalog+/-: A New Family of Languages for Ontology Querying

By Andrea Calì (2,3),  Georg Gottlob (1,3),
Thomas Lukasiewicz (1), and  Andreas Pieris (1)
(1) Computing Laboratory University of Oxford, UK
(2) Department of Information Systems and Computing Brunel University, UK
(3) Oxford-Man Institute of Quantitative Finance University of Oxford, UK

PDF Version

Abstract

We briefly report on Datalog±, a family of recently introduced variants of Datalog. In Datalog± languages, Datalog is extended by allowing features such as existential quantifiers, the equality predicate, and the truth constant false to appear in rule heads. At the same time, the resulting language is syntactically restricted, so as to achieve decidability and in some relevant cases even tractability.

Datalog (see, e.g., [1]) has been used as a paradigmatic database programming and query language for over three decades. Rules in Datalog± are so-called tuple-generating dependencies (TGDs), i.e., Datalog (Horn) rules with the possibility of having existentially quantified variables in the head. For example, the rule person(X) →∃Y father(X,Y ) (with the universal quantifiers omitted) expresses the fact that every person has a father. Existential quantification in Datalog± rules allows us to overcome the shortcomings of Datalog as an ontology language [15].

In the following, we will consider the ontological query answering problem as that of answering Boolean conjunctive queries (BCQs) against a database instance D (a set of ground facts) under an ontology Σ constituted by rules. The (decision) problem is to calculate whether q is entailed by D and Σ, written as D ∪ Σq, or, equivalently, whether q has positive answer against D and Σ. Notice that considering BCQs is without loss of generality regarding complexity.

Unfortunately, already for sets Σ of TGDs alone, most basic reasoning and query answering problems are undecidable.  In particular, given an ontology constituted by a set Σ of TGDs, and a set of ground facts D, checking whether D ∪ Σq is undecidable when q is a ground fact [3]. Worse than that, there exist a fixed set of TGDs and a BCQ, and only the database is given as input, where undecidability still holds [4]. Languages in the Datalog± family have various restrictions on the form of the rule bodies, and this allows for decidability of query answering, and in some cases tractability in data complexity, i.e., the complexity when the only input is the instance D, while all the rest is considered fixed.

Guardedness [2] is a well-known restriction of first-order logic that ensures decidability. Based on this notion, guarded TGDs (GTGDs) have been introduced [6, 4]. In a guarded TGD, the rule body is required to have an atom that contains as arguments all body variables of the rule. This class of TGDs ensures polynomial-time data complexity of query answering. The more restricted class of linear TGDs (LTGDs) is the class of TGDs having a single body-atom. Such a class has even better computational properties than GTGDs; in fact, linear TGDs are first-order rewritable, which means that any set Σ of LTGDs, and any BCQ q, can be transformed into a first-order query q_Σ such that Dq_Σ iff D ∪ Σq, for every database D. This property, introduced in [13] in the context of description logics, is essential if D is a very large database, which is the usual case. It means that query answering can be deferred to a standard query language such as (basic, non-recursive) SQL. GTGDs can be enriched by stratified negation, a simple non-monotonic form of negation often used in the context of Datalog [6]. GTGDs are extended by weakly-guarded sets of TGDs [4], where the guardedness condition for rule bodies is somewhat relaxed.

Stickiness, a completely different paradigm for decidable and tractable query answering, was introduced in [9]. The class of sticky sets of TGDs is defined in [9] by a syntactic criterion that is easily testable. Sticky sets of TGDs are first-order rewritable. Extensions of sticky sets of TGDs are studied in [11].

Negative constraints are rules whose head is the truth constant false, denoted by ⊥. It turns out, as shown in [6], that negative constraints can be added to TGDs without any increase of complexity. The reason is that checking whether a rule ρ:body →⊥ is satisfied by a database D, given a Datalog± program Σ, is tantamount to showing that D ∪ Σ ⁄body, i.e., to the evaluation of a BCQ.

Equality-generating dependencies (EGDs) have a body of the same form as TGDs, but having in their head an equality between two variables appearing in the body. Unfortunately, as is well-known in database theory, query answering becomes undecidable even when putting together some extremely week forms of TGDs and EGDs such as inclusion dependencies and functional dependencies [14]. It is interesting for real-world scenarios to study the interaction of TGDs with a very simple, nevertheless very useful class of EGDs, namely key dependencies (or
simply keys).  Semantic and syntactic conditions ensuring that keys are usable without destroying decidability and tractability have been recently studied in [4, 6, 9].

The Datalog± family has several applications—we mention just a few of them, referring the reader, for instance, to [5, 7]. LTGDs and keys (combined with negative constraints) have been used to model and query various extensions of Entity-Relationship schemas [8, 10]. In spite of their restricted syntax, linear TGDs prove to be very useful for ontology modeling and querying: LTGDs with key dependencies and negative constraints are capable of properly capturing the whole DL-Lite family [13, 16]. The F-Logic Lite ontology language, introduced and studied in [12], can also be modeled in the Datalog± framework [4].

References