Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue

1 Introduction

RDF is the W3C recommendation data model to represent information about World Wide Web resources, while SPARQL is the standard language for querying RDF data, since its standardization in 2008. One of the distinctive features of Semantic Web data is the existence of vocabularies with predefined semantics: the RDF Schema (RDFS) and the Ontology Web Language (OWL), which can be used to derive logical conclusions from RDF graphs; hence, an RDF query language equipped with reasoning capabilities to deal with these vocabularies is desirable. In addition, navigational capabilities are vital for data models with an explicit graph structure such as RDF [Alkhateeb et al., 2009; Arenas et al., 2009; P´erez et al., 2010; Fionda et al., 2012], while recursive definitions are a key feature for graph query languages [Barcel´o, 2013; Libkin et al., 2013]. Having an RDF query language available that combines the above key functionalities is of paramount importance for the development of the Semantic Web. This has been recognized by the W3C, which led to the release of SPARQL 1.1 in 2013 [Harris and Seaborne, 2013; Glimm and Ogbuji, 2013], that is, an extended version of the 2008 language with reasoning capabilities to deal with RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. However, there are still useful queries that cannot be expressed in SPARQL 1.1, due to the lack of general recursion [Libkin et al., 2013].

To the best of our knowledge, the only language that supports the above features, focussing on the profile OWL 2 QL of OWL 2, while its query evaluation problem is tractable in data complexity, is the recently introduced rule-based language TriQ-Lite, the lite version of the highly expressive triple query (TriQ) language [Arenas et al., 2014]. This language is based on Datalog∃,¬s,⊥, that is, Datalog extended with existential quantification in rule-heads, stratified negation, and negative constraints with the falsum (⊥) in ruleheads. Unfortunately, TriQ-Lite suffers from a serious drawback, which may revoke its advantage as an expressive RDF query language, namely it is not a plain language. A query language is called plain if it allows the user to write a query as a single program in a simple non-composite syntax. An example of a plain query language is Datalog, where the user simply needs to define a single Datalog program that captures the intended query. The property of plainness provides conceptual simplicity, which is considered to be a key condition for a query language to be useful in practice. Although TriQ-Lite is based on an extension of Datalog, the way its syntax and semantics are defined significantly deviates from the standard way of defining Datalog-like languages, and thus does not inherit the plainness of Datalog. In fact, TriQ-Lite is a composite language, where the user is forced to split the query in several modules Π1, . . . ,Πn so that each Πi can be expressed by the fragment of Datalog∃,¬s,⊥ that is underlying TriQ-Lite, while each pair (Πi, Πi+1) is bridged via a set Qi of conjunctive queries (more details are given in Section 4).

From the above discussion, we conclude that an RDF query language that fulfills certain desiderata, which in turn guarantee its applicability in real Semantic Web applications, is currently missing. These desiderata are the following:

1. Plainness: simple syntax and semantics, with the aim of simplifying the definition of queries;
2. Reasoning Capabilities: express every SPARQL query under the entailment regime for OWL 2 QL;
3. Recursive Definitions: general form of recursion must be supported, and ideally Datalog must be incorporated;
4. Efficiency: query evaluation must be data tractable, and feasible by the use of standard database technology.

At this point, we would like to expose an additional (conceptual) shortcoming of SPARQL 1.1, which must be taken

into account during the designing of an RDF query language. Under the OWL 2 direct semantics entailment regime, the evaluation of a basic graph pattern over an RDF graph adopts the so-called active domain semantics, i.e., it uses the notion of entailment in OWL 2 QL, but allowing variables and blank nodes to take only values from the RDF graph. As discussed in [Arenas et al., 2014], this forces the user to encode part of the reasoning in the actual query, which undoubtedly leads to unnatural and complex queries (an example is given in Section 3). Notably, TriQ-Lite provides the definition of the more natural entailment regime, where the active domain semantics is dropped. This is certainly an additional desideratum:

1. Reasoning-Query Decoupling: the entailment regime without the active domain semantics must be definable, with the aim of decoupling the reasoning from the query.

In this work, we focus on TriQ-Lite, which is a language in evolution, and we investigate how it can be transformed into a plain language without sacrificing any of the other desiderata. The outcome of our study is TriQ-Lite 1.0, the new version of TriQ-Lite, which is based on Datalog∃,¬sg,⊥; we use the superscript ¬sg (instead of ¬s) since, for our purposes, it suffices to focus on negation that, apart from being stratified, is also grounded, i.e., it can be used with predicates that can only store constants. The proposed formalism is part of Datalog±, that is, a family of logical KR languages [Cal`ı et al., 2012a]. Although several interesting Datalog± languages can be found in the literature (see, e.g., [Baget et al., 2011; Thomazo et al., 2012; Leone et al., 2012; Cal`ı et al., 2012b; 2013]), none of them fulfills all desiderata. Even though Datalog± languages inherit the plainness of Datalog, either they are not expressive enough for satisfying desiderata 2, 3 and 5, or very expressive and thus intractable. Hence, our key challenge was to define a Datalog± language that achieves the right balance between expressivity and complexity.

We present a new syntactic paradigm, which is underlying TriQ-Lite 1.0, called wardedness, that can be informally described as follows: all the dangerous body-variables, i.e., variables that may be bound by the program to non-constant values, and at the same time are propagated to the rule-head, occur in exactly one body-atom, called ward, that can interact with the rest of the rule-body only via harmless join variables, i.e., variables that are bound by the program to database constants. Our technical results can be summarized as follows:

• We introduce in Section 4 TriQ-Lite 1.0, which is based on warded Datalog∃,¬sg,⊥, and show that it fulfills all desiderata; the technical reasons are given in Table 1.
• For the reasoning-query decoupling, apart from expres-
• sive joins among body-variables that are bound to nonconstant values (this exposes one of the main limitations of the language underlying TriQ-Lite), it is vital to allow for existentially quantified variables in rule-heads; this issue is discussed in Section 5.
• We provide in Section 6 a formal justification for the necessity of introducing a new Datalog-based formalism. We establish, via a model-theoretic argument, that existing tractable formalisms are not able to encode the OWL 2 direct semantics entailment regime, and at the same time ensure the reasoning-query decoupling.
• Finally, in Section 7, we substantiate the design choices made in the definition of our formalism. In fact, we show that very mild extensions lead to EXPTIME-hardness.

Let us say that warded Datalog∃,¬sg,⊥, the formalism underlying TriQ-Lite 1.0, is well-suited as a general-purpose KR language, since it extends Datalog with features that allow us to express OWL 2 QL and OWL 2 RL ontologies.

2 Relational Databases and Datalog∃,¬s,⊥

Consider the following pairwise disjoint (infinite countable) sets: a set C of constants, a set N of (labeled) nulls, and a set V of variables. A term t is a constant, null, or variable. An atom has the form p(t1, . . . , tn), where p is an n-ary predicate, and ti's are terms. For an atom a, dom(a) and var(a) is the set of its terms and variables, respectively; these extend to sets of atoms. An instance I is a (possibly infinite) set of atoms p(t), where t is a tuple of constants and labeled nulls. A database D is a finite instance where only constants occur.

A Datalog∃,¬ rule ρ is an expression of the following form: a1 , . . . , an , ¬b1 , . . . , ¬bm → ∃Y1 . . . ∃Yk c, where (with A = {a1 , . . . , an} and B = {b1 , . . . , bm}): n ⩾ 1 and m, k ⩾ 0; ai 's and bj 's are atoms with terms from (C ∪ V); var(B) ⊆ var(A); var(A) ∩ {Y1, . . . , Yk} = ∅; and c contains terms from (C ∪ {Y1, . . . , Yk} ∪ var(A)). The set A is denoted B +(ρ), while B is denoted B -(ρ). The body of ρ, denoted B(ρ), is defined as (A ∪ B). The atom c is the head of ρ, denoted H(ρ). A Datalog∃,¬ program Π is a finite set of Datalog∃,¬ rules. A stratification of Π is defined in the same way as for Datalog¬. We say that Π is stratified if there exists a stratification of Π. A constraint ν is an assertion a1 , . . . , an → ⊥, where n ⩾ 1 and ai 's are atoms with terms from (C ∪ V). The body of ν, denoted B(ν), is the set {a1 , . . . , an}. A Datalog∃,¬,⊥ program Π is a finite set of Datalog∃,¬ rules and constraints. We denote by ex (Π) the set of Datalog∃,¬ rules in Π; Π is stratified if ex(Π) is stratified. A stratified Datalog∃,¬,⊥ query Q is a pair (Π, p), where Π is a stratified Datalog∃,¬,⊥ program, and p is a predicate not in the set of predicates occurring in Π, denoted sch(Π). For brevity, we write Datalog∃,¬s,⊥ for stratified Datalog∃,¬,⊥.

