Temporal and Spatial OBDA with Many-Dimensional Halpern-Shoham Logic

1 Introduction

The aim of ontology-based data access (OBDA) is to streamline the process of gathering information from various data sources by providing the user with a convenient high-level view of the data and thereby making IT middlemen redundant [Poggi et al., 2008]. Typical application scenarios for OBDA include querying databases with multiple tables and complex schemas [Kharlamov et al., 2015], in particular, with sensor and event data [Kharlamov et al., 2014]. Incidentally, these and other real-world use cases reveal that standard OBDA ontology and query languages, designed by the description logic, datalog and Semantic Web communities, do not provide any natural means to deal with numerical information such as historical, geospatial or sensor data.

There have been a number of attempts to add temporal or spatial constructs to conjunctive or SPARQL queries while keeping intact the standard OBDA ontology language OWL2QL. In the temporal case, this approach might seem to be justified because ontology axioms are often assumed to hold at all times; see, e.g., [Guti´errez-Basulto and Klarman, 2012; Baader, Borgwardt, and Lippmann, 2013; Borgwardt, Lippmann, and Thost, 2013; ¨Ozcep et al., 2013; Klarman and Meyer, 2014; ¨Ozc¸ep and M¨oller, 2014]. In the spatial ontology languages designed for OBDA [ ¨Ozc¸ep and M¨oller, 2012; Eiter, Krennwallner, and Schneider, 2013], domain individuals are associated with their spatial extensions via special functions [Lutz and Milicic, 2007]. However, axioms saying that those extensions stand in certain spatial relations easily ruin the main feature of OWL 2 QL-first-order rewritability of conjunctive queries (CQs) [ ¨Ozc¸ep and M¨oller, 2012].

The restriction of temporal and spatial constructs only to queries places the burden of using them on the user rather than on the ontology engineer, and thereby contradicts the spirit of the OBDA paradigm. First temporal extensions of OWL2QL and other logics in the DL-Lite family that enjoy FO-rewritability were proposed by Artale et al. [2013; 2015b]. These formalisms feature LTL temporal operators over Z on concepts and roles. One potential issue with using them in practice could be the complexity of FO-rewritings caused by the point-based temporal operators.

