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 Web Ontology 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 [1, 3, 9, 15], while recursive definitions are a key feature for graph query languages [5, 14]. 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 [10, 12], 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 [14]. 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 [2]. This language is based on Datalog9;: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 Datalog9;:s;? that is underlying TriQ-Lite, while each pair ( i; i+1) is bridged via a set Qi of conjunctive queries.
? This short paper is based on the recent works [
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 [
Notably, TriQ-Lite provides the definition of the more natural entailment regime without the active domain restriction. This is certainly an additional desideratum: 5. Reasoning-Query Decoupling: the entailment regime without the active domain restriction must be definable in order to decouple 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 Datalog9;: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 [
Desideratum How it is Achieved Plainness Standard Datalog-like language Reasoning capabilities 9-quantification and ? in rule-heads Recursive definitions Incorporate full Datalog:s Efficiency Reduction to UCQ evaluation Reasoning-Query Expressive joins in rule-bodies, and decoupling 9-quantification in rule-heads challenge was to define a Datalog language that achieves the right balance between expressivity and complexity.
Contribution. We propose a new syntactic paradigm, which is underlying TriQ-Lite 1:0, called wardedness, that can be informally described as follows: all the dangerous bodyvariables, 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. For example, the program , where the dangerous variables are the variables marked by tilde, triple(X~ ; U; Y~ ); inv (U; V ) ! triple(Y~ ; V; X~ )
type(X~ ; Y ); rest (Y; U ) ! 9Z triple(X~ ; U; Z) triple(X~ ; U; Y ); rest (Z; U ) ! type(X~ ; Z) is warded; for each rule, all the tilde variables occur in a single body-atom a, while all the other variables of a are harmless.
Our technical results can be summarized as follows (for details see [
In fact, we show that very mild extensions lead to EXPTIME-hardness.
Let us say that warded Datalog9;: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.
Acknowledgements. Arenas is funded by the Millenium Nucleus Center for Semantic Web Research under grant NC120004. Gottlob is supported by the EPSRC Programme Grant EP/M025268/ “VADA: Value Added Data Systems – Principles and Architecture”. Pieris is supported by the Austrian Science Fund (FWF), projects P25207-N23 and Y698, and Vienna Science and Technology Fund (WWTF), project ICT12-015.