The semantics Π(D) of a program Π over a database D is defined in a standard way via the chase procedure; for details see [Cal`ı et al., 2012a]. Let Q = (Π, p) be a Datalog∃,¬s,⊥ query, where p is an n-ary predicate. If Π(D) is defined (Π(D) may be undefined due to the constraints), then the evaluation of Q over D, denoted Q(D), is defined as the set of tuples {t ∈ Cn | p(t) ∈ Π(D)}. The data complexity of query evaluation is calculated by considering the query fixed.

3 SPARQL over OWL 2 QL into Datalog∃,¬s,⊥

As recently shown in [Arenas et al., 2014], SPARQL queries under OWL 2 direct semantics entailment regime over OWL 2 QL ontologies can be embedded into Datalog∃,¬s,⊥. In particular, for a graph pattern P and an RDF graph G, it is possible to construct a Datalog∃,¬s,⊥ query QP such that the answer to P over G can be easily decoded from QP (DG), where DG = {triple(a, b, c) | (a, b, c) ∈ G}. For the sake of completeness, we briefly recall how the query QP is constructed. The reader who is familiar with this construction can directly go to Section 4.

3.1 SPARQL into Datalog¬s

For brevity, we first disregard the direct semantics entailment regime, and we illustrate, via some simple examples taken from [Arenas et al., 2014], the main ingredients of the translation of a SPARQL query into a Datalog¬s query.

Example 1 Let P1 be the graph pattern (?X, name, ?Y ), where name is a constant, which asks for the list of pairs (a, b) of elements from an RDF graph G such that b is the name of a in G. P1 is represented via the rule

The predicate queryP1 is used to store the answer to the graph pattern P1. Assume now that P2 is the graph pattern (?X, name, B), where B is a blank node, which asks for the list of elements in G that have a name (we are not interested in retrieving the blank nodes). P2 is represented via the rule

Notice that the variable Y represents the blank node B, and it does not appear in the head since we are not interested in retrieving names. Finally, consider the graph pattern P3

where phone is a property constant. For every constant a in an RDF graph, P3 asks for the name and phone of a, if a's phone number is available in G, and otherwise it asks only for the name of a. Q1 and Q2 are represented via the rules

Having the predicates queryQ1 and queryQ2 in place, we can now represent P3 as follows. First, we define a set of rules for the cases where the phone number is available:

The predicate compatibleP3 is used to store the individuals with phone numbers, which will be used in the rule that takes care of the individuals without phone numbers:

The superscript {3} in the binary predicate queryP3 indicates that the third argument in the answer to P3 is missing.

The approach shown above can be generalized to represent any graph pattern. Let P = {t1, . . . , tn} be a basic graph pattern such that ti = (ui, vi,wi), for every i ∈ [1, n], with {?X1, . . . , ?Xk} be the set of variables in P. Assume that γ is a substitution such that for every symbol u occurring in P , γ(u) = u if u ∈ C, γ(u) = X if u =?X, and γ(u) is a fresh variable if u is a blank node. Then, ρbgp P is defined as the rule:

For a non-basic graph pattern P , Πbgp P is the Datalog program consisting of the rules ρbgp Q for each basic graph pattern Q in P . Moreover, Πopr P is defined as the Datalog¬s program that represents the non-basic graph patterns in P; in fact, Πopr P encodes the semantics of the SPARQL operators occurring in P as explained in Example 1. For our purposes, the formal definition of Πopr P is not important, and therefore we skip it. However, it is crucial to say that Πopr P is a Datalog¬s program. Finally, the program Πout P , which defines the output predicate ansP , is constructed as follows. By construction, some atoms of the form query JP (X1, . . . ,Xk), where J is a set of indexes, occur in the head of some rules of Πopr P (see atom query {3} P (X, Y ) in Example 1); if J = ∅ we simply write queryP (X1, . . . ,Xk). Let mP be the arity of the predicate queryP , i.e., the query-predicate without superscript, occurring in Πopr P . For every atom query JP (X1, . . . ,Xk) in Πopr P , the following rule occurs in Πout P :

where, for each i ∈ J, ti is the special constant ⋆, and after eliminating all the occurrences of ⋆ from (t1, . . . , tn) the tuple (X1, . . . ,Xk) is obtained. For instance, due to the atom query {3} P (X, Y ) occurring in Πopr P3 , where P3 is the graph pattern given in Example 1, the rule

occurs in Πout P3 . Eventually, the Datalog¬s query QP is defined as (ΠP , ansP ), were ΠP = (Πbgp P ∪Πopr P ∪Πout P ).

Let us now explain how the answer to a graph pattern P over an RDF graph G, denoted JPKG, can be obtained from QP (DG). Consider an atom a = ansP (t1, . . . , tmP ), where (t1, . . . , tmP ) ∈ QP (DG). By construction, in Πout P there exists an atom ansP (X1, . . . ,XmP ) that contains only variables (and not the constant ⋆). The mapping µa,P corresponding to a given P is defined as follows: for each i ∈ [1,mP ], if ti ̸= ⋆, then Xi → ti belongs to µa,P , and nothing else occurs in µa,P . Moreover,

are the mappings corresponding to the answers of QP over DG. As shown in [Arenas et al., 2014], JPKG = JQP (DG)K.

3.2 SPARQL Entailment Regime

We now show how the above translation can be extended in order to translate every SPARQL query under OWL 2 direct semantics entailment regime over OWL 2 QL ontologies into a Datalog∃,¬s,⊥ query. We first demonstrate how OWL 2 QL ontologies are stored as RDF graphs. Notice that in the specification of OWL 2, it is defined a standard syntax to represent OWL 2 ontologies as RDF triples. However, for brevity, we use the simplified syntax of [Arenas et al., 2014], having in mind that the approach described below can be adapted to the standard syntax. The vocabulary of an OWL 2 QL ontology consists of unary and binary predicates, called classes and properties, respectively. A basic property is either p or p-, where p is a property. A basic class is either c or ∃p, where c is a class and p a property. To represent an OWL 2 QL ontology, we first include some triples to indicate the classes and the properties in the ontology. For every class c we have the triple (c, rdf:type, owl:Class), asserting that c is of type class. For every property p we have the following triples:

(p, rdf:type, owl:Prop) (p, owl:inv, p-) (p-, rdf:type, owl:Prop) (p-, owl:inv, p) (∃p, owl:rest, p) (∃p, rdf:type, owl:Class) (∃p-, owl:rest, p-) (∃p-, rdf:type, owl:Class).

As said, the notation used above is a simplified version of the notation used in OWL 2. In particular, owl:Prop, owl:inv and owl:rest correspond to the keywords owl:ObjectProperty, owl:inverseOf and owl:Restriction, respectively. Note also that a triple such as (∃p, owl:rest, p) is represented by means of several triples in OWL 2.

The axioms in an OWL 2 QL ontology are represented as follows. (c1, rdfs:sc, c2) indicates that the basic class c1 is a subclass of the basic class c2, while (p1, rdfs:sp, p2) indicates that the basic property p1 is a subproperty of the basic property p2. To indicate that two basic classes c1 and c2 are disjoint we use (c1, owl:disj, c2). As above, we employ a simplified notation; in fact, rdfs:sc, rdfs:sp and owl:disj correspond to the keywords rdfs:subClassOf, rdfs:subPropertyOf and owl:disjointWith, respectively. Note that OWL 2 QL allows for the use of qualified existential quantification in the right-hand side of inclusion assertions, which is not captured by the above encoding. However, such kind of axioms can be simulated in an OWL 2 QL ontology through the use of unqualified existential quantification, auxiliary roles, and inclusions between roles.

The membership assertions in an OWL 2 QL ontology are represented as follows. The triple (a, rdf:type, c) indicates that the constant a belongs to the basic class c, while the triple (a1, p, a2) asserts that the constant a1 is related to the constant a2 via the property p. In the sequel, we say that an RDF graph G represents an OWL 2 QL ontology if there exists an OWL 2 QL ontology O such that, after the translation of O into RDF we obtain G.

Consider now a graph pattern P, and an RDF graph G that represents an OWL 2 QL ontology. In what follows, we present the construction of the Datalog∃,¬s,⊥ query QCP such that the answer to P over G under the OWL 2 direct semantics entailment regime as defined in [Glimm and Ogbuji, 2013], denoted JPKCG , coincides with JQCP (DG)K. Notice that the superscript C is used to indicate that the active domain semantics is adopted. First, we give the crucial programΠOWL2QL, that is, the fixed Datalog∃,¬s,⊥ program that encodes the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies. This program contains three rules that store in a predicate dom(·) all the constant occurring in G:

It also contains some Datalog rules that store the different elements in the ontology:

triple(X, rdf:type, Y ) → type(X, Y ) triple(X, rdfs:sp, Y ) → sp(X, Y ) triple(X, owl:inv, Y ) → inv(X, Y ) triple(X, owl:rest, Y ) → rest(X, Y ) triple(X, rdfs:sc, Y ) → sc(X, Y ) triple(X, owl:disj, Y ) → disj (X, Y ) triple(X, Y,Z) → triple1(X, Y,Z).

The purpose of the last rule is to guarantee that in the predicate triple are stored only constants occurring in G and not nulls. As we shall see, ΠOWL2QL may generate a triple that contains a null z. Therefore, if such a triple is stored in the predicate triple, and not in the auxiliary predicate triple1, we will conclude that dom(z) holds, which violates the intended meaning of the dom predicate. Moreover, ΠOWL2QL contains the following rules to reason about properties:

the following rules to reason about classes:

and the following rule for disjointness constraints:

Finally, ΠOWL2QL contains the following rules to reason about membership assertions:

Having the program ΠOWL2QL in place, the query QCP is defined as (ΠOWL2QL ∪ ΠCP , ansP ), where ΠCP is obtained from ΠP , as defined in Section 3.1, by applying the following modification: for each rule ρ ∈ Πbgp P (recall that Πbgp P is the part of ΠP that encodes the basic graph patterns of P), add in the body of ρ the atom dom(X), for each variable X occurring in ρ, and replace each occurrence of the predicate triple by triple1. The new dom-atoms enforce the constraint that every variable and blank node in P can only take a value from G. As shown in [Arenas et al., 2014], JPKCG = JQCP (DG)K.

3.3 Dropping the Active Domain Restriction

As shown by the following example, the active domain restriction forces the user to encode part of the reasoning in the query, which leads to unnatural and complex queries.

Example 2 Consider the OWL 2 QL ontology O which states that Tom is a person and each person has father, and let G be the RDF graph that represents O. Assume that we want to retrieve the elements of G that have a father. One may be tempted to claim that this query can be expressed via the graph pattern P = (?X, father,B), where B is a blank node. However, JPKCG = ∅ since there are no elements a, b in G such that the triple (a, father, b) is implied by the ontology. To obtain the expected answer, we have to consider the graph pattern (?X, rdf:type, ∃father), which means that we are forced to implicitly encode the fact that the triple (Tom, rdf:type, ∃father) is inferred by the ontology.

As already discussed in [Arenas et al., 2014], the solution to the above problem is to relax the semantics JPKCG in such a way that blank nodes are treated as existentially quantified variables that are not forced to take only values in the RDF graph. Indeed, after this relaxation, the answer to the the graph pattern P = (?X, father, B) over the RDF graph G that represents the ontology O in Example 2 will be Tom since a triple (Tom, father, z), where z ∈ N, is inferred by O. The more general semantics JPKC,N G has been proposed in [Arenas et al., 2014]. Given a graph pattern P and an RDF graph G that represents an OWL 2 QL ontology, JPKC,N G is defined as JQC,N P (DG)K, whereQC,N P = (ΠOWL2QL∪ΠC,N P , ansP ) with ΠC,N P be the program obtained fromΠCP as follows: assuming that Πbgp P is the part of ΠCP that encodes the basic graph patterns, for each rule ρ ∈ Πbgp P , eliminate the atoms of the form dom(X), where X is a variable that appears in the body but not in the head of ρ, which means that X represents a blank node. The superscript C, N indicates that blank nodes may be assigned null values of N.

In view of the fact that the problem of querying OWL 2 QL ontologies using conjunctive queries with inequalities, without restricting the inequalities to compare only database constants, is undecidable [Guti´errez-Basulto et al., 2013], and since SPARQL allows for inequalities, one may think that the more general semantics JPKC,N G leads to undecidability. This is not true since the OWL 2 direct semantics entailment regime is first applied at the level of basic graph patterns, and the results of this step, which is a finite database that contains only constants, are combined using the standard SPARQL operators. Since in basic graph patterns we do not have inequalities, the above undecidability result cannot be applied.

4 FromModular to Standard Queries

Recall that the present work aims at proposing TriQ-Lite 1.0, the new version of TriQ-Lite, that enjoys all crucial desiderata analyzed in Section 1. Towards this direction, we are going to define a standard (non-composite) Datalog∃,¬s,⊥-based formalism that is powerful enough to express the queries QCP and QC,N P , incorporates Datalog¬s , and at the same time its query evaluation problem is tractable in data complexity.

Let us recall that TriQ-Lite, proposed in [Arenas et al., 2014], although is tractable and powerful enough for expressing QCP and QC,N P , it is a non-plain language, where the user can place different parts of the query in different modules, while its semantics is defined in a modular way. For example, the query QCP = (ΠOWL2QL ∪ ΠCP , ansP ) can be expressed (following the syntax of [Arenas et al., 2014]) as

where ΠOWL2QL is the fixed Datalog∃,¬s,⊥ program that encodes the OWL 2 direct semantics entailment regime as discussed in Section 3.2, while {Πbgp P ,Πopr P ,Πout P } forms a partition of ΠCP , where the first program consists of the rules that represent the basic graph patterns, the second one contains the rules that encode the SPARQL operators, and the last one consists of the rules that define the predicate ansP . The semantics of such a query over a database DG is defined in a modular way. First, consider the instance

where, for each rule ρ : ϕ(X,Y) → pρ(X) of Πbgp P , qρ is the conjunctive query ∃Yϕ(X,Y). Then, the semantics of MQ CP over DG is defined as

where, for each ρ ∈ Πout P , qρ is defined as above.

It is evident that TriQ-Lite significantly deviates from the standard way of defining Datalog-like query languages, and this makes the comprehensibility of its syntax and semantics a difficult task. Let us clarify that a single module of TriQ-Lite is not powerful enough for expressing QCP and QC,N P . This is a strong indication that the modular nature of this langauge only helps to gain the missing expressive power for capturing SPARQL queries under the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies, by treating the various parts of the same query in a different way.

The crucial question that comes up is how TriQ-Lite can be transformed into a standard Datalog-like query language, which fulfills all the aforementioned desiderata. The rest of this section is devoted to give an answer to this question by introducing TriQ-Lite 1.0.

4.1 A Standard Datalog∃,¬s,⊥ Language

After a careful syntactic analysis of the query programs of QCP andQC,N P , for an arbitrary graph pattern P, we identified an interesting property regarding the dangerous variables of each rule that was decisive for the definition of our language. From previous studies, we know that the rule-variables that must be tamed, in order to guarantee a good computational behavior, are the body-variables that can be associated with null values, and at the same time are propagated to the rulehead [Baget et al., 2011; Cal`ı et al., 2013]; these are the variables that we dubbed dangerous. The query programs of QCP and QC,N P enjoy the following property: for each rule ρ, its dangerous variables are isolated in a single atom of B +(ρ), and they can interact with the rest of the rule-body only via