In this paper, we suggest a different approach to the design of ontology languages for OBDA with numerical data. We model such data by closed intervals [x↪ y] of appropriate linear orders, say (Z↪ ) or (R↪ <), which can represent periods of time (as in temporal databases), temperature or altitude ranges, the length and width of rectangular (approximations of) spatial regions, etc. Thus, our 'spatio-temporal' entities are hyperrectangles in the n-dimensional Cartesian products X = Qn`=1 X` of linear orders X` = (X`↪✁`). Relation algebras over such entities are well-known in temporal and spatial knowledge representation: Allen's [1983] interval algebra, the rectangle/block algebra RA [Balbiani, Condotta, and del Cerro, 2002], cardinal direction calculus [Goyal and Egenhofer, 2001]; see also [Navarrete et al., 2013; Cohn et al., 2014; Zhang and Renz, 2014] and references therein.

An expressive and elegant formalism for reasoning about intervals was suggested by Halpern and Shoham [1991] who used 'modal' operators of the form [R] and hRi, where R is one of Allen's interval relations. The full Boolean modal logic HS with these operators is undecidable over any non-trivial linear orders [Halpern and Shoham, 1991; Gabbay et al., 2003; Bresolin et al., 2014]. However, it has recently been shown that the Horn fragment of HS with the operators [R] over (Z↪) and the reflexive semantics of the interval relations turns out to be tractable [Artale et al., 2015a].

Here we define an ontology language datalogHS 2n whose programs consist of standard datalog rules with body atoms possibly prefixed by operators hRi` or [R]` and head atoms by [R]` over X` = (Z↪ ) or X` = (R↪ <). The atoms represent standard database relations that can hold at some hyperrectangles of X, and the rules are assumed to hold globally at all of them. Thus, a typical datalogHS 2n rule says that P(t) holds at a hyperrectangle ◆ if Q1(t1)↪ ▷ ▷ ▷ ↪Qk(tk) hold at some (or all) hyperrectangles ◆i such that Ri(◆↪ ◆i), where Ri is one of the basic relations of the n-dimensional block algebra RA. Sets of datalogHS 2n rules can define complex spatial relations such as, for example, P holds at ◆ if the Qi hold at some ◆i with ◆ = T ◆i (or with ◆ being the smallest hyperrectangle containing all the ◆i). As a query language we suggest conjunctive queries (CQs) with atoms of the form P(t)@⌧ and R`(⌧↪ ⌧ 0 ), where t and ⌧ are tuples of individual and interval terms, respectively, and R` an interval relation over X`.

The main result of the paper is that, given a CQ q(v↪ χ) and a datalogHS 2n program⇧, one can construct in linear time a standard datalog program⇧ with a goal G(v↪χ) such that, for any data instance D, a tuple (c↪ δ) is a certain answer to q(v↪χ) and ⇧ over D iff ⇧ ↪D ♣= G(c↪ δ). To obtain this datalog rewritability result, we investigate the structure of the minimal model of (⇧↪ D) based on the space X and show that one can always construct a (non-standard) finite Kripke model of (⇧↪ D) that has polynomially-many worlds in the size of D and gives all certain answers to any CQ. On the other hand, we show that query evaluation for propositional datalogHS 21 programs is P-hard for data complexity. Note that since satisfiability of propositional datalogHS 2n programs is decidable in polynomial time, we obtain a tractable fragment of the RCC8 analogue of the Halpern-Shoham logic HS interpreted over hyperrectangles of Rn , which is known to be not recursively enumerable [Lutz and Wolter, 2006].

We tested the expressivity and efficiency of datalogHS 2n on two real-world data sets: 1D historical data about the Italian Public Administration, and 2D (time ⇥ temperature) weather data. Our datalogHS 2n programs defined complex 'spatiotemporal' predicates, which were then used in simple user queries. Three off-the-shelf datalog tools demonstrated reasonable scalability on the resulting datalog rewritings.

2 DatalogHS 2n

Let X = (X↪ ✁) be either (Z↪ ) or (R↪ <). Denote by int(X) the set of closed intervals [x1↪ x2] with x1 ✁x2. We define the Allen interval relations A, B, E, D, L, O on int(X) by taking

and denote by ¯A, ¯B, ¯E, ¯D, ¯L, ¯O their inverses. Note that int(Z↪) contains punctual intervals while int(R↪<) does not. All of our results below would hold if we took any other discrete order with  in place of (Z↪ ) and any other dense order in place of (R↪<). However, for (Z↪<) the logic we are about to define would be undecidable [Bresolin et al., 2016].

Fix some n ≥ 1 and a linear order X` = (X`↪✁`) as above, for 1  `  n. A hyperrectangle in the n-dimensional space X = Qn`=1 X` is any n-tuple ◆ = (◆1↪ ▷ ▷ ▷ ↪ ◆n) such that ◆` 2 int(X`), for 1  `  n. The set of hyperrectangles in X is denoted by hyp(X). Given ◆↪  2 hyp(X) and an interval relation R, we write ◆R` if ◆`R` and ◆i = i, for i 6= `.

Syntax of datalogHS 2n . A data instance, D, is a finite set of facts of the form P(c)@◆, where P is an m-ary predicate symbol, c an m-tuple of individual constants, for some m ≥ 0, and ◆ 2 hyp(X). This fact says that P(c) is true at ◆. We denote by ind(D) the set of all individual constants in D, by num`(D) the set of x1↪ x2 2 X` with ◆` = [x1↪ x2], for some ◆ mentioned in D, and by int(D) the set of [x1↪ x2] 2 int(X`) with x1↪ x2 2 num`(D), for 1  `  n.

An individual term, t, is an individual variable, v, or a constant, c. A datalogHS 2n program, ⇧, is a finite set of rules of the form

where k ≥ 1, each Ai is either an inequality t 6= t0 with individual terms t and t0 or defined by the grammar

for an m-ary predicate P and individual terms ti, and A+ does not contain any diamond operators hRi`. As usual, the atoms A1↪ ▷ ▷ ▷ ↪ Ak constitute the body of the rule, while A+ or ? its head. We also impose other standard datalog restrictions on datalogHS 2n programs. However, we cannot allow hRi` in the heads as this would make our logic undecidable.

