On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators

We consider monadic datalog queries, in which atoms in the rule bodies can be prefixed by the temporal operators $○$/${○}^{-}$ (at the next/previous moment) and $\mathrm{◇}$/${\mathrm{◇}}^{-}$ (sometime in the future/past) of linear temporal logic L​TL [17]. This query language, denoted ${\text{datalog}}_m^{○\diamond }$, is intended for querying temporal graph databases and knowledge graphs in scenarios such as virus transmission [25, 45], transport networks [28], social media [38], supply chains [46], and power grids [37]. In this setting, data instances are finite sets of ground atoms that are timestamped by the moments of time they happen at. The rules in ${\text{datalog}}_m^{○\diamond }$ queries are assumed to hold at all times, with time being implicit in the rules and only accessible via temporal operators. We choose L​TL for our formalism rather than, say, more expressive metric temporal logic MTL [30, 1] because L​TL has been a well established query language in temporal databases since the 1990s (see [39, 41, 14, 32] and the discussion therein on point versus interval-based query languages), also suitable in the context of temporal knowledge graphs as recently argued in [19].

Our main concern is the classical problem of deciding whether a given temporal monadic datalog query is equivalent to a first-order query (over any data instance). In the standard, atemporal database theory, this problem, known as predicate boundedness, has been investigated since the mid 1980s with the aim of optimising and parallelising datalog programs [27, 16]. Thus, predicate boundedness was shown to be undecidable for binary datalog queries [24] and 2ExpTime-complete for monadic ones (even with a single recursive rule) [15, 8, 29].

Datalog boundedness is closely related to the more general rewritability problem in the ontology-based data access paradigm [11, 3], which brought to light wider classes of ontology-mediated queries (OMQs) and ultimately aimed to decide the data complexity of answering any given OMQ and, thereby, the optimal database engine needed to execute that OMQ. Answering OMQs given in propositional linear temporal logic L​TL is either in ${\text{AC}}^0$, or in ${\text{ACC}}^0\setminus {\text{AC}}^0$, or ${\text{NC}}^1$-complete for data complexity [40], the classes well known from the circuit complexity theory for regular languages. For each of these three cases, deciding whether a given L​TL-query falls into it is ExpSpace-complete, even if we restrict the language to temporal Horn formulas and atomic queries [31]. The data complexity of answering atemporal monadic datalog queries comes from four complexity classes ${\text{AC}}^0⫋\text{L}\subseteq \text{NL}\subseteq \text{P}$ [16, 15].

Our 2D query language ${\text{datalog}}_m^{○\diamond }$ is a combination of datalog and L​TL. It can be seen as the monadic fragment, without negation and aggregate functions, of ${\text{Dedalus}}_0$, a language for reasoning about distributed systems that evolve in time [2]. It is also close in spirit to temporal deductive databases, TDDs [13, 12], extending their monadic fragment with the eventuality operator $\mathrm{◇}$. The main intriguing question we would like to answer in this paper is whether deciding membership of 2D queries in, say, ${\text{AC}}^0$ can be substantially harder than deciding membership in ${\text{AC}}^0$ of the corresponding 1D monadic datalog and L​TL queries.

With this in mind, we focus on the sublanguage ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○\diamond }$ of ${\text{datalog}}_m^{○\diamond }$ that consists of linear queries, that is, those that have at most one IDB (intensional, recursively definable) predicate in each rule body. While the full language inherits from TDDs a PSpace-complete query answering problem (for data complexity), we prove that linear queries can be answered in NL. By ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$ and ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{\diamond }$ we denote the fragments of ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○\diamond }$ that only admit the $○$/${○}^{-}$ and $\mathrm{◇}$/${\mathrm{◇}}^{-}$ operators, respectively. All of our queries are assumed to be connected in the sense that the graph induced by the body of each rule is connected. These fragments retain practical interest: as argued in [15], atemporal datalog programs used in practice tend to be linear and connected. For example, SQL:1999 explicitly supports linear recursion [20], which together with connectedness is a common constraint in the context of querying graph databases and knowledge graphs [35, 42], where the focus is on path queries [21, 23].