(b) Indirect interaction (↷) (a) Direct interaction (→) harmless variables, i.e., variables that cannot be associated with null values. Another key observation is that the involved negation, apart from being stratified, is also grounded, i.e., it is used with predicates that can only store constant values, but not nulls. Let us now formalize the above key properties. Technical Definitions. A position p[i] identifies the i-th attribute of a predicate p. Given a Datalog∃,¬s program Π, the set of affected positions of sch(Π), denoted affected(Π), is inductively defined as follows: (1) if there exists ρ ∈ Π such that at position π an existentially quantified variable occurs, then π ∈ affected(Π); and (2) if there exists ρ ∈ Π, a variable X in B +(ρ) only at positions of affected(Π), and X appears in H(ρ) at position π, then π ∈ affected(Π). Let nonaffected(Π) be the nonaffected positions of sch(Π). For a rule ρ ∈ Π, a variable X ∈ var(B(ρ)) is called harmless (w.r.t. Π) if at least one occurrence of X appears in B +(ρ) at a position of nonaffected(Π); let harmless(ρ) be the set of variables of var(B(ρ)) that are harmless. A variable X ∈ var(B(ρ)) is dangerous (w.r.t. Π) if X ̸∈ harmless(ρ) and X ∈ var(H(ρ)); let dangerous(ρ) be the set of variables of var(B(ρ)) that are dangerous. Π is a Datalog∃,¬sg program ("sg" stands for stratified and ground) if, for each rule ρ ∈ Π, for each atom p(t1, . . . , tn) ∈ B -(ρ), and for each i ∈ [1, n], either (ti ∈ C) or (ti ∈ harmless(ρ)).