Semantics of datalogHS 2n . An interpretation, M, is based on a domain ∆ 6= ; (for the individual variables and constants) and the space X. For any m-ary predicate P , m-tuple a from ∆ and ◆ 2 hyp(X), M specifies whether P is true on a at ◆, in which case we write M↪ ◆ ♣= P (a). Let ⌫ be an assignment of elements of ∆ to the individual variables (we adopt the standard name assumption: ⌫(c) = c, for every individual constant c). We then set inductively:

We say that M satisfies ⇧ under ⌫ if, for all ◆ 2 hyp(X) and all rules A A1 ^ · · · ^Ak in ⇧, we have

(as usual M↪ ◆ 6♣=⌫ ?). M is a model of ⇧ and D if it satisfies ⇧ under every assignment, and M↪ ◆ ♣= P(c), for every fact P(c)@◆ in D. ⇧ and D are consistent if they have a model.

Example 1. Denote by hInti the binary modal operator such that AhIntiA0 holds at a hyperrectangle  iff A holds at some ◆, A0 at some ◆0 , and  = ◆ \ ◆0 . One can show that rules such as B AhIntiA0 are expressible as datalogHS 2n programs. For example, for n = 2, there are 132 = 169 different relative positions of two rectangles; see, e.g., [Navarrete et al., 2013, Fig. 4] for an illustration. Those of them where the rectangles have non-empty intersection are encoded by datalogHS 2n rules such as B h¯Ei1h¯Bi2A^ h¯Bi1h¯Ei2A0 for the position on the left-hand side of the picture below:

Ontology-mediated queries. An interval term, ⌧, is either an interval, ◆, or an interval variable, χ. A conjunctive query (CQ) is a formula of the form

where Φ is a conjunction of atoms of two types:

• P(t)@⌧ with t = (t1↪ ▷ ▷ ▷ ↪ tm) and ⌧ = (⌧1↪ ▷ ▷ ▷ ↪ ⌧n),
• R(⌧↪ ⌧ 0 ) with an interval relation R,