It is known that deciding whether a linear monadic datalog query can be answered in ${\text{AC}}^0$ is PSpace-complete [15, 43] (without the monadicity restriction, the problem is undecidable [24]). The same problem for the propositional L​TL fragments of ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$ and ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○\diamond }$ is also PSpace-complete [31].

Our main results in this paper are as follows:

• $\mathrm{■}$

  Answering ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○\diamond }$ queries is NL-complete for data complexity.

• $\mathrm{■}$

  It is undecidable whether a given ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{\diamond }$-query can be answered in ${\text{AC}}^0$, ${\text{ACC}}^0$, or ${\text{NC}}^1$ (if ${\text{NC}}^1\ne \text{NL}$); it is undecidable whether such a query is L-hard (if $\text{L}\ne \text{NL}$).

• $\mathrm{■}$

  Answering any connected ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$-query is either in ${\text{AC}}^0$ or in ${\text{ACC}}^0\setminus {\text{AC}}^0$, or ${\text{NC}}^1$-complete, or L-hard – and anyway it is in NL.

• $\mathrm{■}$

  It is PSpace-complete to decide whether a connected ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$-query is L-hard; checking whether it is in ${\text{AC}}^0$, or in ${\text{ACC}}^0\setminus {\text{AC}}^0$, or is ${\text{NC}}^1$-complete can be done in ExpSpace.

(Note that dropping the past-time operators ${○}^{-}$ and ${\mathrm{◇}}^{-}$ from the languages has no impact on these complexity results.) Thus, the temporal operators $○$/${○}^{-}$ and $\mathrm{◇}$/${\mathrm{◇}}^{-}$ exhibit drastically different types of interaction between the object and temporal dimensions. To illustrate the reason for this phenomenon, consider first the following ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$-program:

Suppose a data instance consists of timestamped atoms $A(a,0)$, $R(a,b,1)$, $B(b,5)$. We obtain $G(a,0)$ by first applying rule (3) to infer $D(b,5)$, then rule (2) to infer $D(b,4),D(b,3),D(b,2)$, and $D(b,1)$, and finally rule (1) to obtain $G(a,0)$. Rules (2) and (3) are applied along the timeline of a single object, $b$, while the final application passes from one object, $b$, to another, $a$. To do so, we check whether a certain condition holds for the joint timeline of $a$ and $b$, namely, that they are connected by $R$ at time 1. However, if we are limited to the operators $○$/${○}^{-}$, the number of steps that we can investigate along such a joint timeline is bounded by the maximum number of nested $○$/${○}^{-}$ in the program. Therefore, there is little interaction between the two phases of inference that explore the object and the temporal domains. In contrast, rules with $\mathrm{◇}$/${\mathrm{◇}}^{-}$ can inspect both dimensions simultaneously as, for example, the rule

In this case, inferring $G(a,0)$ requires checking the existence of an object $b$ satisfying $D(b,0)$ and $R(a,b,\mathrm{\ell })$ at some arbitrarily distant moment $\mathrm{\ell }$ in the future. Given that our programs are monadic, the predicate $\mathrm{◇}R(X,Y)$ cannot be expressed using operators $○$/${○}^{-}$ only.

Our positive results are proved by generalising the automata-theoretic approach of [15]. As a by-product, we obtain a method to decompose every connected ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$-query $(\pi ,G)$ into a plain datalog part $({\pi }_d,G)$ and a plain L​TL part $({\pi }_t,G)$, which are, however, substantially larger than $(\pi ,G)$, so that the data complexity of answering $(\pi ,G)$ equals the maximum of the respective data complexities of $({\pi }_d,G)$ and $({\pi }_t,G)$. This reinforces the “weakness of interaction” between the relational and the temporal parts of the query when the latter is limited to operators $○$/${○}^{-}$. We also provide some evidence that, in contrast to the atemporal case, the automata-theoretic approach cannot be generalised to the case of disconnected queries. The undecidability of the decision problem for ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{\diamond }$-queries is proved by a reduction of the halting problem for Minsky machines with two counters [33].