Wardedness. We proceed to formalize the aforementioned property regarding the dangerous variables of a rule. Consider a Datalog∃,¬sg program Π and a rule ρ ∈ Π. A set of variables X ⊆ var(B(ρ)) is called warded (w.r.t. Π) if, either X = ∅, or there exists a ∈ B +(ρ), called the ward (of X relative to ρ), such that: (1) var(a) ⊇ X; and (2) (var(a) ∩ var(B(ρ) \ {a})) ⊆ harmless(ρ). Intuitively, the ward isolates the harmful variables of X from the rest of the rule-body. Having the notion of the ward in place, it is now straightforward to formalize the intuitive idea of isolating the dangerous variables of a rule.

Definition 1 A Datalog∃,¬sg,⊥ program Π is warded if, for each ρ ∈ ex(Π), dangerous(ρ) is warded. A Datalog∃,¬sg,⊥ query (Π, p) is warded if Π is warded. A TriQ-Lite 1.0 query is a Datalog∃,¬sg,⊥ query that is warded.

The body of a rule occurring in a warded program can be graphically illustrated (via its hypergraph) as shown in Figure 1, where the shaded part consists only of harmless variables, while the dashed area represents an arbitrary (possibly cyclic) hypergraph. For every graph pattern P, both QCP and QC,N P are warded Datalog∃,¬sg,⊥ queries, and thus:

Theorem 2 Every SPARQL query under the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies (with or without the active domain semantics) can be expressed as a TriQ-Lite 1.0 query.