and all individual and interval variables in Φ are from v [ v0 and χ [ χ0 , respectively. A datalogHS 2n program ⇧ and a CQ q(v↪χ) constitute an ontology-mediated query (OMQ) Q(v↪ χ) = (⇧↪ q(v↪ χ)).

Example 2. Suppose X = X1 ⇥ X2, where X1 = (Z↪) represents time and X2 = (R↪<) temperature. Imagine that a turbine monitoring system is receiving from sensors a stream of data of the form Blade(ID140)@(◆1↪ ◆2), where ID140 is a blade ID and ◆2 2 int(R↪<) is the observed temperature range during the time interval ◆1 2 int(Z↪). Then the rule

says that the temperature of blade v is rising over a rectangle (◆1↪ ◆2) if Blade(v)@(◆-1 ↪ ◆-2 ) and Blade(v)@(◆+1 ↪ ◆+2 ) hold at some (◆-1 ↪ ◆-2 ) and (◆+1 ↪ ◆+2 ) located as shown below:

To find the blades v and the time intervals χ such that the temperature of v was rising before χ, reaching 1500◦ in χ, and dropping after that, we can use the following CQ q(v↪ χ)

Let Q(v↪χ) = (⇧↪ q(v↪χ)) be an OMQ and D a data instance. A certain answer to Q(v↪χ) over D is any pair (c↪ δ) satisfying the following conditions:

• c ✓ ind(D) and δ ✓ int(D), with ♣v♣ = ♣c♣, ♣χ♣ = ♣δ♣;
• for every model M of ⇧ and D, there is a map h of the individual terms in q to ∆ and the interval terms to S` int(X`) preserving constants and dimensions such that h(v) = c, h(χ) = δ, M↪ h(⌧) ♣= P(h(t)) for every atom P(t)@⌧ in q, and R(h(⌧)↪ h(⌧ 0 )) holds in the corresponding X`, for every atom R(⌧↪ ⌧ 0 ) in q.

We say that a program ⇧ is in normal form if it does not contain occurrences of hRi` and nested [R]`. It is readily seen that any OMQ Q = (⇧↪ q) can be transformed to an OMQ Q0 = (⇧0 ↪ q) with ⇧0 in normal form and of linear size in ♣⇧♣ such that Q and Q0 have the same certain answers over any data instance (in a given signature). For example, the rule S(t) hRi`P (t) ^ Q(t) can be replaced with two rules S(t) P 0 (t) ^Q(t) and [¯R]`P 0 (t) P(t), for a fresh P 0 . We assume all our programs are in normal form.

Our aim now is to show that finding certain answers to an OMQ Q(v↪ χ) over any given D can be reduced to finding answers to a standard datalog query (⇧ ↪G(v↪χ)) over D. To do this, we first characterise the structure of models of datalogHS 2n programs.

3 Canonical Models

Let ⇧ be a datalogHS 2n program and C a set of ground atoms of the form P(c)@◆. Denote by cl(C) the result of applying non-recursively the following rules to C:

• if [R]`A@◆ 2 C, then we add to C all A@ with ◆R`;
• if A A1 ^ · · · ^ Ak is a rule in ⇧ and C contains ⌫(Ai)@◆, for all 1  i  k and some assignment ⌫, then we add ⌫(A)@◆ to C;
• if A@ 2 C for all  with ◆R`, then add [R]`A@◆ to C.

(Here, given an atom A and an assignment ⌫, we denote by ⌫(A) the result of replacing each variable v in A with ⌫(v); we also assume that C contains all inequalities c 6= c0 for distinct constants c and c0 .) Then we set cl0 (C) = C and, for any successor ordinal ⇠ + 1 and limit ordinal ⇣,

Theorem 3. (i) If ?@◆ 2 C⇧↪D for any ◆, then ⇧ and D are inconsistent; otherwise, ⇧ and D are consistent and C⇧↪D is their minimal model in the sense that P(c)@◆ 2 C⇧↪D implies M↪ ◆ ♣= P (c), for any model M of ⇧ and D.

Now, given a data instance D, we set C⇧↪D = cl2@0 (D). If ?@◆ ◁2 C⇧↪D for all ◆, we regard C⇧↪D as an interpretation and call it the canonical model of ⇧ and D.

(ii) A pair (c↪ δ) is a certain answer to (⇧↪ q(v↪ χ)) over D that is consistent with ⇧ iff C⇧↪D ♣= q(c↪ δ).

Our next aim is to describe the structure of C⇧↪D. Suppose X = (X↪ ✁) is a linear order and K = ¶k1↪ ▷ ▷ ▷ ↪ km♦ a finite subset of X with kj ✁ kj+1, for 1  j < m. Denote by secX(K) the following set of sections of X:

where (-1↪ k) = ¶x 2 X ♣ x✁k↪ x 6= k♦ and symmetrically for (k↪1). Given σ1↪ σ2 2 secX(K), we write σ1 ⪯ σ2 if [x1↪ x2] 2 int(X), for some x1 2 σ1, x2 2 σ2. The relation ⪯ is a linear order, which is reflexive if ✁ is reflexive (if ✁ is irreflexive then [k↪ k] 6⪯ [k↪ k]). We now define a partition of int(X) into non-empty zones of the form

for any σ1↪ σ2 2 secX(K) with σ1 ⪯ σ2. The set of zones is denoted by zoneX(K). For m = 3, the partition of int(X) into zones is shown below, where intervals [x↪ y] are represented by points (x↪ y) in the Euclidean plane:

(zone-uniformity) for any interval relation R and any zones ⇣1 and ⇣2, if ◆1R◆2 for some ◆1 2 ⇣1 and ◆2 2 ⇣2, then for every ◆01 2 ⇣1 there is ◆02 2 ⇣2 such that ◆01R◆02 .

It is not hard to see that, for p = 2♣K♣ + 1,

Given a data instance D, we define the set zone(D) of hyperzones of D as Qn`=1 zone`(D), where zone`(D) = zoneX` (num`(D)). By using (zone-uniformity) for both R and ¯R along with the definition of C⇧↪D, we obtain:

Theorem 4. If P(c)@◆ 2 C⇧↪D, then P(c)@ 2 C⇧↪D for all  from the same hyperzone as ◆.

Note that (zone-uniformity) and Theorem 4 do not hold for (Z↪<); see [Bresolin et al., 2016]. For example, consider ⇧ = ¶[E]q [B]r, [E]r [B]q♦ and D = ¶q@[0↪ 0]♦: we have q@[n↪ n] 2 C⇧↪D for even n 2 N but q@[n↪ n] 62 C⇧↪D for odd n.