The paper is organised as follows. In Section 2, we give formal definitions of data instances and queries, and prove that every temporal monadic datalog query can be answered in P, and in NL if it is linear. In Section 3, we show that checking whether a given query with operator $\mathrm{◇}$ or ${\mathrm{◇}}^{-}$ has data complexity lower than NL is undecidable. Section 4 considers ${\text{datalog}}_{\mathrm{𝑙𝑚}}^{○}$-queries by presenting a generalisation of the automata-theoretic approach of [15], which is then used in Section 5 to provide the decidability results. We conclude with a discussion of future work and our final remarks in Section 6. Detailed proofs can be found in the full version of this paper [4].

A relational schema $\mathrm{\Sigma }$ is a finite set of relation symbols $R$ with associated arities $m\ge 0$. A database $D$ over a schema $\mathrm{\Sigma }$ is a set of ground atoms $R(d_1,\mathrm{\dots },d_m)$, $R\in \mathrm{\Sigma }$, $m$ is the arity of $R$. We call $d_i$, $1\le i\le m$, the domain objects or simply objects. We denote by ${\mathrm{\Delta }}_D$ the set of objects occurring in $D$. We denote by $|D|$ the number of atoms in $D$. We denote by $[a,b]$ the set of integers $\{m\mid a⩽m⩽b\}$, where $a,b\in \mathbb{Z}$. A temporal database $𝒟$ over a schema $\mathrm{\Sigma }$ is a finite sequence $⟨D_l,D_{l+1}\mathrm{\dots },D_{r-1},D_r⟩$ of databases over this schema for some , $l,r\in \mathbb{Z}$. Each database $D_i,l⩽i⩽r,$ is called the $i$’th slice of $𝒟$ and $i$ is called a timestamp. We denote $[l,r]$ by $\mathrm{tem}(𝒟)$. The size of $𝒟$, denoted by $|𝒟|$, is the maximum between $|\mathrm{tem}(𝒟)|$ and $\max \{|D_l|,\mathrm{\dots },|D_r|\}$. The domain of the temporal database $𝒟$ is ${\bigcup }_{l\le i\le r}{\mathrm{\Delta }}_{D_i}$ and is denoted by ${\mathrm{\Delta }}_{𝒟}$. A homomorphism from $𝒟$ as above to ${𝒟}^{\prime }=⟨D_{l^{\prime }},D_{l^{\prime }+1}\mathrm{\dots },D_{r^{\prime }-1},D_{r^{\prime }}⟩$ is a function $h$ that maps ${\mathrm{\Delta }}_{𝒟}\cup [l,r]$ to ${\mathrm{\Delta }}_{{𝒟}^{\prime }}\cup [l^{\prime },r^{\prime }]$ so that $R(d_1,\mathrm{\dots },d_m)\in D_{\mathrm{\ell }}$ if and only if $R(h(d_1),\mathrm{\dots },h(d_m))\in D_{h(\mathrm{\ell })}^{\prime }$.

We will deal with temporal conjunctive queries (temporal CQs) that are formulas of the form $Q(\overline{X})=\exists \overline{U}\phi (\overline{X},\overline{U})$, where $\overline{X},\overline{U}$ are tuples of variables and $\phi$, the body of the query, is defined by the following BNF:

where $R\in \mathrm{\Sigma }$ and $Z_1,\mathrm{\dots },Z_m$ are variables of $\overline{X}\cup \overline{U}$, and $𝒪$ is any of $○,{○}^{-},\mathrm{◇}$ and ${\mathrm{◇}}^{-}$ (the operators $○$/${○}^{-}$ mean “at the next/previous moment” and $\mathrm{◇}$/${\mathrm{◇}}^{-}$ “sometime in the future/past”). For brevity, we will use the notation ${𝒪}^n$, $𝒪\in \{○,\mathrm{◇}\}$, for a sequence of $n$ symbols $𝒪$ if $n>0$, of $|n|$ symbols ${𝒪}^{-}\in \{{○}^{-},{\mathrm{◇}}^{-}\}$ if , and an empty sequence if $n=0$. We call $\overline{X}$ the answer variables of $Q$. To provide the semantics, we define $𝒟,\mathrm{\ell }\vDash \phi (d_1,\mathrm{\dots },d_m)$ for $\mathrm{\ell }\in \mathbb{Z}$ and $d_1,\mathrm{\dots },d_m\in {\mathrm{\Delta }}_{𝒟}$ as follows:

and symmetrically for ${○}^{-}$ and ${\mathrm{◇}}^{-}$. Given a temporal database $𝒟$, a timestamp $\mathrm{\ell }\in \mathbb{Z}$, and a query $Q(\overline{X})=\exists \overline{U}\phi (\overline{X},\overline{U})$, we say that $𝒟,\mathrm{\ell }\vDash Q(d_1,\mathrm{\dots },d_k)$ if there exist ${\delta }_1,\mathrm{\dots },{\delta }_s\in {\mathrm{\Delta }}_{𝒟}$ such that $𝒟,\mathrm{\ell }\vDash \phi (d_1,\mathrm{\dots },d_k,{\delta }_1,\mathrm{\dots },{\delta }_s)$, where $k=|\overline{X}|,s=|\overline{U}|$.

The problem of answering a temporal CQ $Q$ is to check, given $𝒟$, $\mathrm{\ell }\in \mathrm{tem}(𝒟)$, and $\overline{d}=⟨d_1,\mathrm{\dots },d_k⟩$, whether $𝒟,\mathrm{\ell }\vDash Q(\overline{d})$. Answering temporal CQs is not harder than that for non-temporal CQs. Indeed, we show that any $Q$ is -rewritable in the sense that there exists an -formula $\psi (\overline{X},t)$ such that for all $\mathrm{\ell }$ and $\overline{d}$ as above $𝒟,\mathrm{\ell }\vDash Q(\overline{d})$ whenever $\psi (\overline{d},\mathrm{\ell })$ is true in the two-sorted first-order structure ${𝔖}_{𝒟}$, whose domain is ${\mathrm{\Delta }}_{𝒟}\cup \mathrm{tem}(𝒟)$, and where $R(\overline{d},\mathrm{\ell })$ is true whenever $𝒟,\mathrm{\ell }\vDash R(\overline{d})$ and is true whenever (see [5] for details). It follows by [26] that the problem of answering a temporal CQ $Q$ is in ${\text{AC}}^0$.

We outline the construction of the rewriting. Let $Q(\overline{X})=\exists \overline{U}\phi (\overline{X},\overline{U})$. The main issue with the construction is that temporal subformulas of $\phi$, say $\mathrm{◇}\varkappa$, may be true for $\overline{d}$ at $\mathrm{\ell }\in \mathrm{tem}(𝒟)$, because $𝒟,{\mathrm{\ell }}^{\prime }\vDash \varkappa (\overline{d})$ for ${\mathrm{\ell }}^{\prime }\notin \mathrm{tem}(𝒟)$. Had that not been the case, we could construct the rewriting for $Q$ straightforwardly by induction of $\phi$. To overcome this, let $N$ be the number of temporal operators in $\phi$. We use a property that for all tuples $\overline{d}$ of objects from ${\mathrm{\Delta }}_{𝒟}$ and subformulas $\varkappa$ of $\phi$, we have

Thus, for any subformula $\varkappa (\overline{Z})$ of $\phi$, we construct, by induction, the formulas ${\psi }_{\varkappa }(\overline{Z},t)$ and ${\psi }_{\varkappa }^i(\overline{Z})$ for $i\in [-N-1,\mathrm{\dots },-1]\cup [1,\mathrm{\dots },N+1]$, so that for any $𝒟$, $\mathrm{tem}(𝒟)=[l,r]$, and any objects $\overline{d}\in {\mathrm{\Delta }}_{𝒟}^{|\overline{Z}|}$,