Warded Datalog∃,¬sg,⊥, and therefore TriQ-Lite 1.0, can be conceived as a refined version of a more expressive formalism called weakly-frontier-guarded Datalog∃,¬sg,⊥ [Baget et al., 2011]. The latter requires the existence of a body-atom, called guard, that contains (or guards) all the dangerous variables. Thus, wardedness is a restriction of weak-frontierguardedness, where the interface between the guard and the rest of the rule-body contains only harmless variables.

4.2 TriQ-Lite 1.0: A Tractable Language

Interestingly, the mild syntactic restriction applied on weakly-frontier-guarded Datalog∃,¬sg,⊥ has a huge impact on the data complexity, namely it decreases from EXPTIME to PTIME. This implies that our formalism achieves the right balance between expressivity and complexity:

Theorem 3 Query evaluation for TriQ-Lite 1.0 is PTIMEcomplete in data complexity.

The lower bound immediately follows from the fact that plain Datalog is PTIME-hard [Dantsin et al., 2001]. The nontrivial part is to establish the PTIME upper bound. Given a database D, and a TriQ-Lite 1.0 query Q = (Π, p), we first need to check whether Π(D) is defined. This task can be reduced to query evaluation for warded Datalog∃,¬sg . Thus, it suffices to show that the latter is in PTIME. Fix a database D, and a warded Datalog∃,¬sg query Q = (Π, p). Our goal is to construct in polynomial time a database DL and a linear Datalog∃ query QL = (ΠL, p) such that Q(D) = QL(DL), while the arity of the predicates of sch(ΠL) does not depend on D. Linear Datalog∃ rules are rules with just one body-atom. Query evaluation for linear Datalog∃ is polynomial in the number of rules and the number of predicates occurring in the query program, and exponential in the maximum arity over all predicates in the query program [Gottlob et al., 2014]. Thus, our reduction shows that query evaluation for warded Datalog∃,¬sg is in PTIME in data complexity. Moreover, query evaluation for linear Datalog∃ can be effectively reduced to query evaluation for unions of conjunctive queries [Gottlob et al., 2014], and thus our reduction shows that query evaluation for warded Datalog∃,¬sg is feasible by the use of standard RDBMSs. Notice that a similar approach has been followed in [Arenas et al., 2014] to show that query evaluation for TriQ-Lite is in PTIME in data complexity. However, as we shall discuss below, there is a fundamental difference between TriQ-Lite and warded Datalog∃,¬sg that makes the definition of the above reduction even more challenging.

The reduction to query evaluation for linear Datalog∃ consists of the following three steps: (1) Normalization: we normalize Π so that each rule is head-ground, i.e., each term occurring in the head is either a constant or a harmless variable, or semi-body-ground, i.e., there exists at most one body-atom that contains a harmful variable; (2) Eliminate Negation: we construct a database D+, and a negation-free program Π+ such that Q(D) = Q+(D+), where Q+ = (Π+, p). Since the negation is stratified and grounded, Π+ can be computed from Π in the standard way, by replacing each negative atom