We can view each order X` as a Kripke frame I` with the set of worlds int(X`) and accessibility relations R. The space X = Qn`=1 X` gives rise to the n-dimensional product frame I = Qn`=1 I` [Gabbay et al., 2003]. The canonical model C⇧↪D can then be regarded as a first-order Kripke model with the first-order domain ind(D) and Kripke frame I where P (c) holds at a world ◆ iff P(c)@◆ 2 C⇧↪D.

Denote by Z` the Kripke frame with the set of worlds zone`(D) and accessibility relations R over them such that ⇣1R⇣2 iff ◆1R◆2 for some ◆1 2 ⇣1 and ◆2 2 ⇣2. Now, define a Kripke model S⇧↪D over the product frame Z = Qn`=1 Z` as follows: P(c) holds in a world ⇣ iff P(c)@◆ 2 C⇧↪D for some (equivalently, all) ◆ 2 ⇣. Let f` be a map from X` onto zone`(D) sending all intervals in any zone ⇣ to ⇣, and let f(◆) = (f1(◆1)↪ ▷ ▷ ▷ ↪ fn(◆n)). By Theorem 4 and (zoneuniformity), f is a p-morphism from C⇧↪D onto S⇧↪D. This fact and Theorem 3 give the following theorem:

Theorem 5. Fix some X = Qn`=1 X` with X` = (Z↪) or X` = (R↪<). For any OMQ Q(v↪χ) = (⇧↪ q(v↪χ)) and any data instance D that is consistent with ⇧, a pair (c↪ δ) is a certain answer to Q over D iff there is a tuple ⇠ of zones such that S⇧↪D ♣= q(c↪ ⇠) and δi 2 ⇠i, for 1  i  ♣δ♣.

The model S⇧↪D can be constructed in polynomial time using the same rules as in the definition of C⇧↪D, but with a quadratic number of hyperzones in place of hyperrectangles. This gives the upper bound of the next theorem:

Theorem 6. The problem of checking whether (c↪ δ) is a certain answer to Q(v↪χ) over D is P-complete for data complexity and EXPTIME-complete for combined complexity. For propositional datalogHS 2n programs, the problem is Pcomplete for combined complexity.

We establish the lower bound for data complexity by reduction of the monotone (fan-in 2) circuit value problem, which is known to be P-hard. Let C be a monotone circuit whose gates are enumerated by consecutive positive even integers so that if there is an edge from n to m then n < m. We encode C with an input ↵ by a data instance D with the facts:

• G@([n - 1↪ n]), for every G-gate n, G 2 ¶AND↪ OR♦;
• V@([0↪ n-1]) (or V@([0↪ n])) if the first (resp., second) input of gate n gets a value V 2 ¶T↪ F♦;
• I@([n↪m-1]) (or I@([n↪m])) if the output of gate n is the first (resp., second) input of gate m;
• S@([N↪N + 1]) and I@([N↪N + 1]), where N is the last (output) gate in C.

We illustrate the construction by the following example:

2

Let ⇧ be the propositional program

whose clauses encode the truth-table for AND and dually for OR with F and T swapped (which can clearly be rewritten in datalogHS 21 ). One can check that C(↵) = 1 iff the answer to the OMQ (⇧↪ 9χ (S@χ^T@χ)) over D is 'yes'. Note that this reduction works for both (Z↪) and (R↪<). Note also that OMQs with LTL 2 horn ontologies [Artale et al., 2015b] (which are syntactically similar to propositional datalogHS 21 programs but with the underlying 2-fragment of the linear time temporal logic) can be evaluated in AC0 for data complexity. The difference between the data complexities of these formalisms can be explained by the fact that (classical) HS is essentially two-dimensional whereas LTL operates in one dimension; cf. [Gabbay et al., 2003].

We show now that the problem of finding certain answers to datalogHS 2n OMQs can be reduced to computing answers to standard datalog programs over the same data instances.

4 Datalog Rewriting

Suppose we are given an OMQ Q(v↪ χ) = (⇧↪ q(v↪ χ)). Our aim is to rewrite Q(v↪χ) to a datalog program⇧ with a goal G(v↪χ) such that, for any data instance D, a tuple (c↪ δ) is a certain answer to Q(v↪χ) over D iff ⇧ ↪D ♣= G(c↪ δ). To simplify presentation, we only consider the case of 1D space;

a generalisation to n dimensions is straightforward though cumbersome. Here we only show the rules for X = (R↪<) and indicate the necessary modifications for (Z↪ ).

To operate with numbers in num(D), we first use the builtin <, 6= and stratified negation to define in ⇧ the predicates succ, max and min over num(D), where succ(s1↪ s2) iff s2 is an immediate <-successor of s1 in num(D), max(s) iff s is the maximal number in num(D), and similarly for min(s). We also use two constants +1 and -1 assuming that -1 < s < +1, for any s 2 num(D). Note that stratified negation (supported by most datalog tools) is not required elsewhere in ⇧ . In fact, a system implementing datalogHS 2n could simply maintain the extensions of the above predicates, which are ontology- and query-independent.

We encode sections secX(num(D)) of the partition of X using a binary predicate sec(s1↪ s2): punctual sections correspond to s1 = s2 and open sections to s1 < s2. More formally, sec(s1↪ s2) is defined by the following rules:

We also require the immediate proper ⪯-successor relation on secX(num(D)). Recall that for (R↪<) each punctual section is followed by an open one and the other way round:

Thus, nx(s1↪ s2↪ s01 ↪ s02 ) holds just in case the section defined by (s01 ↪ s02 ) immediately follows the section of (s1↪ s2). Note that there is a third option for (Z↪): the punctual section [s↪ s] can be followed by the punctual section [s + 1↪ s + 1].

Each zone in zoneX(num(D)) is characterised by a pair of sections in secX(num(D)), and so we use quadruples of variables to specify zones and define a quaternary predicate zone for (R↪<) by the rule

Assuming that ⇧ is in normal form, we replace each P (t) in it with P ⇤ (t↪ s↪ e) and each [R]P (t) with P[R](t↪ s↪ e), where two pairs s = (s1↪ s2) and e = (e1↪ e2) form a zone quadruple. To translate the facts from a data instance into zones, we use the rules

Thus, it remains to define the predicates of the form P[R]. We begin with P[E]. A slice of the accessibility relation E in the Kripke frame Z with worlds zoneX(D) is illustrated below:

We use the predicate E0(s↪ e) to identify zones without any proper E-successors:

If [E]P holds at a zone, then both P ⇤ and [E]P are propagated to all E-accessible zones using the rules

(The last rule reflects reflexivity of E in zones based on punctual sections.) For the converse direction, we require the following recursive rules for P[E] of its fixpoint definition:

We define P[¯E], P[B] and P[¯B] in a similar manner. For example, we need

and the rules for P[B] and P[¯B] contain nx(e↪ e0 ) in place of nx(s↪ s0 ). These predicates are then used to define P[R] for the remaining relations R. For example, for P[A], we have

Finally, suppose q(v↪χ) = 9v0 ↪χ0 Φ(v↪ v0 ↪χ↪χ0 ), where Φ is a conjunction of atoms of the form P(t)@[⌧1↪ ⌧2] and R(⌧1↪ ⌧2). For each such P (t)@[⌧1↪ ⌧2], we add to our program

where the ternary predicate in is defined by

We also add the rules defining the interval relations R such as

Finally, we add the rule with the head G(v↪ χ) and the body containing the P (t↪ ⌧) and R(⌧1↪ ⌧2) from the given CQ, and denote the resulting program by ⇧ .

Theorem 7. For any data instance D, a tuple (c↪ δ) is a certain answer to Q(v↪χ) over D iff ⇧ ↪D ♣= G(c↪ δ).

Note that the size of ⇧ is linear in the size of Q. Indeed, the rewriting consists of a fixed number of rules to define the partition and a fixed number of rules for each [R]P in the program. The arity of predicates in ⇧ is the original arity of predicates +4n for n zone quadruples in n-dimensional case.

5 Case Studies

We tested the expressive power and efficiency of OBDA with datalogHS 2n using two real-world scenarios. In our experiments, we used three off-the-shelf tools for (extensions of) datalog: CLASP [Gebser, Kaufmann, and Schaub, 2012] (v 3.1.4, with GRINGO v 4.5.4 as grounder), DLV [Leone et al., 2006] (v Dec 17 2012), and XSB [Sagonas, Swift, and Warren, 1994] (v 3.6). The three systems ran with default parameters on an Intel Xeon E3-1245 3.30 GHz workstation with 16GB of memory under the Ubuntu 12.04 64-bit OS.

5.1 Querying Historical Documents: 1DCase

In the first case study, we used datalogHS 2n to query the historical data in the STOLE 1 ontology, which extracts facts about the Italian Public Administration from journal articles [Adorni et al., 2015]. The dataset contains 1743 facts about institutions, legal systems, historical events and people obtained from articles published between 1850 and 1935. We represented the timestamps in years using the interval structure of (Z↪ ). The (atemporal) STOLE ontology was extended with datalogHS 2n rules such as

for institutions founded during the Regno di Sardegna period and historical event during the publication period of a journal,

relating journals to the legal system when they were established and closed, respectively, and

for persons cited by journal articles after their death. We then used the new intensional predicates to formulate complex queries such as 2SysJ(x) given by the formula

which finds journals published over two or more legal systems. The runtimes (in seconds) of the three systems on our queries are reported in table below:

The total number of zones for the dataset is 38503, and the last column gives the number of facts in the materialisation.

5.2 QueryingMeteorological Data: 2DCase

In the second case study, we used datalogHS 2n to query the US weather data collected by MesoWest 2 and containing sensor measurements of the temperature, precipitation, pressure, etc. by weather stations across the country. We mapped the MesoWest dataset tables to tuples T◦ (s↪ t1↪ t2↪ ⌧1↪ ⌧2), where s is the ID of a weather station, [t1↪ t2] a time interval, and [⌧1↪ ⌧2] the minimal and maximal temperature observed during this interval. The measurements are taken every six hours, so that t2 - t1 = 6 for all s, but different s may have different [t1↪ t2]. We extended this data by tuples of the form NAM(0:00◁10▷01▷2016↪ 6:00◁10▷01▷2016↪ ↪ ) to indicate the night AM hours, and similar tuples NPM for night PM, DAM for day AM, and DPM for day PM hours. Normally, during sunny days, the day AM temperature is not lower than the night AM temperature and the night PM temperature is not higher than the day PM temperature. The picture below shows patterns with abnormally low and high temperatures:

1 For STOria LEgislativa della pubblica amministrazione italiana.

2 http://mesowest.utah.edu

MEM means that the system runs out of memory (16 GB). The total number of zones for the time and temperature dimensions is given in the last two columns. The experiments show that standard off-the-shelf systems scale relatively well even with such large numbers of zones. Specialised index data structures and optimisations should boost performance. For example, one could pre-compute zones and relations on them, and use highly scalable triple store RDFox [Nenov et al., 2015] (without the need to implement arithmetic).

6 Conclusions

We designed an ontology language datalogHS 2n with the aim of OBDA over many-dimensional interval-based spatiotemporal data. DatalogHS 2n ontologies are supposed to define complex spatio-temporal predicates (such as those in the examples above), which can then be used in user queries. We proved datalog rewritability of ontology-mediated queries, and demonstrated experimentally, using real-world data, that these rewritings are reasonably well executable by off-the-shelf datalog systems. This seems to be the first working application of a fragment of the Halpern-Shoham logic HS, which is undecidable over any interesting linear order.

Note that the following are disallowed in datalogHS 2n : (i) operators hRi in the head of the rules, (ii) the strict semantics for R over Z (which can express metric constraints such as 'interval of length n'), and (iii) punctual intervals [n↪ n] over R. The addition of (i) or (ii) would make datalogHS 2n undecidable; the effect of (iii) remains unknown.

Propositional datalogHS 2n can be of interest in classical spatial representation as it provides a tractable formalism for reasoning about hyperrectangles. For example, it would be interesting to investigate whether our formalism can be adopted to handle rotated rectangles in the world of Angry Birds [Zhang and Renz, 2014], regions of arbitrary shape, and operators based on more expressive relations than Allen's.

Acknowledgments. This work has been supported by the EPSRC UK grant and EP/M012670/1 (iTract).