For the base case, we set ${\psi }_R(\overline{Z},t)=R(\overline{Z},t)$ and ${\psi }_R^i(\overline{Z})=\perp$. For an induction step, e.g., ${\psi }_{○\varkappa }^{-1}(\overline{Z})={\psi }_{\varkappa }(\overline{Z},\min )$, ${\psi }_{○\varkappa }^{N+1}(\overline{Z})={\psi }_{\varkappa }^{N+1}(\overline{Z})$, ${\psi }_{○\varkappa }^i(\overline{Z})={\psi }_{\varkappa }^{i+1}(\overline{Z})$ for all other $i$, and finally ${\psi }_{○\varkappa }(\overline{Z},t)=\exists t^{\prime }((t^{\prime }=t+1)\wedge {\psi }_{\varkappa }(\overline{Z},t^{\prime }))\vee ((t=\max )\wedge {\psi }_{\varkappa }^1(\overline{Z}))$. Here, $\min$ and $\max$ are defined in as, respectively, -minimal and -maximal elements in $\mathrm{tem}(𝒟)$ ($(t^{\prime }=t+1)$ is -definable as well). The required rewriting of $Q$ is then the formula $\exists \overline{U}{\psi }_{\phi }(\overline{X},\overline{U},t)$.

In the non-temporal setting, a body of a CQ (a conjunction of atoms), can be seen as a database (a set of atoms). We have a similar correspondence in the temporal setting, for queries without operators $\mathrm{◇}$ and ${\mathrm{◇}}^{-}$. Indeed, observe that ${○}^a({\phi }_1\wedge {\phi }_2)\equiv {○}^a{\phi }_1\wedge {○}^a{\phi }_2$ and ${○○}^{-}\phi \equiv {○}^{-}○\phi \equiv \phi$. Hence we can assume that any temporal CQ body is a conjunction of temporalised atoms of the form ${○}^{k}R(Z_1,\mathrm{\dots },Z_m)$. Given a temporal CQ $Q$ of this form, let $l$ be the least and $r$ the greatest number such that ${○}^{l}R(\overline{Z})$ and ${○}^r{R}^{\prime }({\overline{Z}}^{\prime })$ appear in $Q$, for some $R,R^{\prime },\overline{Z}$ and ${\overline{Z}}^{\prime }$. Let ${𝒟}_Q$ be a temporal database whose objects are the variables of $Q$, and $\mathrm{tem}(𝒟)$ equals $[l,r]$ if $0\in [l,r]$, $[0,r]$ if , and $[l,0]$ if . Furthermore, let $R(\overline{Z})\in D_{\mathrm{\ell }}$ whenever ${○}^{\mathrm{\ell }}R(\overline{Z})$ is in $Q$, $\mathrm{\ell }\in \mathrm{tem}(𝒟)$. Then we can, just as in the non-temporal case, characterise the relation $\vDash$ in terms of homomorphisms:

Our first result about deciding the complexity of a given query is negative.

The proof is by a reduction from the halting problem of 2-counter machines [33]. Namely, given a 2-counter machine $M$ we construct a query $({\pi }_M,G)$ that is in ${\text{AC}}^0$ if $M$ halts and NL-complete otherwise.

Recall, that a 2-counter machine is defined by a finite set of states $S=\{s_0,\mathrm{\dots },s_n\}$, with a distinguished initial state $s_0$, two counters able to store non-negative integers, and a transition function $\mathrm{\Theta }$. On each step the machine performs a transition by changing its state and incrementing or decrementing each counter by 1 with a restriction that their values remain non-negative. The next transition is chosen according to the current state and the values of the counters. However, the machine is only allowed to perform zero-tests on counters and does not distinguish between two different positive values. Formally, transitions are given by a partial function $\mathrm{\Theta }$:

Let $\mathrm{sgn}(0)=0$ and $\mathrm{sgn}(k)=+$ for all $k>0$. A computation of $M$ is a sequence of configurations:

such that for each , holds $\mathrm{\Theta }(s_i,\mathrm{sgn}(a_i),\mathrm{sgn}(b_i))=(s_{i+1},{\epsilon }_1,{\epsilon }_2)$ and $a_{i+1}=a_i+{\epsilon }_1$, $b_{i+1}=b_i+{\epsilon }_2$. We assume that $a_0,b_0=0$ and $\mathrm{\Theta }$ is such that $a_i,b_i⩾0$ for all $i$. We call $m$ the length of the computation. We say that $M$ halts if $\mathrm{\Theta }(s_m,\mathrm{sgn}(a_m),\mathrm{sgn}(b_m))$ is not defined in a computation. Thus, $M$ either halts after $m$ steps or goes through infinitely many configurations.