¬s(t) with ¯ s(t), where the extension of ¯ s in D+ is the complement of s w.r.t. the ground semantics of Π over D, that is, the instance Π(D)↓ = {a ∈ Π(D) | dom(a) ⊂ C}; and (3) Linearization of Q+: We define DL = Π+(D+)↓, and we transform Π+ into ΠL. The program Π+ can be partitioned into {Π+h ,Π+b }, where Π+h consists of all the headground rules of Π+, while Π+b = (Π+ \ Π+h ) of semi-bodyground rules. The rules of Π+h can be safely ignored since only ground atoms can be inferred from them, which are already in DL. Finally, ΠL is obtained from Π+b by replacing each non-linear rule ρ, where a is the ward of dangerous(ρ), with the linear rules {h(ρ) → h(head(ρ))h∈Hρ , where Hρ are all the homomorphisms that map (body(ρ) \ {a}) to DL.

Ground Semantics. It remains to show that the ground semantics can be computed in polynomial time. Fix a database D, and a warded Datalog∃ query Q = (Π, p). We show that:

Proposition 4 The instance Π(D)↓ can be constructed in polynomial time w.r.t. D.

A similar result can be found in [Arenas et al., 2014] for constant-join Datalog∃ programs, that is, programs consisting of rules that can join only harmless variables, which are underlying TriQ-Lite. However, warded Datalog∃ programs can join harmfull variables, and this is precisely the fundamental difference between constant-join Datalog∃ and warded Datalog∃ that makes our task technically more challenging. To establish Proposition 4, it suffices to show that the problem of deciding whether a ground atom a belongs to Π(D) is feasible in polynomial time w.r.t. D. To this end, we significantly extend the alternating procedure Proof, proposed in [Arenas et al., 2014], for constant-join Datalog∃ . Let us first introduce the notion of the proof-tree via an example.

Example 3 Consider the warded Datalog∃ program Π′ :

ρ1 : p(X, Y ) → ∃Z p(Y,Z) ρ2 : p(X, Y ) → ∃Z s(Y,Z)

ρ3 : p(X, Y ), s(Y,Z) → t(X),

the database D′ = {p(a, b)}, and the atom a = t(b). A proof of a w.r.t. D′ and Π′ is depicted in Figure 2(a), while a proof-tree of a w.r.t. D′ and Π′ is given in Figure 2(b). Having a proof of a, we can construct a proof-tree of a by, roughly speaking, reversing the edges and unfolding the obtained graph into a tree by repeating some nodes. On the other hand, having a proof-tree of a, we can construct a proof of a by reversing the edges and collapsing some nodes.

Clearly, to establish Proposition 4, it suffices to show that the problem of deciding whether a proof-tree exists is feasible in polynomial time. Proof(a, D, Π) constructs a proof-tree P of a w.r.t. D and Π (if it exists) by constructing the various branches of P in parallel universal computations. The difficulty during this alternating procedure, is to guarantee that the branches constructed in parallel computations are compatible so that, after their merging, a valid proof-tree of a w.r.t. D and Π is obtained. In fact, we need to ensure that the "fresh" null values occurring in more than one branch of P (see the null z1 in the proof-tree of Figure 2(b)), represent the same term in Π(D). An abstract description of our algorithm follows.

Proof(a,D,Π) starts from a, and applies appropriate resolution steps until the database D is reached. In particular, it consists of the following steps:

• A rule ρ ∈ Π such that H(ρ) and a unify is guessed. After resolving a with ρ we get the set of atoms θρ,a(B(ρ)), where θρ,a is the most general unifier for H(ρ) and a. Notice that θρ,a maps the variables occurring in B(ρ) but not in H(ρ) into "fresh" nulls.
• θρ,a(B(ρ)) is partitioned into {S1, . . . , Sn} so that, for each null z occurring in θρ,a(B(ρ)), there exists exactly one i ∈ [1, n] such that Si contains z, and there is no partition of θρ,a(B(ρ)) with n+1 elements that satisfies the latter condition, i.e., each element of {S1, . . . , Sn} is ⊆-minimal. The intention underlying the above partition is to keep together the nulls that appear in more than one branch of the proof-tree under construction, until enough information regarding their generation, which will be used to ensure the compatibility among the various branches, is known.
• Universally select each set S ∈ {S1, . . . , Sn} and prove it, which means that each atom of S must be proved. More precisely, for each atom b ∈ S, a rule ρb ∈ Π is guessed such that H(ρb) and b unify, and the set of atoms θρb,b(B(ρb)) is obtained.
• With S = {b1 , . . . , bm}, ⋃i∈[1,m] θρbi ,bi (B(ρbi )) is partitioned as above, and each component of the partition is proved recursively in a parallel universal computation.

During the execution of the above procedure, the first time that a null z is lost after resolving an atom b (that contains z) with a rule ρ ∈ Π, which means that z is associated with an existentially quantified variable in H(ρ), we conclude that θρ,b(H(ρ)) represents the atomwhere z is invented. It is vital to ensure that the atoms where z is invented in parallel computations are isomorphic to θρ,b(H(ρ)). This can be achieved by carrying together with the component that contains z the crucial atom θρ,b(H(ρ)). Although the above is only a highlevel description of our algorithm, it gives enough evidence for its soundness. By exploiting wardedness, we can show that at each step of the computation of Proof(a,D,Π) we need logarithmic space w.r.t. D. Since ALOGSPACE coincides with PTIME, Proposition 4 follows.

5 ProgramExpressive Power

One may claim that Datalog¬s and TriQ-Lite 1.0, or, equivalently, warded Datalog∃,¬sg,⊥, are formalisms with the same expressive power, and raise the following question: is warded Datalog∃,¬sg,⊥, and in particular the feature of existential quantification, necessary for our purposes? This question is directly related to our fifth desideratum, i.e., the absolute decoupling between the reasoning process, and the process of defining the actual query. In fact, warded Datalog∃,¬sg,⊥ fulfills the above desideratum since is able to encode the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies via a fixed program, namely ΠOWL2QL, that does not depend on any graph pattern, and also is able to express every SPARQL query when the active domain semantics is dropped. However, the above desideratum, and in particular the encoding of the OWL 2 direct semantics entailment regime via a fixed program, cannot be achieved with Datalog¬s [Arenas et al., 2014]. Thus, the answer to the above question is that the existential quantification is vital in order to accomplish the decoupling between the reasoning part and the actual query.

The classical notion of expressive power does not capture the above key difference between Datalog¬s and warded Datalog∃,¬sg,⊥. Interestingly, this is captured by the recent notion of program expressive power [Arenas et al., 2014]. Consider a query language L and a program Π. The program expressive power of Π relative to L, denoted PepL[Π], is the of triples (D,Λ, p(t)) such that (Π ∪ Λ) ∈ L, the predicate p occurs only in the head of the rules of Λ (i.e., the rules of Λ act as the output rules of (Π ∪ Λ)), and t ∈ Q(D), where Q = (Π ∪ Λ, p). Roughly, PepL[Π] encodes that set of atoms that can be inferred from a database D via a query Q ∈ L, where Π consists of the rules of Q other than the output rules. The program expressive power of L is now naturally defined as Pep[L] = {PepL[Π] | Π ∈ L}. We say that a language L is more expressive than L′ w.r.t. the program expressive power, written as L′ ≺Pep L, if Pep[L′ ] ⊆ Pep[L] and Pep[L] ̸⊆ Pep[L′ ]. We can show that:

Theorem 5 Datalog¬s ≺Pep TriQ-Lite 1.0.

The above result formally explains the key difference between Datalog¬s and TriQ-Lite 1.0, and the importance of the existential quantification in rule-heads.

6 Model-theoretic Justification of Wardedness

The goal of this section is to justify the necessity for defining a new formalism instead of exploiting an existing one. To this end, we are going to establish, via a model-theoretic argument, that existing Datalog-based formalisms, which seem suitable for our purposes, are not able to encode the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies via a fixed program. The only previously known plain formalisms that are powerful enough for our purposes are weakly-guarded Datalog∃,¬sg,⊥ [Cal`ı et al., 2013] and weakly-frontier-guarded Datalog∃,¬sg,⊥ [Baget et al., 2011]. However, these two formalisms are EXPTIME-complete in data complexity, and thus inherently intractable. One may suggest to exploit existing tractable subclasses of the above formalisms. We show that such subclasses, and in particular (frontier-)guarded Datalog∃,¬sg,⊥, are not powerful enough for encoding the OWL 2 direct semantics entailment regime (no matter whether the active domain semantics is adopted or not) via a fixed program. This justifies the necessity for introducing warded Datalog∃,¬sg,⊥. We first expose, via an example, a crucial model-theoretic property that a language must fulfill in order to be able to encode the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies via a fixed program.

Example 4 Consider the basic classes c0, . . . , cn, and the basic property p, and let O be the OWL 2 QL ontology that encodes the following: the constant a belongs to c0, c0 is a subclass of ∃p, ∃p- is a subclass of c1, and ci is a subclass of ci+1, for each i ∈ [1, n - 1]. It is not difficult to verify that, after encoding O as an RDF graph G, we infer the triples (z, rdf:type, ci), for each i ∈ [1, n], where z is a "fresh" null. Observe that the null value z is connected, via joint occurrences in triples, to all the constants in G that represent classes. In other words, the number of constants that are connected to z depends on the RDF graph.

It can be seen that a Datalog∃,¬s,⊥ language is suitable for our purposes only if it allows us to connect an invented null, using a fixed program, with an unbounded number of constants, or, in other words, if it enjoys the so-called unbounded ground-connection property. The ground-connection of a null z to an instance I, denoted gc(z, I), is the set of constants {c ∈ C | there exists a ∈ I such that {c, z} ⊆ dom(a)}, that is, all the constants that jointly appear with z in an atom of I. A family of databases is a sequence D1 ,D2 , . . ., where each Dn is a database such that |dom(Dn )| = n. The formal definition of the above key property follows:

Definition 6 A Datalog∃,¬s,⊥ language C enjoys the unbounded ground-connection property (UGCP), if there exists a family of databases D1 , D2 , . . ., and a program Π in C such that, for each n > 0, Π(Dn ) is defined, and |gc(z,Π(Dn ))| depends on n, for at least one null z in Π(Dn ).

Our formalism enjoys the above model-theoretic property; this can be shown by exploiting Example 4. On the other hand, given a (frontier-)guarded Datalog∃,¬sg,⊥ program Π, for every database D such that Π(D) is defined, and for every null z in Π(D), gc(z,Π(D)) consists of the constants that appear in the atom of Π(D) in which z was generated, i.e., |gc(z,Π(D))| ⩽ ω, where ω is the maximum arity over all predicates of sch(Π), and thus does not depend on |dom(D)|. From the above discussion, we get the following:

Proposition 7 It holds that, (1) Warded Datalog∃,¬sg,⊥ enjoys the UGCP; and (2) (Frontier-)guarded Datalog∃,¬sg,⊥ does not enjoy the UGCP.

To sum up, all the known tractable subclasses of weakly(frontier-)guarded Datalog∃,¬sg,⊥ do not enjoy the UGCP, and thus they are not powerful enough for encoding the OWL 2 direct semantics entailment regime over OWL 2 QL ontologies via a fixed program. This justifies the necessity for defining warded Datalog∃,¬sg,⊥, the Datalog-based language underlying TriQ-Lite 1.0.

7 Complexity-theoretic Justification of Wardedness

Let us now substantiate the design choices made in the definition of TriQ-Lite 1.0. We show that mild extensions of warded Datalog∃ immediately lead to languages that are EXPTIME-hard in data complexity, and thus provably intractable.

This is a strong sign that wardedness lies at the boundaries of data tractability. Recall that the key idea underlying wardedness is to collect the dangerous variables of a rule in a single body-atom, and force them to interact with the rest of the rulebody only via harmless variables. Thus, the apparent way to extend warded Datalog∃ is to allow the dangerous variables to interact with the rest of the body via harmful ones.

Towards this direction, the mildest relaxation of wardedness is to allow the existence of an atom (other then the ward) in the body of a rule, which contains only harmless variables apart from one harmful variable V that is either dangerous or not. If V is dangerous, then we say that the interaction of the dangerous variables with the rest of the body is direct, and we get the formalism →-warded Datalog∃ ; otherwise, we say that their interaction is indirect, and we get ↷- warded Datalog∃ ("→" refers to the direct interaction, while "↷" refers to the indirect interaction). The body of a rule occurring in a →-warded (resp., ↷-warded) Datalog∃ program is graphically illustrated in Figure 3(a) (resp., 3(b)). Figures 1 and 3 confirm that the above proposed formalisms are obtained by minor syntactic extensions of warded Datalog∃ . However, as we show below, these minor extensions have a significant impact on the data complexity of query evaluation.

Proposition 8 Query evaluation for ⋆-warded Datalog∃ , where ⋆ ∈ {→,↷}, is EXPTIME-hard in data complexity.

The above result is shown by simulating the behavior of an alternating polynomial space Turing machine M via a fixed ⋆-warded Datalog∃ query, where ⋆ ∈ {→, ↷}.

8 FutureWork

Our next step is to experimentally evaluate the employed procedures. To this end, a challenging task is to design a practical algorithm for computing the ground semantics of a program. This will allows us to productively exploit the fact that query evaluation for TriQ-Lite 1.0 can be reduced to query evaluation for linear Datalog∃ , which in turn implies that standard database technology and techniques can be employed.

Acknowledgements. G. Gottlob was supported by the EPSRC Programme Grant EP/M025268/ "VADA: Value Added Data Systems - Principles and Architecture". A. Pieris was supported by the Austrian Science Fund (FWF): P25207-N23 and Y698.