Let $M$ be a 2-counter machine. We construct a connected linear query $({\pi }_M,G)$ using the operator $\mathrm{◇}$ only, such that its evaluation is in ${\text{AC}}^0$ if $M$ halts, but becomes NL-complete otherwise. The construction with the operator ${\mathrm{◇}}^{-}$ instead of $\mathrm{◇}$ is symmetric.

We set the EDB schema $\mathrm{\Sigma }=\{T,U_1,U_2\}$ of three relations which stand for “transition”, “first counter update”, and “second counter update”, respectively. Intuitively, domain elements of a temporal database represent configurations of $M$, and role triples of $T$, $U_1$ and $U_2$, arranged according to certain rules described below, will play the role of transitions. A sequence of nodes connected by such triples will thus represent a computation of $M$. Our program ${\pi }_M$ will generate an expansion along such a sequence, trying to assign to each configuration an IDB that represents a state of $M$, which will be possible while the placement of the connecting roles on the temporal line follows the rules of $\mathrm{\Theta }$. If the machine halts, there is a maximum number of steps we can make, so the check can be done in ${\text{AC}}^0$. If $M$ does not halt, however, it has arbitrarily long computations, and the query evaluation becomes NL-complete.

Here are the details. A configuration $(s,a,b)$ is represented by an object $d$ and three timestamps ${\mathrm{\ell }}_0,{\mathrm{\ell }}_1,{\mathrm{\ell }}_2$ such that ${\mathrm{\ell }}_1={\mathrm{\ell }}_0+a$ and ${\mathrm{\ell }}_2={\mathrm{\ell }}_0+b$. The values of the counters $a$ and $b$ are indicated, respectively, by existence of connections $U_1^{{\mathrm{\ell }}_1}(d,d^{\prime })$ and $U_2^{{\mathrm{\ell }}_2}(d,d^{\prime })$ to some object $d^{\prime }$ that is supposed to represent the next configuration in the computation. For the transition to happen, we also require $T^{{\mathrm{\ell }}_0}(d,d^{\prime })$. Given a computation of the form (16), the corresponding computation path is a pair $(⟨d_0,\mathrm{\dots },d_n⟩,{\mathrm{\ell }}_0)$, where for each , there are $T^{{\mathrm{\ell }}_0}(d_i,d_{i+1})$, $U_1^{{\mathrm{\ell }}_0+a_i}(d_i,d_{i+1})$, and $U_2^{{\mathrm{\ell }}_0+b_i}(d_i,d_{i+1})$ in the database, with an additional requirement that $a_0=b_0=0$. Two types of problems may be encountered on such a path. A representation violation occurs when an object has more than one outgoing edge of type $T$, $U_1$, or $U_2$. A transition violation of type $(s_i,\alpha ,\beta )$ is detected when there are two consecutive nodes $d_i,d_{i+1}$, $\alpha =\mathrm{sgn}(a_i),\beta =\mathrm{sgn}(b_i)$, and $\mathrm{\Theta }(s_i,\alpha ,\beta )\ne (s_{i+1},a_{i+1}-a_i,b_{i+1}-b_i)$. The program ${\pi }_M$ will look for such violations. It will have an IDB relation symbol $S_i$ per each state $s_i$ of $M$. The initialisation rules allow to infer any state IDB from a representation violation, and the IDB $S_i$ from a transition violation of type $(s_i,\alpha ,\beta )$. The recursive rules then push the state IDB up a computation path following the rules of $\mathrm{\Theta }$ and tracing “backwards” a computation of $M$. Once ${\pi }_M$ infers the initial state IDB at a position with zero counter values, we are done. It remains to give the rules explicitly.

We use a shortcut ${\mathrm{◇}}^{\ast }$ to mean a “reflexive” version of $\mathrm{◇}$, i.e. ${\mathrm{◇}}^{\ast }\phi \equiv \mathrm{◇}\phi \vee \phi$. Clearly, every rule ${\mathrm{◇}}^{\ast }$ can be rewritten to an equivalent set of rules without it. We need the rules:

to detect representation violations. For transition violations, we first define IDBs $N{E}_c^{\epsilon }$, where $c\in 1,2$ stand for the respective counter and $ϵ\in \{-1,0,1\}$ stands for the change of that counter value in a transition. Each $N{E}_c^{\epsilon }$ detects situations when a correct transition was not executed, e.g. having $ϵ=-1$, the timestamps $\mathrm{\ell }$ and ${\mathrm{\ell }}^{\prime }$ that are marked by an outgoing $U_c$ in consecutive configurations satisfy $\mathrm{\ell }-1>{\mathrm{\ell }}^{\prime }$, $\mathrm{\ell }={\mathrm{\ell }}^{\prime }$, or , which they should not. The rules are the following:

for $c\in \{1,2\}$. Then, again, any state can be inferred from a violation:

for each transition $\mathrm{\Theta }(s_i,\alpha ,\beta )=(s_j,{\epsilon }_1,{\epsilon }_2)$, and for all ${\epsilon }_1,{\epsilon }_2$ when $\mathrm{\Theta }(s_i,\alpha ,\beta )$ is not defined. Finally, we require

This finalises the construction of $({\pi }_M,G)$. Any expansion of $({\pi }_M,G)$ starts with the body of the rule (25) and then continues by a sequence of bodies of the rules of the form (24) and ends with a detection either of a representation violation, defined by (17) – (18), or of a transition violation, defined by (23). If $M$ halts in $m$ steps, it is enough to consider expansions containing no more than $m$ bodies of (24). Thus, in this case $({\pi }_M,G)$ is in ${\text{AC}}^0$. If, on the contrary, $M$ does not halt, we can use expansions representing arbitrarily long prefixes of its computation for a reduction from directed reachability problem, rendering the query NL-hard.

From now on, we focus on queries that use operators $○$ and ${○}^{-}$ only. In this section, we develop a generalisation of the automata-theoretic approach to analysing query expansions proposed in [15]. In Section 5 we use this approach to study the data complexity of this kind of queries.

Recall from Section 2.1.1 the definitions of composition and expansion of rule bodies, alphabets ${\mathrm{\Gamma }}_{\pi }^r$ and ${\mathrm{\Gamma }}_{\pi }^i$, and the language $\text{expand}(\pi ,G)\subseteq {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }({\mathrm{\Gamma }}_{\pi }^i)$. We observe that for any sequence of rule bodies $B_1,\mathrm{\dots },B_{n-1}\in {\mathrm{\Gamma }}_{\pi }^r$ and $B_n\in {\mathrm{\Gamma }}_{\pi }^i$ the compositions $B_1\circ \mathrm{\cdots }\circ B_{n-1}$ and $B_1\circ \mathrm{\cdots }\circ B_n$ are well-defined. They are words in the languages ${({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }$ and ${({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }({\mathrm{\Gamma }}_{\pi }^i)$, respectively. Note that $B_1\circ \mathrm{\cdots }\circ B_n$ is a temporal CQ over schema $\text{EDB}(\pi )$, while $B_1\circ \mathrm{\cdots }\circ B_{n-1}$ is that over $\text{EDB}(\pi )\cup \text{IDB}(\pi )$, since it contains the IDB atom of $B_{n-1}$. For $w\in {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }({\mathrm{\Gamma }}_{\pi }^i)$, ${𝒟}_w$ is defined as the (temporal) database corresponding to (temporal) CQ $w$, while for $w\in {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }$ we define ${𝒟}_w$ as the database corresponding to the CQ obtained from $w$ by omitting the IDB atom. For either $w$, ${𝒟}_w$ is over the schema $\text{EDB}(\pi )$. Having that, we define the language $\text{accept}(\pi ,G)\subseteq {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }\cup {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }({\mathrm{\Gamma }}_{\pi }^i)$ of all words $w\in {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }\cup {({\mathrm{\Gamma }}_{\pi }^r)}^{\ast }({\mathrm{\Gamma }}_{\pi }^i)$ such that ${𝒟}_w,\pi ,0\vDash G(X)$.