A
Expressive Languages for Path Queries over Graph-Structured Data
PABLO BARCELÓ, University of Chile
LEONID LIBKIN, University of Edinburgh
ANTHONY W. LIN, Univerity of Oxford
PETER T. WOOD, Birkbeck, University of London

For many problems arising in the setting of graph querying (such as finding semantic associations in RDF
graphs, exact and approximate pattern matching, sequence alignment, etc.), the power of standard languages
such as the widely studied conjunctive regular path queries (CRPQs) is insufficient in at least two ways.
First, they cannot output paths and second, more crucially, they cannot express relationships among paths.
We thus propose a class of extended CRPQs, called ECRPQs, which add regular relations on tuples ofpaths, and allow path variables in the heads of queries. We provide several examples of their usefulness inquerying graph structured data, and study their properties. We analyze query evaluation and representationof tuples of paths in the output by means of automata. We present a detailed analysis of data and combinedcomplexity of queries, and consider restrictions that lower the complexity of ECRPQs to that of relational
conjunctive queries. We study the containment problem, and look at further extensions with first-orderfeatures, and with non-regular relations that add arithmetic constraints on the lengths of paths and numbersof occurrences of labels.
Categories and Subject Descriptors: H.2.1 [Database Management]: Logical Design—Data Models; F.1.1[Computation by abstract devices]: Models of Computation—Automata
General Terms: Theory, Languages, Algorithms
Additional Key Words and Phrases: Graph databases, conjunctive queries, regular relations, regular pathqueries

1. INTRODUCTION

For graph-structured data, queries that allow users to specify the types of paths inwhich they are interested have always played a central role. Most commonly, the specification of such paths has been by means of regular expressions over the alphabetof edge labels [Abiteboul et al. 1997; Calvanese et al. 2000; Consens and Mendelzon
1990; Florescu et al. 1998; Mendelzon and Wood 1995]. The output of a query is typically a set of tuples of nodes that are connected in some way by the paths specified.
The canonical class of queries with this functionality are the conjunctive regular pathqueries (CRPQs). These have been the subject of much investigation, e.g. [Calvanese
et al. 2000; Deutsch and Tannen 2001; Florescu et al. 1998].
However, the rapid increase in the size and complexity of graph-structured data
(e.g. in the Semantic Web, or in biological applications) has raised the need for addiAuthors’ addresses: P. Barceló, Department of Computer Science, University of Chile, Avda Blanco Encalada 2120, 3er piso, Santiago, Chile; L. Libkin, School of Informatics, University of Edinburgh, Informatics
Forum, 10 Crichton Street, Edinburgh EH8 9AB, United Kingdom; A. W. Lin, Department of Computer
Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom; P. T.
Wood,Department of Computer Science and Information Systems, Birkbeck, University of London, Malet
Street, London WC1E 7HX, United Kingdom.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights
for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any componentof this work in other works requires prior specific permission and/or a fee. Permissions may be requested
from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212)869-0481, or permissions@acm.org.
c YYYY ACM 0362-5915/YYYY/01-ARTA $10.00
DOI 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:2

Pablo Barceló et al.

tional functionality in query languages. Specifically, in many examples, the minimum
requirements of sufficiently expressive queries are: (a) the ability to define complex semantic relationships between paths and (b) the ability to include paths in the outputof the query. Neither of these is supported by CRPQs.
There are multiple examples of queries that require these new capabilities. For example, Anyanwu and Sheth [2003] introduce a query language for RDF/S in whichpaths can be compared based on specific semantic associations. Follow-up work in[Anyanwu et al. 2007] proposes the SPARQ2L query language, which extends SPARQL
with path variables and path filtering expressions. In handling biological sequences
one often needs to compare paths based on similarity (e.g., edit distance) [Gusfield1997]. Paths can be compared with respect to other parameters, e.g., lengths or numbers of occurrences of labels, which can be useful in route-finding applications [Barrett
et al. 2000].
As for the ability to output paths, this has been proposed, for example, as an extension to the SPARQL query language – the standard for retrieving RDF data [Kochut
and Janik 2007]. However, that proposal only included a declarative language, and left
most basic questions unexplored (e.g., what should an output be if there are infinitely
many paths between nodes?). Other applications for this new functionality include
determining the provenance of data or artifacts [Holland et al. 2008], finding associations in linked data [Lehmann et al. 2007], biological data [Lee et al. 2007] or social (orcriminal) networks [Sheth et al. 2005], as well as performing semantic searches over
web-derived knowledge [Weikum et al. 2009].
While the need for the extended functionality of graph query languages is welldocumented (and sometimes is even incorporated into a programming syntax), the basic properties of such languages are completely unexplored. We do not know whether
queries can be meaningfully evaluated, what their complexity is, whether they can be
optimized, etc.
Our main goals, therefore, are to formally define extensions of graph queries thatcan express complex semantic associations between paths and output paths to theuser, and to study them, concentrating on query evaluation and its complexity, as well
as some static analysis problems.
We work with the class of extended conjunctive regular path queries or (ECRPQs),
which generalize CRPQs by allowing them to express the kind of semantic association
properties described above. That is, we allow(1) n-tuples of path labels to be checked for conformity to n-ary path languages, and(2) paths, rather than simply nodes, to be output.
As an example, consider a graph G with a single edge label, defining the studentadvisor relationship. Using CRPQs, one can express many queries, such as finding
academic ancestors, or people whose sets of academic parents and grandparents intersect, or checking whether x and y have a common academic ancestor (and if so, whothat person is). However, with CRPQs we cannot express queries asking for pairs ofscientists who have the same-length path to a given advisor, nor can we ask for the precise paths by which two people are related to their common academic ancestor. With
ECRPQs, we can express such queries.
We now outline a few further examples of problems where the power of ECRPQs is
required. They will be fully developed in Section 3, after we have presented the syntax
and semantics of ECRPQs.
— Pattern matching. Given an alphabet Σ and a set of variables V, a pattern is a string
over Σ ∪ V. A pattern defines a pattern language by instantiating variables withstrings in Σ∗ . For example, the pattern aXbX denotes the set of all strings of the
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:3

form a · w · b · w, where w ∈ Σ∗ . Pattern languages need not be even context-free: e.g.,
the language of squared strings (i.e., strings w · w for w ∈ Σ∗ ) can be expressed by
the pattern XX, where X ∈ V. But finding nodes x and y connected by a path whoselabel is in the language of squared strings can be expressed by the ECRPQ:
Ans(x, y) ← (x, π1 , z), (z, π2 , y), π1 = π2
where x, y and z are node variables and π1 and π2 are path variables. Variables z,
π1 , and π2 are meant to be existentially quantified. What makes this different from
CRPQs is the binary relation π1 = π2 on paths: it states that the path labels between
x and an intermediate node z, and between z and y are the same.
— Semantic web associations. In RDF/S, properties can be declared to be subpropertiesof other properties. This is used by Anyanwu and Sheth [2003] to define a notion ofsemantic association based on ρ-isomorphic property sequences: two sequences areρ-isomorphic if they are of the same length and the properties at the same position in each sequence are subproperties of one another. Such pairs of sequences canbe found by a modification of the previous query with a different binary relation
expressing the fact that the paths are ρ-isomorphic.
— Approximate matching. Approximate string matching [Grahne and Thomo 2004;
Kanza and Sagiv 2001] and (biological) sequence alignment [Gusfield 1997] are both
based on the notion of edit distance. The relation representing pairs of sequencesthat have edit distance at most k from one another, for some fixed k, is regular[Frougny and Sakarovitch 1991]. So given a graph representing a pair of sequences,an ECRPQ can determine whether they have edit distance at most k, i.e. if one of
the sequences can be obtained from the other by applying at most k times the edit
operations of insertion, deletion and substitution of a symbol. We show in Section 4that we can also output the actual gaps and mismatches in the sequences using an
ECRPQ.
What kinds of relations can be used to compare paths? Following the idea behind
CRPQs, which allow regular conditions on paths, we use regular relations for pathcomparisons. Examples of regular relations (for now, binary) on paths π1 and π2 are:— path equality: π1 = π2 ;— length comparisons: |π1 | = |π2 | (and likewise for < and ≤);— prefix: π1 is a prefix of π2 ;— small edit distance: edit distance between π1 and π2 is at most k, for a fixed k;— synchronous transformation: if π1 = a1 . . . an , then π2 = h(a1 ) . . . h(an ) for some map
h : Σ → Σ.
Even though specifying regular relations with regular expressions is probably lessnatural than specifying regular languages (at least it is more cumbersome), we still
believe that our approach is of potential practical impact. In fact, any standard that
intends to use many (or some) of the expressive benefits of ECRPQs, without including
regular relations, could choose an appropriate set of commonly used regular relations(e.g., equality, length comparisons, or small edit distance), and use those as built-in
predicates in a query language.
Note that many common relations are not regular, for example, the suffix relation,
the substring or subsequence relation, or arithmetic comparisons of lengths of paths(e.g., |π1 | = 2|π2 |). Nonetheless, we shall show that some of the results can be extended
to nonregular relations, in particular to path-length comparisons.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:4

Pablo Barceló et al.

Outline of the results. After we formally define ECRPQs, we present an algorithm
for query evaluation. It turns out that the sets of labels of paths satisfying a query are
regular, and thus the evaluation algorithm constructs automata to represent such sets.
We then investigate the complexity of query evaluation. As yardsticks, we consider
relational languages as well as CRPQs. For conjunctive queries, combined complexity
is NP-complete, while it jumps to P SPACE-complete for relational calculus. Hence wecannot hope to get anything below NP for ECRPQs, and we hope not to exceed the complexity of relational queries in a reasonable class. As for data complexity, it is known
to be NL OGSPACE-complete for CRPQs, so this will serve as another benchmark.
It turns out that the data complexity of ECRPQs matches that of CRPQs, but combined complexity goes up from NP to P SPACE, matching relational calculus instead. In
this case it is natural to look for restrictions. A standard one for CQs is a restriction toacyclicity. This works for CRPQs – combined complexity becomes tractable – but does
not work for ECRPQs, as the combined complexity remains P SPACE-complete. However, if our regular relations can only consider lengths of paths, then the complexity of
ECRPQs drops to NP, matching the complexity of the usual relational CQs.
We then study extensions of CRPQs and ECRPQs: with negation and universal
quantification, and with some non-regular relations. For the former, we get surprisingly reasonable bounds for CRPQs, but the complexity becomes too high when both
negation and relations on paths are allowed. For the latter, we consider extensions withlinear constraints on path lengths, and prove some good complexity bounds (tractabledata complexity and NP combined complexity). We also consider relations that compare numbers of occurrences of labels in paths, and prove some low complexity bounds
for queries with such relations.
While query containment is known to be decidable for CRPQs, we show that ECRPQs share more properties with full relational calculus: containment for them becomesundecidable. We recover decidability in one important subcase though.
Additional contributions. An extended abstract of this paper appeared in [Barceló
et al. 2010]. The key new contributions are as follows. First, all results now come withcomplete detailed proofs. Second, all main questions left open in [Barceló et al. 2010]
have been solved. In particular:— [Barceló et al. 2010] asked whether the data complexity of ECRPQs with negation
is elementary. We give a negative answer to this question in Theorem 8.2.
— [Barceló et al. 2010] asked whether decidability results on CRPQs with lengthcomparisons extend to ECRPQs with length comparisons, and whether complexity bounds (in the case of decidability) remain the same. We give positive answers
to both questions in Theorem 8.5.
We also asked in [Barceló et al. 2010] whether the containment of a CRPQ in an
ECRPQ is decidable. While this paper was in preparation, a negative answer to thisquestion was given by [Freydenberger and Schweikardt 2011]; this is also discussed in
the paper.
Organization. In the next section, we present background material on graphs, regular relations and CRPQs. Section 3 introduces ECRPQs, while Section 4 discusses
their applications in more detail. In Section 5, we consider the evaluation of ECRPQs.
Section 6 deals with the data and combined complexity of ECRPQs. In Section 7 westudy query containment, and in Section 8 we consider extensions with negation, andwith non-regular features. Finally, Section 9 is devoted to related work while Section
10 summarizes the results obtained in the paper.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:5

2. PRELIMINARIESLabeled graphs and paths. Queries in our setting will be evaluated over labeledgraph databases, that naturally model semistructured data. Formally, if Σ is a finite
alphabet, then a Σ-labeled graph database G (or simply graph database if Σ is clear
from the context) is a pair (V, E), such that V is a finite set of nodes and E ⊆ V × Σ × V
is a set of directed edges labeled in Σ.
A path ρ between nodes v0 and vm in G is a sequence v0 a0 v1 a1 v2 · · · vm−1 am−1 vm ,where m ≥ 0, so that all the vi ’s are in V , all the aj ’s are letters of Σ, and (vi , ai , vi+1 )is in E for each i < m. The label of such a path ρ, denoted by λ(ρ), is the string
a0 · · · am−1 ∈ Σ∗ . We also define the empty path as (v, ε, v) for each v ∈ V ; the label ofsuch a path is the empty string ε.
Note that a Σ-labeled graph database G can be naturally viewed as a nondeterministic finite automaton (NFA) over alphabet Σ without initial and final states. Its states
are nodes in V , and its transitions are edges in E. We use this equivalence in several
constructions in the paper.
Regular relations. As our plan is to extend the notion of recognizability from string
languages to n-ary string relations, we now give the standard definition of regular
relations over Σ [Elgot and Mezei 1965; Frougny and Sakarovitch 1991; Blumensath
and Grädel 2000]. Regular relations are recognized by synchronous n-ary automata(also called letter-to-letter automata). These automata have n input tapes onto which
the input strings are written, followed by an infinite sequence of ⊥ symbols. At eachstep the automaton simultaneously reads the next symbol on each tape, terminatingwhen it reads ⊥ on each tape.
Formally, let ⊥ be a symbol not in Σ. We denote the extended alphabet (Σ ∪ {⊥})by Σ⊥ . Let s̄ = (s1 , . . . , sn ) be an n-tuple of strings over alphabet Σ. We construct astring [s̄] over alphabet (Σ⊥ )n , whose length is the maximum of the sj ’s, and whosei-th symbol is a tuple (c1 , . . . , cn ), where each ck is the i-th symbol of sk , if the length of
sk is at least i, or ⊥ otherwise. In other words, we pad shorter strings with the symbol⊥, and then view the n strings as one string over the alphabet   of n-tuples of letters. For
example, if s1 = aba and s2 = babb, then [(s1 , s2 )] = ab ab ab ⊥b , a string over Σ⊥ × Σ⊥ .
An n-ary relation S on Σ∗ is regular, if the set {[s̄] | s̄ ∈ S} of strings over alphabet (Σ⊥ )n is regular (i.e., accepted by an automaton over (Σ⊥ )n , or given by a regularexpression over (Σ⊥ )n ). We shall often use the same letter for both a regular expression over (Σ⊥ )n and the relation over Σ∗ it denotes, as doing so will not lead to any
ambiguity.
As an example, consider a binary relation s  s′ , saying that s is a prefix of s′ .
The automaton recognizing this relation accepts if it reads a sequence of letters of theform (a, a), for a ∈ Σ, possibly followed by a sequence of letters of the form (⊥, b), forb ∈ Σ. As another example, consider a binary relation el(s, s′ ) (equal length) sayingthat |s| = |s′ |. This relation is recognized by an automaton that accepts if it does notsee any letters involving the ⊥ symbol.
To understand which relations on strings are regular, it is often useful to provide amodel-theoretic characterization of this class. In the following we assume familiarity
with first-order logic (FO). Consider the FO-structure Muniv = hΣ∗ , , el, (Pa )a∈Σ iwith domain Σ∗ , where  and el are as above, and Pa (s) is true iff the last letter for s isa. This is known as a universal automatic structure due to the following [Blumensath
and Grädel 2000; Bruyère et al. 1994]: an n-ary relation S on Σ∗ is regular iff there
exists an FO formula ϕS (x1 , . . . , xn ) over Muniv such that S = {s̄ ∈ (Σ∗ )n | Muniv |=ϕS (s̄)}.
In particular, regular relations are closed under all Boolean combinations, product,
and projection. Furthermore, using the above result it is quite easy to show that an nACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:6

Pablo Barceló et al.

ary relation is regular, by exhibiting FO formulae defining them (see [Blumensath andGrädel 2000; Bruyère et al. 1994; Benedikt et al. 2003] for examples). For example,|s| < |s′ | is a regular relation definable by ϕ(x, y) = ∃y ′ (y ′  y ∧ y ′ 6= y ∧ el(y ′ , x)).
On the other hand, more elaborate techniques have to be used to prove that an n-ary
relation on Σ∗ is not regular. Examples of this kind include the binary relation ss ,that consists of all pairs (s1 , s2 ) such that s1 is a subsequence of s2 , and the ternary
relation that contains all tuples (s1 , s2 , s3 ) such that s1 s2 = s3 .
Conjunctive regular path queries. A basic querying mechanism for graphdatabases is the class of regular path queries [Abiteboul et al. 1999; Calvanese et al.
2002] that retrieve all pairs of objects in a graph database connected by a path conforming to some regular expression. However, it has been argued (e.g. [Milo and Suciu
1999]) that in order to make regular path queries useful in practice, they should be
extended with several features, one of them being the possibility of using conjunctionsof atoms. This extension yields the class of conjunctive regular path queries, which weformally define below (see also [Consens and Mendelzon 1990; Mendelzon and Wood
1995; Florescu et al. 1998; Calvanese et al. 2000]). We use a syntax that will be easy
to modify later to add the features of ECRPQs.
Fix a countable set of node variables (typically denoted by x, y, z, . . .), and a countable
set of path variables (denoted by π, ω, χ, . . .). A conjunctive regular path query (CRPQ)
Q over a finite alphabet Σ is an expression of the form:^^Ans(z̄) ←(xi , πi , yi ),Lj (ωj ),
(1)
1≤i≤m

1≤j≤t

such that(i). m > 0, t ≥ 0,(ii). each Lj is a regular expression over Σ,(iii). x̄ = (x1 , . . . , xm ), ȳ = (y1 , . . . , ym ) and z̄ are tuples of node variables,(iv). {π1 , . . . , πm } are distinct path variables,(v). {ω1 , . . . , ωt } are distinct path variables and each ωj is among the πi ’s, and(vi). z̄ is a tuple of node variables among x̄ and ȳ.
The atom Ans(z̄) is the head of the query, while the expression on the right of the ←is its body. The query Q is Boolean if its head is of the form Ans(), i.e. z̄ is the empty
tuple.
Intuitively, such a query Q selects tuples z̄ for which there exist values of the remaining node variables from x̄ and ȳ and paths πi between xi and yi whose labels satisfy
the regular expressions L1 to Lt . Formally, to define the semantics of CRPQs Q of theform (1), we first introduce a relation (G, σ, µ) |= Q, where:(i). σ is a mapping from x̄, ȳ to the set of nodes of a graph database G = (V, E), and(ii). µ is a mapping from {π1 , . . . , πm } to paths in G.
This relation holds iff µ(πi ) is a path in G from σ(xi ) to σ(yi ), for 1 ≤ i ≤ m, and thelabel of each path µ(ωj ) is in the language of Lj , for 1 ≤ j ≤ t.
We now define Q(G) to be the set of tuples σ(z̄) such that (G, σ, µ) |= Q. If Q is
Boolean, we let Q(G) be true if (G, σ, µ) |= Q for some σ and µ (that is, as usual, theempty tuple models the Boolean constant true, and the empty set models the Boolean
constant false).
Remark: Our syntax differs slightly from the usual CRPQ syntax in the literature(see e.g. [Florescu et al. 1998; Calvanese et al. 2000]). The reason is that we makeexplicit use of path variables in the queries – to treat CRPQs and ECRPQs in a uniform
manner – while the standard approach is to refer to paths only implicitly.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:7

3. EXTENDED CONJUNCTIVE REGULAR PATH QUERIESOur goal is to extend the class of CRPQs in two ways. First, we want to allow freepath variables in the heads of queries. Second, we want the bodies of queries to permit
checking relations on sets of paths rather than just conformance of individual paths toregular languages. This leads to the definition of a class of extended CRPQs.
Definition 3.1. An extended conjunctive regular path query (ECRPQ) Q over Σ isan expression of the form:^^Ans(z̄, χ̄) ←(xi , πi , yi ),Rj (ω̄j ),
(2)
1≤i≤m

1≤j≤t

such that(i). m > 0, t ≥ 0,(ii). each Rj is a regular expression that defines a regular relation over Σ,(iii). x̄ = (x1 , . . . , xm ) and ȳ = (y1 , . . . , ym ) are tuples of node variables,(iv). π̄ = (π1 , . . . , πm ) is a tuple of distinct path variables,(v). {ω̄1 , . . . , ω̄t } are distinct tuples of path variables, such that each ω̄j is a tuple ofvariables from π̄, of the same arity as Rj ,(vi). z̄ is a tuple of node variables among x̄, ȳ, and(vii). χ̄ is a tuple of path variables among those in π̄.
✷Note that this is similar to the definition of CRPQs; the main differences between(1) and (2) are:
— ECRPQs can check whether a tuple of path labels belongs to a regular relation,rather than just checking whether a path label belongs to a regular language; and— outputs of ECRPQs may contain both nodes and paths, while outputs of CRPQs
contain only nodes.
The head, the body, and the notion of Boolean ECRPQs V
are defined in the standard
way. The relational part of an ECRPQ Q of the form (2) is 1≤i≤m (xi , πi , yi ).
The semantics of ECRPQs is defined by a natural extension of the semantics of CRPQs. For an ECRPQ Q of the form (2), a graph database G and mappings σ from nodevariables to nodes and µ from path variables to paths, we write (G, σ, µ) |= Q if
— µ(πi ) is a path in G from σ(xi ) to σ(yi ), for 1 ≤ i ≤ m, and— for each ω̄j = (πj1 , . . . , πjk ), the tuple of strings consisting of labels ofµ(πj1 ), . . . , µ(πjk ) belongs to the relation Rj .
The output of Q on G (where the head of Q is Ans(z̄, χ̄)) is defined as
Q(G) = {(σ(z̄), µ(χ̄)) | (G, σ, µ) |= Q}.
Note that the implicit existential quantification over path variables that appear in
the body but not in the head is quantification over a potentially infinite set, as there
are infinitely many paths in any cyclic graph database.
From now on, we identify the class of CRPQs with the restriction of the class of
ECRPQs to queries that do not use regular relations of arity ≥ 2. This is more generalthan the definition of the previous section, since we now allow CRPQs to output paths.
It is easy to prove that the class of ECRPQs is strictly more expressive than the classof CRPQs.
P ROPOSITION 3.2. There is an ECRPQ that is not equivalent to any CRPQ.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:8

Pablo Barceló et al.

P ROOF. Let Q be a CRPQ with the head Ans(x, y). With each string s = a0 . . . an−1 ∈Σ+ , we associate a graph Gs with vertices v0 , . . . , vn and edges (v0 , a0 , v1 ), (v1 , a1 , v2 ),. . . , (vn−1 , an−1 , vn ). We let strings(Q) be {s ∈ Σ+ | (v0 , vn ) ∈ Q(Gs )}.
We now prove that strings(Q) is regular for every CRPQ Q. To see how the result
follows from this, consider an ECRPQ Q′
Ans(x, y) ← (x, π, z), (z, π ′ , y), a+ (π), b+ (π ′ ), el(π, π ′ ).
Q′ selects nodes connected by a path with the label am bm for some m > 0. Hencestrings(Q′ ) = {am bm | m > 0} is not regular, and thus Q′ is not equivalent to a CRPQ.
To show that strings(Q) is regular for a CRPQ Q, we explain how to construct an
NFA for it. Assume that Q uses (existentially quantified) variables z1 , . . . , zk . The automaton first guesses the order in which witnesses to these variables appear in Gs .
This imposes an order on variables x, y, and z̄, with x always coming first and y always coming last. For each pair of variables z and z ′ such that z comes before z ′ , the′query Q determines the language LQ
zz ′ that the path from z to z must belong to as
follows. Suppose we have clauses (z, π, z ′ ), L(π), (z ′ , π ′ , z), L′ (π ′ ) (absent clauses can always be added, with the path between nodes belonging to Σ∗ ). Then the language LQ
zz ′is L ∩ rev(L′ ), where rev(L′ ) is the regular language of reversals of strings in L′ .
The automaton for strings(Q), after making the initial guess of the ordering of variables, traverses the string, deciding when the witness for the next variable occurs. For
keeping notation simple in the explanation below, assume that the order is z1 , . . . , zk ,with none of the variables witnessed by the same element. The automaton starts simQQulating all automata for the languages LQ
xzi and Lxy . When the automaton for Lxz1 isin a final state, it may guess that this is the point where the witness for z1 occurs.
Q
Then it starts simulating all automata for the languages LQ
z1 zi , for i > 1, and Lz1 y , nowQwaiting to make a guess for z2 in a state where the automata for Lxz2 and LQ
z1 z2 arein accepting states. It continues like that; the final state will be those where all theQautomata for LQ
zi y and Lxy are in final states, confirming that the guesses have been
made correctly. It is routine to check that this construction is correct.
The result continues to hold for Boolean queries as well (see the electronic appendix).
4. APPLICATIONS OF EXTENDED CONJUNCTIVE REGULAR PATH QUERIESIn this section, we show that ECRPQs can express queries found in a wide variety
of application areas, including finding associations in semantic web (or linked) data,
pattern matching, approximate string matching, and biological sequence alignment.
Finding semantic web associations In a query language for RDF/S introduced in[Anyanwu and Sheth 2003], paths can be compared based on specific semantic associations. Edges correspond to RDF properties and paths to property sequences. A property
a can be declared to be a subproperty of property b, which we denote by a ≺ b. Two property sequences u and v are called ρ-isomorphic iff u = u1 , . . . , un and v = v1 , . . . , vn , forsome n, and ui ≺ vi or vi ≺ ui for every i ≤ n. Nodes x and y are called ρ-isoAssociatediff x and y are the origins of two ρ-isomorphic property sequences.
Finding nodes which are ρ-isoAssociated cannot be done in a query language supporting only conventional regular expressions, not least because doing so requires
checking that two paths are of equal length. However, pairs of ρ-isomorphic sequences
can be expressed using the regular relation R given by the following regular expression:∗[(a, b)
a,b∈Σ: (a≺b∨b≺a)

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:9

Then an ECRPQ returning pairs of nodes x and y that are ρ-isoAssociated can be
written as follows:
Ans(x, y) ← (x, π1 , z1 ), (y, π2 , z2 ), R(π1 , π2 )Path variables in an ECRPQ can also be used to return the actual paths found by thequery, a mechanism found in the query languages proposed in [Abiteboul et al. 1997;
Anyanwu and Sheth 2003; Holland et al. 2008; Kochut and Janik 2007]. For example,
in [Anyanwu and Sheth 2003] a ρ-query can take a pair of nodes u, v and return theproperty sequences relating them. This too can be expressed by an ECRPQ:
Ans(π1 , π2 ) ← (u, π1 , z1 ), (v, π2 , z2 ), R(π1 , π2 )where the regular relation R is defined as above.
Pattern matching Let Σ be a finite alphabet and V be a countable set of variables
such that Σ ∩ V = ∅. A pattern α is a string over Σ ∪ V. It denotes the language LΣ (α)
obtained by applying substitutions σ : V → Σ∗ to α. As we remarked already, suchlanguages need not even be context-free.
However, for each pattern α = α1 · · · αn , where every αi ∈ Σ ∪ V, we can define
an ECRPQ Qα (x, y) which finds pairs of nodes connected by a path in LΣ (α) (notethat this property is not definable by a CRPQ). Indeed, the relational part of Qα is(x0 , π1 , x1 ), . . . , (xn−1 , πn , xn ). If αi is a letter a ∈ Σ, then Qα contains the atom a(πi ),while if αi is a variable, then Qα contains the atom Σ∗ (πi ). Finally, to ensure equalityof variables, for every pair αi , αj which are the same variable, the query Qα contains
a conjunct πi = πj . It is clear that Qα indeed finds nodes connected by paths whoselabels are in LΣ (α).
In fact, ECRPQs can express queries corresponding to a larger class of languages
than the pattern languages. For instance, the language an bn cn , where a, b, c ∈ Σand n ∈ N, cannot be denoted by patterns, but can easily be denoted by an ECRPQ′
withS the help of the equal length predicate el (recall that el(π, π ) is a shorthand for( a,b∈Σ (a, b))∗ (π, π ′ )):Ans(x, y) ← (x, π1 , z1 ), (z1 , π2 , z2 ), (z2 , π3 , y), a∗ (π1 ), b∗ (π2 ), c∗ (π3 ), el(π1 , π2 ), el(π2 , π3 ).

Approximate matching and sequence alignment We treat approximate string
matching and (biological) sequence alignment together because both are based on thenotion of edit distance between strings. We consider the three edit operations of insertion, deletion and substitution, defined as follows. Let s, s′ ∈ Σ∗ . Applying an edit
operation to s yielding s′ can be modeled as a binary relation ❀ over Σ∗ such thatx ❀ y holds iff there exist u, v ∈ Σ∗ , a, b ∈ Σ, with a 6= b, such that one of the following
is satisfied:x = uav, y = ubv (substitution)x = uav, y = uv (deletion)x = uv, y = ubv (insertion)k

Let ❀ stand for the composition of ❀ with itself k times. The edit distance de (x, y)kbetween x and y is the minimum number k of edit operations such that x ❀ y.
We define a relation D≤k between strings as follows: (x, y) ∈ D≤k iff de (x, y) ≤ k. This
relation is regular (indeed, it is easy to see that it is accepted by a two-tape transducer,
and the difference between the lengths of x and y is bounded by k; then it follows fromthe fact that rational relations of such bounded distance are regular [Frougny and
Sakarovitch 1991]).
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:10

Pablo Barceló et al.

We now consider the use of edit distance in finding string (or sequence) alignments.
We can view an alignment of strings x and y over Σ at distance k as follows:x = x0 a1 x1 · · · ak xk
y = y0 b1 y1 · · · bk yk(3)such that (i) xi , yi ∈ Σ∗ and xi = yi for i ∈ [0, k], and (ii) ai , bi ∈ Σ ∪ {ǫ} and ai 6= bi , fori ∈ [1, k]. There is an alignment of x and y at distance k iff (x, y) ∈ D≤k . We call eachpair (xi , yi ) a match and each pair (ai , bi ) a mismatch if ai , bi ∈ Σ or a gap if ai or bi is
ǫ. (If we allow that ai = bi , then we align the strings with distance at most k).
We have shown above that we can use an ECRPQ to determine whether there exists
an alignment at distance k between two strings. However, we may also wish to return
the actual gaps and mismatches to the user. For that, we assume that each node hasan ǫ-labeled loop, and use an ECRPQ whose body is as follows^^^^(xi , πi , xi+1 ),(yi , ρi , yi+1 ),π2i = ρ2i ,R(π2i−1 , ρ2i−1 ),0≤i≤2k0≤i≤2k

0≤i≤k

1≤i≤k

where R is a finite language containing all pairs (a, b) in Σ ∪ {ǫ} with a 6= b. The headof the query contains the variables π2i−1 , ρ2i−1 , for 1 ≤ i ≤ k.
With the same approach, we can use ECRPQs to align not only pairs but arbitrary
tuples of sequences. Multiple sequence alignment is used to find the shared evolutionary origins of biological sequences.
In Section 8, we consider adding linear constraints on lengths of paths to ECRPQs.
Such functionality would give us the ability to compare various properties of alignments. Given an alignment between sequences x and y as shown in (3) above, thenumber of mismatches between x and y is given bym = Σki=1 |ai | · |bi |k−1
while the total number of gaps in x and y is given by k − m. If Σi=1
|xi | = 0, for example,
then all mismatches and gaps in x are consecutive. The number of non-gaps in x, forexample, is given by Σki=1 |ai |. Overall we have the relationshipk = Σki=1 |ai | + Σki=1 |bi | − Σki=1 |ai | · |bi |that is, k equals the number of non-gaps in x plus the number of non-gaps in y minus
the number of mismatches.
5. QUERY EVALUATION

We now describe how ECRPQs can be evaluated. We need to take care of two aspects
that distinguish ECRPQs from CRPQs: relations on paths, and path variables in the
output. To deal with the former, we define a notion of convolutions of graph databases
and queries, that reduces the evaluation of ECRPQs to the evaluation of CRPQs. To
deal with the latter, we produce an automaton construction that can represent both
nodes and paths in the output.
Convolutions of graphs and queries. We now present a construction that transforms a graph database G and an ECRPQ Q into a graph database G′ and a CRPQ Q′
with a single relational atom so that the evaluation of Q′ over G′ “coincides” (modulo
a simple translation) with the evaluation of Q over G.
Let G be a Σ-labeled graph database. By G⊥ we denote the Σ⊥ -labeled graphdatabase obtained from G by adding a ⊥-labeled loop to each node of G. We iteratively
define Gm , the m’th convolution of G, as follows:
G1 := G⊥ and Gm+1 = G⊥ ⊗ Gm ,ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:11

where ⊗ denotes the product of two graph databases. We use the symbol ⊗ rather
than × to indicate that this is not the standard product viewed as a graph/automaton
over the same alphabet, but rather a graph over the product of alphabets. Formally,
given a Σ1 -labeled graph database G1 = (V1 , E1 ) and a Σ2 -labeled graph database
G2 = (V2 , E2 ), their product G1 ⊗ G2 is the (Σ1 × Σ2 )-labeled graph database G =(V1 × V2 , E), where E contains edges ((v1 , v2 ), (a, b), (v1′ , v2′ )), such that (v1 , a, v1′ ) ∈ E1
and (v2 , b, v2′ ) ∈ E2 . Note that this makes Gm a (Σ⊥ )m -labeled graph database.
Consider an ECRPQ Q of the form:^^Ans(z̄, χ̄) ←(x2i−1 , πi , x2i ),Rj (π̄ j ).
(4)
1≤i≤m

1≤j≤t

Note that the variables x1 , . . . , x2m are not necessarily distinct. Let Sj (1 ≤ j ≤ t) be thenj -ary regular relation defined by Rj . We let LQ be the regular expression over (Σ⊥ )mthat represents the m-ary regular relation SQ = S1 (π̄ 1 ) ⊲⊳ . . . ⊲⊳ St (π̄ t ). Note that
SQ is indeed regular since the class of regular relations is closed under intersection,
projection, and product, and that relations of the form {s̄ | si = sj }, which are necessary
for defining joins, are regular as well.
The convolution of ECRPQ Q (4) is the CRPQ query Qc defined as
Ans(y, y ′ , π) ← (y, π, y ′ ), LQ (π).

(5)

mNote that this is indeed a CRPQ over (Σ⊥ ) -labeled graph databases. Moreover,Qc (Gm ), which consists of sets of tuples each comprising two m-tuples of nodes anda path in Gm , contains all the information we need to extract Q(G); below, we show
how to do this.
Letρ̄ = v̄0 ā0 v̄1 ā1 v̄2 · · · v̄p−1 āp−1 v̄p
be a path in Gm , where v̄i = (vi1 , . . . , vim ) for each i ≤ p is a node in Gm , and āi =m(a1i , . . . , ami ) for each i ≤ p − 1 is an element of (Σ⊥ ) . Then, for each j ≤ m, we letjρ̄(j) = v0j aj0 v1j · · · vp−1
ajp−1 vpj

be a path in G⊥ . Notice that this is indeed a path in G⊥ but not necessarily in G, as
it may contain ⊥-labeled loops. We then let ρ̄s (j) stand for the path obtained from ρ̄(j)by eliminating all such loops v⊥v; this is now a path in G.
The output of Qc (Gm ) consists of tuples of the form (ū, ū′ , ρ̄), where ū =(u1 , u3 , . . . , u2m−1 ) and ū′ = (u2 , u4 , . . . , u2m ) are nodes in Gm and ρ̄ is a path in Gm .
We say that (ū, ū′ ) are Q-compatible if, whenever xi = xj in Q, we have ui = uj , for alli, j ≤ 2m. We now define the Q-compatible output of Qc on Gm as the projection of theset(ū, ū′ ) is Q-compatible(ū, ū′ , ρ̄s (1), . . . , ρ̄s (m))
and (ū, ū′ , ρ̄) ∈ Qc (Gm )onto the attributes that appear in the head of Q in (4). That is, if xi is among z̄, we
project onto ui , and if πj is among χ̄, we project onto ρ̄s (j).
From all the previous remarks we immediately obtain the following:
T HEOREM 5.1. Let Q be an ECRPQ of the form (4) and G a graph database. Thenthe Q-compatible output of the convolution CRPQ Qc on Gm coincides with Q(G).
Representing paths in the answer. Since ECRPQs can return paths, the answer
to a query may be infinite (for example, if there is a cycle in the input graph, then we
have infinitely many paths). In such cases we need to return a compact representation
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:12

Pablo Barceló et al.

of the set of answers to an ECRPQ Q . It turns out that for each tuple of nodes v̄, theset {χ̄ | (v̄, χ̄) ∈ Q(G)} is a regular relation, and an automaton defining this relation
can be constructed in time polynomial in the size of the input graph. We now present
this construction.
Consider an ECRPQ Q of the form (2), i.e.,^^Ans(z̄, χ̄) ←(xi , πi , yi ),Rj (π̄ j ),
1≤i≤m

1≤j≤p

a graph database G = (V, E), and a tuple v̄ of nodes such that |v̄| = |z̄|. We let Q(G, v̄)stand for the set {ρ̄ | (v̄, ρ̄) ∈ Q(G)}.
Let |χ̄| = k. We say that a path π̄ in Gk represents a k-tuple of paths (ρ1 , . . . , ρk ) in
Q(G, v̄) if π̄s (j) = ρj for each j ≤ k and the label of π̄ is precisely [λ(ρ1 ), . . . , λ(ρk )].
Recall that λ(·) stands for the label of a path; in particular, each λ(ρj ) is a string inΣ∗ . Recall also that [·] transforms a tuple of k strings into a string of k-tuples. Noticethat such a path π̄ is unique for the tuple (ρ1 , . . . , ρk ), and in turn determines the tuple(ρ1 , . . . , ρk ) uniquely.
P ROPOSITION 5.2. For each ECRPQ Q with the head Ans(z1 , . . . , zℓ , χ1 , . . . , χk ),graph database G = (V, E) and tuple v̄ ∈ V ℓ , one can construct, in polynomial time(G,v̄)
in |E|, an automaton AQ
over the alphabet V k ∪ (Σ⊥ )k that accepts precisely the
representations of all the tuples of paths in Q(G, v̄).
In order to prove this proposition we use techniques similar to those in the proof of
Theorem 6.3. Therefore, we postpone its proof until we prove Theorem 6.3.
6. COMPLEXITY OF QUERY EVALUATIONThe reduction from ECRPQs to CRPQs gives us fairly easy upper bounds: one has tocompute the convolution and evaluate a CRPQ over it. Using NL OGSPACE and NP
bounds on the data and combined complexity of CRPQs, we conclude that the data
complexity of ECRPQs is in P TIME, and their combined complexity is in E XPTIME.
But can we do better?
It turns out that we can. For data complexity, we can lower the bound to
NL OGSPACE: that is, the data complexity of CRPQs and ECRPQs is the same. For
combined complexity, however, relations do make a difference: we show P SPACEcompleteness of combined complexity. In the relational world, there are many techniques for lowering the NP combined complexity of conjunctive queries, typically byconsidering acyclic queries. This approach works for CRPQs, for which we show that
acyclic queries can be evaluated in P TIME. However, when we move to ECRPQs,
acyclicity does not lower the complexity. We then show that the techniques inspiredby modeling infinite-state systems for verifying their temporal properties give us NPcompleteness of combined complexity of classes of ECRPQs, matching the combinedcomplexity of relational CQs.
6.1. Data complexity

If we fix a query Q over Σ, the problem we look at is the following:
P ROBLEM:
I NPUT:Q UESTION:ECRPQ- EVAL(Q)A Σ-labeled graph database G, a tuple v̄ ofnodes in G and a tuple ρ̄ of paths in G.
Does (v̄, ρ̄) belong to Q(G)?

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:13

The convolution technique, if applied carefully, gives us an NL OGSPACE upperbound. To evaluate the convolution query Qc over Gm , we use an “on the fly” evaluation of the emptiness algorithm for the cross product of the automaton Gm , with aguessed assignment for the initial and final states, and the automaton AQ that accepts
the language LQ of the convolution query. In the proof we still have to deal with sometechnical details (for instance, the presence of paths in the output for non-Boolean
queries).
T HEOREM 6.1.
NL OGSPACE.

For each ECRPQ Q, the problem ECRPQ- EVAL(Q) is in

For reasons that will become clear later, we postpone the proof of this theorem until
immediately after the proof of Theorem 6.3.
Since the problem can be NL OGSPACE-hard even for regular path queries that do
not make use of path variables in the head [Consens and Mendelzon 1990], we also
have a matching lower bound. Also note that when query Q is fixed, Proposition 5.2
tells us that there is a polynomial-size family of automata that represents the whole
space of answers for Q over G.
6.2. Combined complexity

We now turn to the combined complexity, that is, query evaluation that takes both thegraph database and the query as input:
P ROBLEM:
I NPUT:Q UESTION:ECRPQ- EVAL
A finite alphabet Σ, a Σ-labeled graphdatabase G, an ECRPQ Q over Σ, a tuplev̄ of nodes in G and a tuple ρ̄ of paths in G.
Does (v̄, ρ̄) belong to Q(G)?

The problem CRPQ- EVAL is the restriction to when the query Q in the input is a
CRPQ.
We start with the easier problem CRPQ- EVAL. It appears to be a folklore result(although we could not find it stated explicitly in the literature) that, without pathvariables in the head (i.e., the empty tuple ρ̄) this problem is NP-complete. For thesake of completeness we present a proof (in the appendix) of a slightly more general
result that handles free path variables as well.
P ROPOSITION 6.2. CRPQ- EVAL is NP-complete.
However, adding regular relations to queries makes the query evaluation problem
harder (at least under widely-held complexity theoretical assumptions). Notice that
this is in stark contrast with what happens in the same case to the data complexity ofthe problem, where relations on paths do not increase the complexity.
T HEOREM 6.3. ECRPQ- EVAL is P SPACE-complete. It remains P SPACE-hard evenwhen restricted to Boolean ECRPQs.
P ROOF. We first prove membership. Let Q be an ECRPQ of the form^^Ans(z̄, χ̄) ←(xi , πi , yi ),Rj (ω̄j ),
1≤i≤m

1≤j≤t

v̄ a tuple of nodes in G such that |v̄| = |z̄| and ρ̄ a tuple of paths in G such that|ρ̄| = |χ̄|. From Proposition 5.1, checking whether (v̄, ρ̄) ∈ Q(G) is equivalent to checking whether (v̄, ρ̄) belongs to the Q-compatible output of Qc over Gm , where Qc is the
convolution Ans(y, y ′ , π) ← (y, π, y ′ ), LQ (π) of Q as defined in Section 3. We show that
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:14

Pablo Barceló et al.

the latter can be done in nondeterministic polynomial space in the size of Q and G.
Then membership will follow from Savitch’s Theorem, that shows that P SPACE equals
NP SPACE. First, we notice the following:
L EMMA 6.4. It is possible to construct from Q an automaton AQ , of size at most
exponential in the size of Q, such that AQ accepts exactly the language defined by LQ .
P ROOF. Recall that LQ is defined over (Σ⊥ )m . Further, assume that Rj is definedover (Σ⊥ )nj , nj > 0, and that ω̄j = (πj1 , . . . , πjnj ). Each regular expression Rj (1 ≤ j ≤ t)
can be transformed in polynomial time in the size of Q into an equivalent NFA Aj .
Assume that pj ≥ 0 is the number of states of Aj , for each 1 ≤ j ≤ t. Then we can define
the NFA AQ as the one that on string w̄ = (a11 , . . . , a1m ) · · · (aℓ1 , . . . , aℓm ) over alphabet(Σ⊥ )m does the following: It checks that for each 1 ≤ j ≤ t the string(a1j1 , . . . , a1jn ) · · · (aℓj1 , . . . , aℓjn )
j

j

nj

over alphabet (Σ⊥ ) is accepted by Aj . If that is the case, AQ accepts w̄; otherwise, it
rejects.
Clearly, AQ can be constructed by taking the cross product of all the Aj ’s and thenprojecting each coordinate on the corresponding indexes from {1, . . . , m}. That is, as′sume that (r1 , . . . , rm ) and (r1′ , . . . , rm
) are two states of AQ , where rj is a state of Aj ,for each 1 ≤ j ≤ t. Then there is a transition in AQ labeled (a1 , . . . , am ) ∈ (Σ⊥ )m if andonly if there is a transition labeled (aj1 , . . . , anj ) from rj to rj′ in Aj , for each 1 ≤ j ≤ t.
m
Thus, AQ has at most max {pj | 1 ≤ j ≤ t} states. Since the alphabet of AQ is alsoof exponential size with respect to Q, we get that AQ is of size at most exponential in
the size of Q.
Notice that, since AQ is of exponential size in the size of Q, we can assume without loss of generality that each state of AQ is of polynomial size in Q. We can thendefine an algorithm that checks in nondeterministic polynomial space whether (v̄, ρ̄)
belongs to the Q-compatible output of Qc on Gm as follows. The algorithm first guessesa polynomial space assignment σ from {y, y ′ } to the nodes of Gm . Then the algorithm
checks that σ “respects” v̄, i.e. for each z in z̄, if the value in v̄ that corresponds to thevariable z is v, then σ(z) = v. Afterwards, the algorithm checks whether (σ(y), σ(y ′ )) is
Q-compatible. All this can be done in polynomial space.
Recall that Gm (σ(y), σ(y ′ )) is the NFA that is obtained from Gm by fixing σ(ȳ) andσ(ȳ ′ ) as initial and final states, respectively. It is not hard to see that Gm (σ(y), σ(y ′ ))is of exponential size in G and Q, but the size of each one of its states is polynomialin the size of G and Q. Further, (v̄, ρ̄) belongs to the Q-compatible output of Qc over
Gm if and only if there is a string ā1 · · · āp over alphabet (Σ⊥ )m that is accepted by
AQ × Gm (σ(y), σ(y ′ )) and that “respects” ρ̄; this means that there is a run(q0 , ū0 ), . . . , (qp , ūp )m′of AQ × G (σ(y), σ(y )) over ā1 · · · āp , such that (1) each qi (0 ≤ i ≤ p) is a state of AQ ,(2) each ūi (0 ≤ i ≤ p) is a state of Gm (σ(y), σ(y ′ )) (i.e. a node of Gm ), (3) q0 and qp are
an initial and final state of AQ , respectively, (4) ū0 and ūp are the initial and final stateof Gm (σ(y), σ(y ′ )), respectively (i.e. ū0 = σ(y) and ūp = σ(y ′ )), and (5) if µ̄ is the pathū0 ā1 ū1 ā2 ū2 · · · ūp−1 āp−1 ūp in Gm , then for each 1 ≤ j ≤ m and variable χ in χ̄ such thatχ = πj it is the case that µ̄s (j) = ρ, assuming that ρ is the value that corresponds to χin the tuple ρ̄.
As we have mentioned, both AQ and Gm (σ(y), σ(y ′ )) are of exponential size. However, each state in AQ × Gm (σ(y), σ(y ′ )) is of polynomial size. Thus, checking whether
there is a string in AQ × Gm (σ(y), σ(y ′ )) that “respects” ρ̄ can be done in nondeterACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:15

ministic P SPACE by using a standard “on-the-fly” construction of AQ × Gm (σ(y), σ(y ′ ))as follows: Whenever the emptiness algorithm wants to move from a state r1 of
AQ × Gm (σ(y), σ(y ′ )) to a state r2 , it guesses r2 and checks whether there is a transition from r1 to r2 . Once this is done, the algorithm can discard r1 and follow from r2 .
Thus, at each step, the algorithm needs to keep track of at most two states, each one ofpolynomial size. Further, it is not hard to see that the extra constraint for the emptiness algorithm of finding a string that respects ρ̄ does not increase the complexity.
For hardness we use a polynomial-time reduction from the problem of regular expression intersection (REI), which is known to be P SPACE-complete [Kozen 1977]. This
problem is defined as follows: Given m regular expressions R1 , . . . , Rm over a common
alphabet Σ = {a1 , . . . , an }, is there a string w ∈ Σ∗ that belongs to Ri for each i ∈ [1, m]?
It follows from [Kozen 1977] that REI remains P SPACE-complete even for a fixed Σ.
Let R = R1 , . . . , Rm be an instance of the REI problem, and assume that the common
alphabet of the Ri ’s is Σ = {a1 , . . . , an }. We construct (in polynomial time) an instance(Σ, GR , QR ) of the ECRPQ evaluation problem as follows:— QR is the Boolean queryAns() ←^

(xi , πi , yi ), Ri (πi ),i∈[1,m]^πi = πj ,i,j∈[1,m]such that the elements in the set {x1 , . . . , xm , y1 , . . . , ym } are pairwise distinct. That
is, QR asks whether there exist nodes u1 , . . . , um , v1 , . . . , vm and paths ρ1 , . . . , ρm in
the graph, such that ρi (i ∈ [1, m]) is path from ui to vi and λ(ρi ) belongs to Ri , andfor each i, j ∈ [1, m], λ(ρi ) = λ(ρj ).
— GΣ
R = (V, E) is the Σ-labeled graph database such that V = {v1 , . . . , vn+1 } and E
contains all tuples of the form (vi , a, vj ), such that (1) i, j ∈ [1, n + 1] and i 6= j, and(2) a = aj−1 if i < j, and a = aj otherwise. Notice that for each node v in GΣR andstring w ∈ Σ∗ , there is a path ρ in GΣ
R that starts in v and such that λ(ρ) = w.
We prove next that there is a string w ∈ Σ∗ that belongs to Ri for each i ∈ [1, m]Σ
iff QR (GΣR ) = true. Assume first that QR (GR ) = true. Then there exist nodes
u1 , . . . , um , v1 , . . . , vm and paths ρ1 , . . . , ρm in GΣ
R , such that (1) ρi (1 ≤ i ≤ m) is apath from ui to vi , (2) λ(ρi ) belongs to Ri , and (3) for each 1 ≤ i, j ≤ m it is the casethat λ(ρi ) = λ(ρj ). In particular, the string λ(ρi ) belongs to Ri , for each i ∈ [1, m]. On
the other hand, assume that w ∈ Σ∗ belongs to each Ri . Let ρ be an arbitrary path thatstarts in v1 and such that λ(ρ) = w. Assume that ρ goes from v1 to v. Then clearly there
exist nodes u1 , . . . , um , v1 , . . . , vm (namely, ui = v1 and vi = v for each 1 ≤ i ≤ m) andpaths ρ1 , . . . , ρm in GΣ
R (namely, ρi = ρ for each 1 ≤ i ≤ m), such that (1) ρi (1 ≤ i ≤ m)is path from ui to vi , (2) λ(ρi ) belongs to Ri , and (3) for each 1 ≤ i, j ≤ m it is the casethat λ(ρi ) = λ(ρj ). This implies that QR (GΣ✷R ) = true.
By adapting the previous machinery we can now give a proof of Proposition 5.2 andTheorem 6.1.
P ROOF OF T HEOREM 6.1. The same “on-the-fly” algorithm used in the proof of Theorem 6.3 works. Notice, however, that in this case (that is, with Q assumed to be fixed)
the size of AQ × Gm (σ(y), σ(y ′ )) is polynomial. Further, each one of its states can be
represented with O(log |G|) bits. This implies that the nondeterministic algorithm of
the previous proof works in NL OGSPACE.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:16

Pablo Barceló et al.

P ROOF OF P ROPOSITION 5.2. Let Q be a fixed ECRPQ of the form^^Ans(z1 , . . . , zℓ , χ1 , . . . , χk ) ←(xi , πi , yi ),Rj (ω̄j ),
1≤i≤m

1≤j≤t

G = (V, E) be a Σ-labeled graph database, v̄ = (v1 , . . . , vℓ ) be a tuple of nodes in G, andQc be the convolution Ans(y, y ′ , π) ← (y, π, y ′ ), LQ (π) of Q as defined in Section 3.
First, define Θ as the set of all those mappings σ from {y, ȳ ′ } to Gk that “respect” v̄
and that satisfy that (σ(y), σ(y ′ )) is Q-compatible. Then
S construct, in polynomial timein |E|, the NFA A that accepts the intersection of σ∈Θ Gk (σ(y), σ(y ′ )) and the NFA
AQ that recognizes LQ . It is not hard to see that from A it is possible to construct, in
polynomial time, an automaton B over alphabet V k ∪ (Σ⊥ )k , that accepts exactly thosestrings v̄0 ā1 v̄1 ā2 · · · v̄p−1 āp v̄p such that (1) each v̄i (0 ≤ i ≤ p) is a node in V k , (2) eachāi (1 ≤ i ≤ p) is an element of (Σ⊥ )k , and (3) v̄0 , . . . , v̄p is a successful run of A overā1 · · · āp (that is, in particular v̄0 and v̄p are initial and final states of A, respectively).
Finally, by projecting on the corresponding path variables, it is possible to construct in(G,v̄)
polynomial time in |B| the NFA AQ
that accepts exactly the restriction of the paths
accepted by B to the variables in χ̄. Thus, the whole process takes polynomial time and(G,v̄)
the size of AQ
is polynomial in |E|.
6.3. Restrictions

We now look at various approaches to lowering the complexity of query evaluation.
Acyclic queries. It is, of course, a classical result of relational theory that acyclic
conjunctive queries are tractable with respect to combined complexity. What if we require that the relational part of an (E)CRPQ be acyclic? Formally,Vwe say that an
ECRPQ or a CRPQ Q is acyclic if the graph HQ of its relational part 1≤i≤m (xi , πi , yi ),containing precisely the edges (xi , yi ) for i ≤ m, is acyclic.
The following result shows that the situation is similar for CRPQs but drasticallydifferent for ECRPQs: the restriction works for the former but not for the latter. In
fact, allowing only unary regular relations is precisely the boundary of tractability forthe query evaluation problem restricted to acyclic ECRPQs.
T HEOREM 6.5.
— The problem CRPQ- EVAL is in P TIME, if restricted to the class of acyclic CRPQs.
— The problem ECRPQ- EVAL is P SPACE-complete, even if restricted to the class ofacyclic Boolean ECRPQs, over a fixed alphabet Σ, that make use of regular relationsof arity at most 2.
P ROOF. The second result uses the reduction of Theorem 6.3, which requires
Boolean acyclic queries and binary relations over a fixed alphabet. Next we prove thefirst result.
Let Σ be a finite alphabet, G = (V, E) a Σ-labeled graph database, Q a CRPQ over Σof the form^^Ans(z̄, χ̄) ←(xi , πi , yi ),Lj (ωj ),
1≤i≤m

1≤i≤t

v̄ a tuple of nodes in G and ρ̄ a tuple of paths in G. We assume without loss of generalitythat |v̄| = |z̄| and |χ̄| = |ρ̄|.
We start by transforming Q into a Boolean query Q′ that makes use of constants fornodes and paths as follows. First, instantiate the node variables in the body of Q whichappear in z̄ with the corresponding nodes from v̄. In the same way, instantiate the pathvariables in the body of Q which appear in χ̄ with the corresponding paths from ρ̄.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:17

Now, for each i ∈ [1, m], the combination of (xi , πi , yi ) and the Lj (ωj )’s can be evaluated in P TIME to yield a binary relation ri over pairs of nodes v1 and v2 such that
(v1 , v2 ) ∈ ri iff there is a path from v1 to v2 in G satisfying Rj , for each 1 ≤ j ≤ t suchthat ωj = πi . This can be done using the standard technique of forming an NFA torecognize the intersection of the languages denoted by Ri and G, except that G is now
viewed as an automaton in which every node is both an initial and final state (unlessxi and/or yi has been instantiated to a node in G, in which case the initial and/or final
states are restricted accordingly; and unless πi has been instantiated to a path in G,
in which case we have to restrict the initial an/or final states accordingly, as well as
checking whether the label of such a path satisfies Rj , for each 1 ≤ j ≤ t such thatωj = πi ).
It is not hard to see then that the problem of checking whether (v̄, ρ̄) ∈ Q(G) is equivalent to the problem of evaluating an acyclic conjunctive query Q′ , whose size is linear
in the size of Q, over the relational database that contains the relations r1 , . . . , rm .
Since each ri can be constructed in polynomial time, and the evaluation of acyclic conjunctive queries over relational databases is known to be in P TIME, we conclude thatthe problem of evaluating acyclic CRPQs over graph databases is in P TIME.
Numerical representations of regular relations. The idea here comes from thefield of verification of infinite-state systems, where regular languages are used to represents possible states of such systems (e.g., strings of states of an unbounded numberof components of a system) and regular relations represent transitions between them
[Abulla et al. 2003]. While many problems related to verifying such systems are computationally hard or even undecidable, they become easier if an abstraction of a regular
language presentation is used. Often such abstractions are in the form of definability in linear integer arithmetic, see, e.g., [Verma et al. 2005; Ibarra et al. 2002]. We
shall now look at a similar idea of abstracting regular relations in connection with the
ECRPQ evaluation problem.
We first look at relations that consider only the lengths of strings. More precisely,with each n-ary regular relation R, we associate a regular relation Rlen defined as{(s1 , . . . , sn ) | ∃(s′1 , . . . , s′n ) ∈ R : |si | = |s′i | for all i}.
Now, given an ECRPQ Q, we define Qlen as Q in which each relation R is replaced by
Rlen . This is still an ECRPQ due to the following:
L EMMA 6.6. If R is a regular relation, then so is Rlen .
It turns out that with this abstraction, we can lower the combined complexity to thatof ordinary relational conjunctive queries.
T HEOREM 6.7. The problem of checking, for a graph database G, a tuple ā, and an
ECRPQ Q, whether ā ∈ Qlen (G), is NP-complete.
We now prove both Lemma 6.6 and Theorem 6.7.
P ROOF. We start with a few observations about relations of the form Rlen . Let R
be an m-ary relation over Σ. By P we denote an ordered partition of {1, . . . , m}, i.e.,a partition of {1, . . . , m} into blocks B1 , . . . , Bk for some k ≤ m with an order B1 <. . . < Bk on them. Given an m-tuple s̄ = (s1 , . . . , sm ) of strings over Σ, we say that it
length-conforms to P if two conditions hold:— if i, j are in the same block of the partition P, then |si | = |sj |; and— if i ∈ Bp and j ∈ Bq with p < q, then |si | < |sj |.
By ℓ(s̄) we denote the tuple (|s1 |, . . . , |sm |) ∈ Nm , and by ℓP (s̄), if s̄ length-conforms
to P, the following tuple (n1 , . . . , nk ):ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:18

Pablo Barceló et al.

— n1 = |sj | for an arbitrary j ∈ B1 ;— np+1 = |sj | − |si | for arbitrary sj ∈ Bp+1 and si ∈ Bp .
Since s̄ length-conforms to P, this is unambiguous.
Recall that a unary automaton is an automaton over a one-letter alphabet; its transitions therefore can be viewed as a binary relation on the set of states. Given such an
automaton A, it accepts strings of the form an for the single-letter a, which we identify
with numbers, writing instead that A accepts n ∈ N.
We now need the following claim. Assume that R is given by a letter-to-letter NFA
AR . Let A be an arbitrary automaton; by A(I, F ) we mean an automaton with the sametransitions as A, but initial states I and final states F . Now if we have a sequence
A1 , . . . , Ak of unary automata, we say that it accepts n̄ = (n1 , . . . , nk ) via a tuple ofstates (q1 , . . . , qk−1 ) if there is an initial state q0 of A1 and a final state qk of Ak so thatnj is accepted by Aj (qj−1 , qj ), for all j ≤ k. Note that each state qj , for 1 ≤ j < k, must
be shared by Aj and Aj+1 .
C LAIM 6.7.1. Given a regular relation R over m-ary tuples of strings, and an ordered partition P of {1, . . . , m} with k blocks, there exist unary automata A1 , . . . , Ak
and sets of states S1 , . . . , Sk , which can be effectively constructed from AR and P, suchthat, for each s̄ that length-conforms to P,s̄ ∈ Rlen ⇔ ℓP (s̄) is accepted by A1 , . . . , Ak via some tuple (q1 , . . . , qk−1 ),where each qj is in Sj , for j ≤ k.
We now prove the claim. First note that membership in Rlen for tuples that lengthconform to P depends only on ℓP (s̄): if both s̄ and s̄′ length-conform to P and ℓP (s̄) =ℓP (s̄′ ), then s̄ ∈ Rlen iff s̄′ ∈ Rlen .
We also need the following observation. We say that from a state q of AR , a final
state is reachable by (P, j) if it is reachable by reading a string that starts with lettersthat have ⊥ in positions corresponding to Bi for i < j and letters from Σ in positions
corresponding to Bp for p ≥ j, then continues with letters that have ⊥ in positions
corresponding to Bi for i < j + 1 and letters from Σ in positions corresponding to Bp
for p ≥ j + 1, and so on, until it finally reads a sequence of letters having ⊥ in positions
corresponding to B1 , . . . , Bk−1 and letters from Σ in positions on Bk , before reaching a
final state. By the standard reachability analysis of the automaton graph we can seethat the set of such states can be computed in polynomial time in the size of AR .
We now construct the sequence of unary automata A1 , . . . , Ak inductively as follows.
The states of all the automata will be the states of AR . The transitions will be subsets
of transitions of AR .
— Automaton A1 , while reading its input, guesses at each step a letter in Σm (i.e., no ⊥symbols) and simulates a transition of AR . Its accepting states are those (reachable)
states from which a final state of AR is reachable by (P, 2).
— The automaton Ap+1 has as its set of initial states the final states of Ap . It simulates
AR on letters that have ⊥ in positions corresponding to B1 , . . . , Bp , and symbols in Σ
in positions corresponding to Bp+1 , . . . , Bk (i.e., it guesses such a letter for each input
symbol). Its accepting states are those from which a final state of AR is reachableby (P, p + 2). If p + 1 = k, its accepting states are the reachable final states of AR .
Suppose now s̄ ∈ Rlen . Then ℓP (s̄) is accepted by A1 , . . . , Ak via some tuples of states:
simulating AR gives us an accepting run. Conversely, if ℓP (s̄) is accepted by A1 , . . . , Ak
via a tuple of states (q1 , . . . , qk−1 ), from the description of the Ai ’s we get a tuple ofstrings s̄′ (the guessed strings) so that s̄′ is accepted by AR and ℓP (s̄) = ℓP (s̄′ ); thus s̄
is accepted by Rlen . This proves the claim.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:19

We now use the fact that the language accepted by a unary NFA A is a union of at
most quadratically many arithmetic progressions (i.e., sets θ = a + bN = {a + bn | n ∈N}). This was first claimed in [Chrobak 1986], and a mistake in that paper was recently
fixed in [To 2009], which also showed that such a set of arithmetic progressions can beconstructed in polynomial time. This, together with Claim 6.7.1, gives us the following.
C LAIM 6.7.2. Given a regular relation R over m-ary tuples of strings, and an ordered partition P of {1, . . . , m} with k blocks, there exist sets Θ1 , . . . , Θk of arithmetic
progressions, which can be constructed in polynomial time, such that there is a set
J ⊆ Θ1 × . . . Θk satisfying the following:s̄ ∈ Rlen ⇔ ∃ (θ1 , . . . , θk ) ∈ J : ni ∈ θi for all i ≤ k,where ℓP (s̄) = (n1 , . . . , nk ). Moreover, given a tuple (θ1 , . . . , θk ) ∈ Θ1 , . . . , Θk , one cancheck in polynomial time whether it belongs to J.
Note that each of the claims implies Lemma 6.6. We now prove Theorem 6.7 using
these claims.
Let G = (V, E) be a Σ-labeled graph database, and Q an ECRPQ in which
all relations R have been replaced by Rlen , i.e., a query of the form Ans(z̄, χ̄) ←V jVi (xi , πi , yi ), j Rlen (π̄j ). Given a tuple of nodes and a tuple of paths, we need to check
whether they belong to the output of the query. The first step of an NP (combined complexity) algorithm is of course to guess the witness nodes. Thus, we need to show how
to check, for tuples ā, b̄, ā′ , b̄′ of nodes with |ā| = |b̄| and |ā′ | = |b̄′ | as well as a tuple
V j
VV(π̄j ) holds for someof paths ρ̄ with |ρ̄| = |ā′ | whether i (ai , πi , bi ), i′ (a′i , ρi , b′i ), j Rlen
tuple of paths π̄. Since the second conjunct is trivially verifiable in polynomial time,
our goal is thus to show how to check the existence of a tuple of paths π̄ so that^^ j(ai , πi , bi ),Rlen (π̄j )
i≤p

j≤t

holds. Here each π̄j is a tuple of paths among the πi ’s and those in ρ̄.
For this, we proceed as follows. We guess an ordered partition P of the set of indicesjof π̄ such that ρ̄ length-conforms to P. Next, for each of the relations Rlen
, we compute,as in Claim 6.7.2, the sets Θi ’s of arithmetic progressions and guess the set J that willjwitness membership in Rlenfor the given ordered partition. We then verify in polynomial time that each guessed tuple of arithmetic progressions belongs to J. Finally, foreach of the paths we use, we guess the points on that path whose distance from thestarting point of the path are the same as the length of the paths of smaller length. For
example, if we have 4 paths π1 , . . . , π4 and an ordered partition Π = {{1, 2}, {3}, {4}},we would guess, for a subgoal (a, π4 , b), nodes a′ and a′′ so that the distance from a to a′will be the same as the lengths of π1 and π2 , and the distance from a to a′′ will be thesame as the length of π3 . Now it remains to check that we can find paths π̄ that satisfy
these guesses.
But now it follows from Claim 6.7.2 that the latter can be solved if we can solve thefollowing problem: given nodes a1 , . . . , an in a graph database, arithmetic progressions
θij for i, j ≤ n, and a family S of subsets of {1, . . . , n} × {1, . . . , n}, do there exist paths
πij between ai and aj for i, j ≤ n so that |πij | ∈ θij and whenever (i, j) and (i′ , j ′ ) arein the same set of S, we have |πij | = |πi′ j ′ |? Indeed, by guessing intermediate points ofpaths, we eliminated the need for inequality comparisons between the length of paths.
To solve this problem, we view the graph database as unary automata Aij , for every
i, j ≤ n, where ai is the initial state and aj is the final state, and the transitions are
the graph edges themselves. Each such automaton can be converted in polynomial time
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:20

Pablo Barceló et al.

ij
into a union of arithmetic progressions cij
k + dk N so that the lengths of paths between
ai and aj are precisely the numbers that belong to one of the progressions. Then the
problem above is solvable iff the following Presburger formula

 ^ _
^
 ^
ij
′
′
(6)
∃x11 . . . ∃xnn
x=x∃n (cij
+
d
kn
=
x
)∧θ
(x
)
∧
ij
ij
ij
ij
ij
k
i,j≤n

S∈S (i,j),(i′ ,j ′ )∈Skis satisfiable. Indeed, the witnesses xij ’s then are the lengths of the witness paths
between ai and aj , for i, j ≤ n. In (6), for an arithmetic progression θ = a + bN, wherea and b are integer constants, by θ(x) we mean the formula ∃n(x = a + bn).
As (6) is an existential Presburger formula, its satisfaction can be checked in NP. In
ijfact one can guess, for each i, j, a particular arithmetic progression cij
k + dk N that will
witness the satisfaction of the formula, and then (6) is transformed into an instanceof integer linear programming, for which witnesses of polynomial size can be guessed
according to [Papadimitriou 1981].
It is straightforward to observe that all the guesses can be combined and the entire
procedure runs in NP, thus completing the proof.
It also follows from Theorem 6.7 that the combined complexity of queries Qlen (i.e.,
when the input contains Qlen rather than Q) is NP-complete as well.
Another standard way of creating an abstraction of R is to count the numbers of occurrences of symbols; this, however, leads to non-regular languages and relations (e.g.,
if we only count numbers of occurrences of letters, strings from (ab)∗ will be transformed into strings in which the number of a’s equals the number of b’s). Nonetheless,
we can prove an NP upper bound for such nonregular relations; they will be consideredin the next section when we look at extensions of ECRPQs.
Repetition of path variables In the definitions of CRPQs and ECRPQs, repetition of path variables is allowed in neither the relational parts nor the regular languages/relations. For instance, we cannot write (x, π, y), (x′ , π, y ′ ), nor can we write
R1 (ω̄), R2 (ω̄). We refer to these as relational repetitions and regular repetitions, respectively. What happens if these are allowed? It turns out that the complexity of ECRPQs
is not affected, but the combined complexity of CRPQs jumps to that of ECRPQs, nomatter what kind of repetition is allowed.
P ROPOSITION 6.8. The problem ECRPQ- EVAL remains in P SPACE for ECRPQs
with any kind of repetition, while the problem CRPQ- EVAL becomes P SPACE-complete
even for Boolean acyclic CRPQs with either relational or regular repetitions.
P ROOF. The proof of Theorem 6.3 can be easily adapted to show that the problem
ECRPQ- EVAL remains in P SPACE for ECRPQs with any kind of repetition. For the
lower bound we use the same reduction from REI used in the proof of Theorem 6.3, but
this time we construct the CRPQ^
Ans() ←
(xi , π, yi ), Ri (π),
1≤i≤mthat repeats path variables.
7. QUERY CONTAINMENTThe task of checking query containment is crucial for problems such as query optimization and data integration. The problem of query containment for CRPQs was
first introduced in [Florescu et al. 1998] which showed an E XPSPACE upper bound.
A matching lower bound was then shown in [Calvanese et al. 2000]. Here we study the
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:21

problem of query containment for ECRPQs, i.e., checking for two ECRPQs Q and Q′
over Σ, whether Q(G) ⊆ Q′ (G) for every Σ-labeled graph database G.
It is well-known that the containment and equivalence problem are undecidable forrational relations on words, i.e., relations defined by asynchronous transducers [Berstel 1979]. However, in the context of ECRPQs we cannot use this fact to establish
the undecidability of containment because regular relations used in ECRPQs are synchronous. In fact, for regular relations, containment is decidable. Hence in order toprove Theorem 7.1 below, which states that containment for ECRPQs is undecidable,
we have to use different techniques. In fact, we have indicated in Section 4 how string
patterns (with variables) can be coded by ECRPQs. Combining this with a recent resulton the undecidability of pattern containment [Freydenberger and Reidenbach 2010],
we obtain the following.
T HEOREM 7.1. There exists a fixed finite alphabet Σ, such that the containment
problem for ECRPQs over Σ is undecidable.
P ROOF. It has been recently shown in [Freydenberger and Reidenbach 2010] that
there is a finite alphabet Σ such that the problem of checking whether LΣ (α) ⊆ LΣ (β),
for arbitrary patterns α and β over Σ, is undecidable. We reduce this problem to the
problem of query containment for ECRPQs over a fixed alphabet.
Let α = α1 · · · αn and β = β1 · · · βm be patterns over Σ; that is, each αi and βj (1 ≤i ≤ n, 1 ≤ j ≤ m) is an element of Σ ∪ V (where V is a set of variables). Let Qα
and Qβ be ECRPQs for α and β as constructed in Section 4. Assume
without loss ofVgenerality that the relational parts of α and β are of the form 1≤i≤n (xi−1 , πi , xi ) andV′1≤j≤m (yj−1 , πj , yi ), respectively.
′
Let p and p be symbols not in Σ ∪ V. Define Σ′ as Σ ∪ {p, p′ }. Further, define Q′α
as the ECRPQ over Σ′ that is obtained from Qα by (1) extending its relational partwith the atoms (xinit , π0 , x0 ) and (xn , πn+1 , xend ), and (2) extending its body with theatoms p(π0 ) and p′ (πn+1 ). In the same way, we define Q′β as the ECRPQ over Σ′ thatis obtained from Qβ by (1) extending its relational part with the atoms (yinit , π0′ , y0 )′′and (ym , πm+1
, yend ), and (2) extending its body with the atoms p(π0′ ) and p′ (πm+1). We
prove next that α ⊆ β iff Q′α ⊆ Q′β .
Indeed, assume first that Q′α ⊆ Q′β . Let w̄ = a1 · · · aq be a string over Σ that belongs to LΣ (α). Let G be the Σ′ -labeled graph database such that (1) its set of nodes is{vinit , v0 , v1 , . . . , vq , vend }, (2) there is an edge from vinit to v1 labeled p, (3) there is anedge from vp to vend labeled p′ , (4) there is an edge from vi−1 to vi (1 ≤ i ≤ q) labeled ai ,and (5) those are the only edges in G. Notice that there is a unique path in G from v0
to vq , and the label of that path is precisely w̄.
Clearly, Q′α (G) = true, and thus, Q′β (G) = true. Notice that for every assignment
σ from the node variables of Q′β to the nodes of G and for every assignment µ fromthe path variables in Q′β to the paths in G such that (σ, µ) satisfies Q′β , it must be
the case that (1) σ(yinit ) = vinit , σ(y0 ) = v0 , σ(ym ) = vq , and σ(yend ) = vend , and′(2) if ρ = µ(π1′ ) · · · µ(πm) then ρ = v0 a1 v1 · · · vp−1 aq vq and λ(ρ) = w̄. This shows thatw̄ ∈ LΣ (β). We conclude that α ⊆ β.
Assume, on the other hand, that α ⊆ β. Let G be an arbitrary Σ′ -labeled graphdatabase such that Q′α (G) = true. Assume that σ is an assignment from the nodevariables of Q′α to the nodes of G and µ is an assignment from the path variables in
Q′α to the paths in G such that (σ, µ) satisfies Q′α . Let v = σ(x0 ) and v ′ = σ(xn ). Then
there exists a path ρ in G from v to v ′ such that λ(ρ) ∈ LΣ (α). Then λ(ρ) ∈ LΣ (β). We
conclude that Q′β (G) = true, and thus, that Q′α ⊆ Q′β . This concludes the proof of thetheorem.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:22

Pablo Barceló et al.

It follows from [Freydenberger and Schweikardt 2011] that the problem of containment of a CRPQ in an ECRPQ remains undecidable. We can recover decidability in the
opposite case. The problem of containment of an ECRPQ in a CRPQ is the problem ofchecking whether Q(G) ⊆ Q′ (G) for every Σ-labeled graph database G, where Q is an
ECRPQ and Q′ is a CRPQ over Σ. We can adapt proof techniques from [Calvanese et al.
2000] to show that the above problem has the same complexity as CRPQ containment.
T HEOREM 7.2. The problem of checking containment of an ECRPQ in a CRPQ is
E XPSPACE-complete.
P ROOF. Hardness follows from [Calvanese et al. 2000], since the problem of querycontainment is E XPSPACE-hard already for CRPQs. Next we prove membership. In order to prove that Q is not contained in Q′ we look for a counterexample along the linesof how it is done in [Calvanese et al. 2000; Florescu et al. 1998]. That is, we look for alabeled graph database G such that Q(G) 6⊆ Q′ (G). But as opposed to [Calvanese et al.
2000], which coded counterexamples as strings accepted by usual automata, we code
counterexamples as strings accepted by automata that accept k-ary regular relations,where k depends on Q only. This is because the query Q may contain regular relationsof arity bigger than 1 in its body, and, thus, in most of the cases no standard automaton
will be capable of keeping track of the relationships between paths that are required
to satisfy Q.
As in the case of [Calvanese et al. 2000; Florescu et al. 1998], it is useful firstto give a semantic characterization of containment between ECRPQs in terms ofthe notion of canonicalgraphs. Let Q be an ECRPQ of the form: Ans(z̄, χ̄) ←
V
V
R
(x
,
π
,
y
),
i i
1≤j≤t j (ω̄j ), and assume that each Rj (1 ≤ j ≤ t) is a regular1≤i≤m ilanguage that represents an nj -ary regular relation. Let G be a graph database and σ
an assignment of the node variables in Q into G. Then G is σ-canonical for Q if:— G consists of m simple paths, one for each conjunct in the relational part of Q, which
are node and edge disjoint, i.e. only the start and end nodes can be shared between
different paths;— for each 1 ≤ j ≤ m, if ρj is the path associated with the atom (xj , πj , yj ) then ρjstarts at the node σ(xj ) and ends at the node σ(yj ); and— for each 1 ≤ j ≤ t, if ω̄j = πj1 , . . . , πjnj (1 ≤ jℓ ≤ m, for each 1 ≤ ℓ ≤ nj ) then[λ(ρj1 ), . . . , λ(ρjnj )] satisfies Rj .
Clearly, if G is σ-canonical for Q for some assignment σ, and χ̄ = (πℓ1 , . . . , πℓp ), where. . , ρℓp ) belongs to Q(G).
each πℓi belongs to {π1 , . . . , πm }, then (σ(z̄), ρℓ1 , . V
V
Let Q′ be an ECRPQ of the form Ans(z̄, χ̄) ← 1≤i≤m′ (ui , πi′ , vi ), 1≤j≤t′ Sj (ω̄j′ ) overthe same alphabet as Q, and assume that each Sj (1 ≤ j ≤ t′ ) is a regular languagethat represents a pj -ary regular relation, pj > 0. Notice that we assume that Q′ has
the same node and path variables in the head as Q (i.e. it has the same free variables
as Q). Further, we assume without loss of generality that the set of non-free variablesof Q and Q′ respectively are disjoint.
Let G be a graph database that is σ-canonical for Q, for some σ. Further, let σ ′ be amapping from the node variables of Q′ into the nodes of G and µ be a mapping fromthe path variables of Q′ into the paths of G. Then (σ ′ , µ) is a (Q′ , G, σ)-mapping, if thefollowing hold:— For each z ∈ z̄, we have that σ(z) = σ ′ (z);— for each χ ∈ χ̄, if χ = πi (1 ≤ i ≤ m) then µ(χ) = ρi ;— for each 1 ≤ j ≤ m′ , µ(πj′ ) is a path from σ ′ (uj ) to σ ′ (vj ); andACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:23

— for each 1 ≤ j ≤ t′ , if ω̄j′ = πj′ 1 , . . . , πj′ p (1 ≤ jℓ ≤ m, for each 1 ≤ ℓ ≤ pj ), thenj[λ(µ(πj′ 1 )), . . . , λ(µ(πj′ p ))] satisfies Sj .
jUsing essentially the same techniques as in [Calvanese et al. 2000; Florescu et al.
1998] it is possible to give the following semantic characterization of ECRPQ containment:
C LAIM 7.2.1. Let Q and Q′ be two ECRPQs over the same alphabet Σ. Then Q is
not contained in Q′ if and only if there exists a Σ-labeled graph database G and an
assignment σ from the variables of Q to the nodes of G, such that G is σ-canonical for
Q and no (Q′ , G, σ)-mapping exists.
The key idea used in [Calvanese et al. 2000] to prove that containment of CRPQs isin E XPSPACE is as follows. Given CRPQs Q and Q′ , first one codes each graph databaseG that is σ-canonical for Q (for some σ) as a string over some extended alphabet of
exponential size, and then constructs an NFA A that accepts exactly those strings overthis extended alphabet that correspond to those codifications of σ-canonical graphs G
for Q for which no (Q′ , G, σ)-mapping exists. The NFA A is double exponential in thesize of the input, i.e. the pair (Q, Q′ ). Thus, checking whether Q is not contained in Q′
is equivalent to checking whether the language accepted by A is nonempty, which canbe done in E XPSPACE by a typical “on-the fly” simulation of A.
In more detail, in orderVto generate candidate
counterexamples to the fact that theV
CRPQ Q := Ans(z̄) ← 1≤i≤m (xi , πi , yi ), 1≤j≤m Lj (ωj ) is contained in the CRPQ
Q′ , Calvanese et al. [2000] construct an NFA A1 that accepts strings of the form
$d1 w1 e1 $d2 w2 e2 $ · · · $dm wm em $, where m is the number of path variables in Q, that
represent graph databases that are σ-canonical for Q, for some assignment σ. Each diand ei (1 ≤ i ≤ m) is a set of node variables from Q. To construct A1 it is necessary todefine:— An NFA that accepts all strings of the form above, such that for each i ∈ [1, m],xi ∈ di , yi ∈ ei , and for each 1 ≤ j ≤ m it is the case that wj belongs to Lj .
— An NFA that checks that the distinct symbols di and ei appearing in the string forma partition of the variables of Q.
Then A1 is defined as the intersection of these two NFAs.
Finally, A1 is extended to an NFA A that accepts those strings w of the form above,that “code” a graph Gw that is σw -canonical for Q and such that no (Q′ , Gw , σw )mapping exists. The size of A is double exponential in |Q| + |Q′ |. It is shown that Q
is not contained in Q′ iff A accepts at least some string.
With essentially the same techniques we can prove Theorem 7.2. Let Q be an
ECRPQ and Q′ be a CRPQ over the same alphabet. Assume that m is the number of relational atoms in Q. Let Q1 be the restriction of Q to the regular relation
atoms of arity at most 1. We construct, using the techniques in [Calvanese et al.
2000] mentioned above, a double exponential NFA A that accepts at least some string
iff Q1 is not contained in Q′ . As we explained above, the NFA A accepts stringsof the form $d1 w1 e1 $d2 w2 e2 $ · · · $dm wm em $. It is then easy to construct an m-ary
letter-to-letter NFA Am of double exponential size, that accepts exactly the strings(d1 w1 e1 , d2 w2 e2 , . . . , dm wm em ) such that A accepts $d1 w1 e1 $d2 w2 e2 $ · · · $dm wm em $. We
then compute the intersection A2 of A with an NFA AQ that checks that, for eachregular relation atom in Q of the form R(πi1 , . . . , πin ), such that R is of arity > 1, thetuple (wi1 , . . . , win ) belongs to R. The size of AQ is exponential, and thus, the size of
A2 is double exponential. Further, it can easily be proved that Q is not contained in Q′
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:24

Pablo Barceló et al.

iff A2 accepts at least some string. This can be done in E XPSPACE by an “on-the-fly”
construction of A2 .
8. EXTENSIONS

We now look at various ways of going beyond the class of ECRPQs. First, we consider
an analog of relational calculus by adding negation and arbitrary quantification to thelanguage. After that, we look at conjunctive queries with non-regular relations; we
handle linear constraints on lengths of paths, and Parikh-image constraints.
8.1. Adding negation

We now investigate the query evaluation problem for the extension of ECRPQs withnegation. Formally, we define the language ECRPQ¬ over alphabet Σ as the set of
formulas described by the following grammar:
atom := π1 = π2 | x = y | (x, π, y) | R(π1 , . . . , πn )ϕ, ψ := atom | ¬ϕ | ϕ ∧ ψ | ∃xϕ | ∃πϕHere x, y range over the set of node variables, π, π1 , . . . range over the set of pathvariables, and R ranges over the set of regular expressions over alphabets (Σ⊥ )n (n >0) that represent n-ary regular relations over Σ. The language CRPQ¬ is defined as
the restriction of ECRPQ¬ to formulas that only make use of regular languages. The
notions of free and bound variables are standard; we write ϕ(x̄, π̄) to list free node andpath variables explicitly.
The semantics of ECRPQ¬ is defined in the standard way. Given a graph databaseG = (V, E), a mapping σ from the set of free node variables of ϕ into V , and a mapping µfrom the set of free path variables of ϕ into the set of paths in G, the notion (G, σ, µ) |= ϕis defined just as for ECRPQs with the following additional rules:— the Boolean connectives ¬ and ∨ have the standard semantics;— (G, σ, µ) |= ∃xϕ iff there exists v ∈ V such that (G, σx→v , µ) |= ϕ, where σx→v extends
the assignment σ by letting σ(x) = v;
— (G, σ, µ) |= ∃πϕ iff there exists a path ρ in G such that (G, σ, µπ→ρ ) |= ϕ, where µπ→ρextends the assignment µ by letting µ(π) = ρ.
Given a graph database G and an ECRPQ¬ formula ϕ(x̄, π̄), we let ϕ(G) be the set oftuples (v̄, ρ̄) such that (G, σ, µ) |= ϕ, where σ(x̄) = v̄ and µ(π̄) = ρ̄.
Notice that ECRPQ¬ and CRPQ¬ express nontrivial properties of graph databasesthat are not expressible by means of ECRPQs. For instance, the query ¬∃π ((x, π, y) ∧L(π)) defines the set of all pairs (a, b) of nodes such that no path between them islabeled by a string from language L.
Combined complexity. The problems ECRPQ¬ - EVAL and CRPQ¬ - EVAL are defined exactly as the query evaluation problems in Section 6.2, except that the input query is from the extended language. Again we see a significant difference between regular languages and regular relations in queries. The complexity jumps inboth cases, but while CRPQ¬ - EVAL can be solved in single-exponential time, ECRPQ¬
queries cannot be evaluated in time bounded by a fixed stack of exponents.
T HEOREM 8.1.
— The problem CRPQ¬ - EVAL is P SPACE-complete.
— The problem ECRPQ¬ - EVAL is decidable, but non-elementary.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:25

P ROOF. We start by proving the first part of the theorem. Hardness follows from
Proposition 6.8 since the language CRPQ¬ allows for path variable repetition. Next
we prove membership.
Let G = (V, E) be a Σ-labeled graph database and ϕ(x̄, π̄) be a CRPQ¬ formula.
Further, let v̄ be a tuple of nodes in G such that |v̄| = |x̄| and ρ̄ be a tuple of paths in
G such that |ρ̄| = |π̄|. Further, assume that L1 , . . . , Lm are all the regular expressions
mentioned in ϕ. Our goal is to define a P SPACE procedure that checks whether (v̄, ρ̄) ∈ϕ(G). In order to do that, we first have to introduce some new terminology.
Let τ be a first-order (FO) vocabulary hN odes, P aths, Endpoints, L1, . . . , Lm i, where
N odes, P aths, and Li (1 ≤ i ≤ m) are unary relation symbols, and Endpoints is aternary relation symbol. We define, from G, an FO structure MG over τ as follows: The
domain of MG is the disjoint union of V and all the paths that belong to G. (Notice thateach node in V is also a path in G, but here we consider them to be different objects.
That is, each v ∈ V appears separately as a node and a path in the domain of MG ).
The interpretation of N odes in MG contains all those elements of the domain that arenodes. The interpretation of P aths in MG contains all those elements of the domainthat are paths. The interpretation of the ternary relation Endpoints contains all tuples(v, ρ, v ′ ) such that ρ is a path in G from node v to node v ′ . Finally, the interpretationof the symbol Li (1 ≤ i ≤ m) contains all those paths in G whose label satisfies theregular expression Li .
Let ϕτ be the FO formula over vocabulary τ obtained from ϕ by simultaneously
replacing (1) each subformula of the form ∃xθ (for x a node variable) with ∃x(N odes(x)∧θ), (2) each subformula of the form ∃πθ (for π a path variable) with ∃π(P aths(π) ∧ θ),and (3) each atomic formula of the form (x, π, y) with (N odes(x) ∧ N odes(y) ∧ P aths(π) ∧Endpoints(x, π, y)).
Clearly, (v̄, ρ̄) ∈ ϕ(G) iff (v̄, ρ̄) belongs to the evaluation of ϕτ over MG .
Of course, MG cannot be effectively constructed from G since the set of paths in G
is potentially infinite, and, thus, MG is also potentially infinite. However, it is possible
to prove that there exists a finite substructure M′G,v̄,ρ̄ of MG such that (v̄, ρ̄) belongs
to the evaluation of ϕτ over MG iff it belongs to the evaluation of ϕτ over M′G,v̄,ρ̄ . Weshow how to define M′G,v̄,ρ̄ next.
Assume that the quantifier rank of ϕτ is k ≥ 0, where as usual the quantifier rankof an FO formula θ is the depth of nested quantification in θ. Let L ⊆ {L1 , . . . , Lm }. We
say that a path in G satisfies L if the label of π satisfies L, for each L ∈ L, and does notsatisfy L′ , for each L′ ∈ {L1 , . . . , Lm } \ L. (Notice that for each path in G there is one,and only one, subset L of {L1 , . . . , Lm } that it satisfies.) For each pair (v, v ′ ) of nodes
in V , and for every L ⊆ {L1 , . . . , Lm }, let cL,v,v′ ≥ 0 be the minimum between k + |ρ̄|and the number of paths in G that go from v to v ′ and satisfy L. We arbitrarily pick,for each pair (v, v ′ ) of nodes in V and for each L ⊆ {L1 , . . . , Lm }, cL,v,v′ distinct paths
cL,v,v′′
ρ1L,v,v′ , . . . , ρL,v,v′ from v to v that satisfy L.
We define the structure M′G,v̄,ρ̄ as follows: Its domain contains all the nodes of V ,each path ρ that belongs to the tuple ρ̄, and every path of the form ρiL,v,v′ , where L ⊆{L1 , . . . , Lm }, v, v ′ ∈ V and 1 ≤ i ≤ cL,v,v′ . The interpretation of N odes in M′G,t̄,ρ̄contains all nodes in the domain. The interpretation of P aths in M′G,v̄,ρ̄ contains all
those elements of the domain that are paths. The interpretation of the ternary relation
Endpoints contain all tuples of the form (v, ρ, v ′ ), where v, v ′ ∈ V and ρ is a path in thedomain that goes from v to v ′ in G. Finally, the interpretation of Li (1 ≤ i ≤ m) in
M′G,v̄,ρ̄ contains all those paths in the domain of M′G,v̄,ρ̄ for which its label satisfies Li .
By using a standard Ehrenfeucht-Fraı̈ssé argument it is possible to prove the following:
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:26

Pablo Barceló et al.

C LAIM 8.1.1. The structures (MG , v̄, ρ̄) and (M′G,v̄,ρ̄ , v̄, ρ̄) are indistinguishable by
FO sentences of quantifier rank ≤ k.
Proof (Sketch): We show that the duplicator has a winning strategy in the k-round
Ehrenfeucht-Fraı̈ssé game played on (MG , v̄, ρ̄) and (M′G,v̄,ρ̄ , v̄, ρ̄). The duplicator’s response to a spoiler move in round i ≤ k is (inductively) defined as follows (we assume
without loss of generality that the spoiler never repeats moves, i.e. in no round does
the spoiler choose an element that has already been chosen by either player in previous
rounds):— If the spoiler’s move in round i is a node in either of the two structures, then the
duplicator responds by mimicking the spoiler’s move on the other structure;— if the spoiler’s move in round i is a path ρ in ρ̄ in either of the two structures,
then again the duplicator responds by mimicking the spoiler’s move on the otherstructure;— if the spoiler plays a path ρ from node v to v ′ , in either of the two structures, suchthat ρ satisfies L ⊆ {L1 , . . . , Lm } and ρ is not a path in ρ̄, then the duplicator responds with any path from v to v ′ in the other structure that (1) satisfies L, (2) does
not belong to ρ̄, and (3) has not been previously chosen in the game. Notice that it isalways possible for the duplicator to choose such a path, since for each pair of nodesv, v ′ ∈ V and for each L ⊆ {L1 , . . . , Lm }, the number of paths from v to v ′ that satisfy
L and that do not belong to ρ̄ is the same up to k.
It is not hard to see that duplicator’s response defined in this way always preserves
a partial isomorphism between the two structures. This implies that the duplicator
has a winning strategy in the k-round Ehrenfeucht-Fraı̈ssé game played on (MG , v̄, ρ̄)and (M′G,v̄,ρ̄ , v̄, ρ̄), and, thus, by well-known results, that the structures are indistinguishable by FO sentences of quantifier rank ≤ k.
✷
The previous claim shows that (v̄, ρ̄) ∈ ϕ(G) if and only if (v̄, ρ̄) belongs to the evaluation of ϕτ over M′G,v̄,ρ̄ . Thus, a straightforward approach to check whether (v̄, ρ̄) ∈ ϕ(G)would be to construct M′G,v̄,ρ̄ and then evaluate ϕτ over it. The problem with this approach is that M′G,v̄,ρ̄ could be of exponential size, and, thus, impossible to constructin polynomial space. It will be necessary to follow a different approach then.
Assume that ϕτ is given in prenex normal form, i.e. ϕτ is of the form
Q1 y1 · · · Qm ym α(x̄, π̄, y1 , . . . , ym ), where each Qi is either ∃ or ∀ and α is quantifierfree (if ϕτ is not in prenex normal form, we can convert it in polynomial time into an
equivalent formula in prenex normal form). We follow a usual P SPACE argument toevaluate FO formulas on structures. The main problem with this is that some of theelements in M′G,v̄,ρ̄ are paths and have to be treated as such. Thus, it is necessary todefine a way of coding paths in polynomial space.
In our case, each path will be coded with an address, that is a string over a finite
alphabet. The address of a path ρ can be intuitively explained as follows:— It starts with a new symbol p, that states that this is the address of a path;— the address continues with the encodings of the two endpoints v and v ′ of the path(separated with some delimiter); this part of the address uses O(log2 |V |) space;— afterwards, the address contains an encoding of the subset L of {L1 , . . . , Lm } that ρsatisfies; this encoding is a string of length m over alphabet {0, 1} such that its i-th
symbol is 1 iff Li ∈ L;
— then the address contains an encoding of the integer i ≤ k + |ρ̄| such that ρ = ρiL,v,v′ ;this encoding uses O(log2 (|ϕ| + |ρ̄|)) space.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:27

Clearly, the address of a path defined in this way can be specified using at most polynomial space.
We show next how the problem of checking whether (v̄, ρ̄) belongs to the evaluationof ϕτ over M′G,v̄,ρ̄ can be solved in polynomial time by an alternating Turing machine.
This will finish the proof of the theorem, since the class of problems that can be solvedin polynomial time by alternating Turing machines coincides with the class of problems that can be solved in P SPACE.
The alternating machine proceeds as follows. It first replaces in ϕτ each variable x inx̄ with the encoding of the corresponding node v of v̄. It then replaces each variable π in
π̄ with the encoding (address) of the corresponding path ρ in ρ̄. Then the machine reads
the formula ϕτ from left-to-right. Each time it encounters an existential quantifier ∃yi
it enters an existential state, and each time it encounters a universal quantifier ∀yi itenters a universal state. In each case, the machine “guesses” the interpretation of yi as
the encoding of a node or a path c(yi ) in the domain. Finally, the machine verifies thatα(v̄, ρ̄, c(y1 ), . . . , c(ym )) holds, and if that is the case it accepts. We show next that thelatter can be done in polynomial time. Notice that this implies that the whole process
can be performed in polynomial time.
We start with the case of the atomic formulas in α. In order to check whether theelement assigned to a variable belongs to the interpretation of N odes in M′G,v̄,ρ̄ , weonly have to check that the encoding of this element does not start with a p. In orderto check whether the element belongs to the interpretation of P aths, it is sufficient
to check that its encoding starts with a p. In order to check whether the elements
a, b, c assigned to variables x, π, y, respectively, are such that (a, b, c) belongs to theinterpretation of Endpoints, we only have to check that b is the encoding of a path,a and c are encodings of nodes, and that b is a path from a to c. Finally, in order tocheck whether the element a assigned to a variable belongs to the interpretation ofLi (1 ≤ i ≤ m), we only have to check that a is a path (i.e. its encoding starts with p)
and the bit that corresponds to Li in the encoding of the subset L of {L1 , . . . , Lm } thatsatisfies a is set to 1.
Thus, the value of the atomic formulas involved in α(v̄, ρ̄, c(y1 ), . . . , c(ym )) can becomputed in polynomial time. But α is a polynomial size Boolean combination of atomic
formulas, and, thus, the value of α(v̄, ρ̄, c(y1 ), . . . , c(ym )) can be computed in polynomial
time from the values of the atomic formulas. We conclude that computing the value ofα(v̄, ρ̄, c(y1 ), . . . , c(ym )) can be done in polynomial time.
There is, however, one small issue that requires explanation in order for the previous
procedure to work properly. Assume that the procedure “guesses” the interpretationof a variable yi in ϕτ to be the encoding of a path in G from v to v ′ that satisfies
L ⊆ {L1 , . . . , Lm }. Then it is necessary to check that, if the encoding implies that thispath is ρiL,v,v′ , then i ≤ cL,v,v′ . In order to do so, the procedure needs to check, in a
subroutine, whether there exist i different paths from v to v ′ that satisfy L. The next
claim shows that this can be done in polynomial space, which finishes the proof of thetheorem.
C LAIM 8.1.2. For each pair v, v ′ ∈ V , subset L of {L1 , . . . , Lm } and i ≤ k + |ρ̄|, one
can check in P SPACE whether there exist i distinct paths in G = (V, E) from v to v ′ thatsatisfy L.
Proof (Sketch): First, let Av,v′ be the automaton over alphabet {v} ∪ (Σ⊥ × V ) defined
as follows. The set of states is the disjoint union of V with a new state s. The initialstate of A is s and the final state is v ′ . Further, the transition relation of A is defined asfollows: (1) For every edge (v1 , a, v2 ) ∈ E there is a transition in A from v1 to v2 labeled
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:28

Pablo Barceló et al.

(a, v2 ), (2) for every node v1 ∈ V there is a transition from v1 to v1 in A labeled (⊥, v1 ),and (3) there is a transition in A from s to v labeled v. Intuitively, Av,v′ accepts exactly
those strings of the form v(a1 , v1 )(a2 , v2 ) · · · (a, v ′ ) such that va1 v1 a2 v2 · · · av ′ is a path inG from v to v ′ , when we allow paths to loop arbitrarily many times on ⊥-labeled nodes.
Let Aiv,v′ be the automaton over alphabet {v i } ∪ (Σ⊥ × V )i defined as follows: The
set of states is V i ∪ {si }, the initial state is si and the final state is (v ′ )i . There is atransition in Ai from ū = (u1 , . . . , ui ) to w̄ = (w1 , . . . , wi ) labeled t̄ = (t1 , . . . , ti ) iff there
is a transition labeled tℓ from uℓ to wℓ in Av,v′ , for each 1 ≤ ℓ ≤ i. Clearly, Aiv,v′ isof exponential size but the size of each one of its states is polynomial. Further, it isdecidable in polynomial time whether there exists a transition labeled t̄ from state ū
to w̄ in Aiv,v′ .
Define now an automaton A′v,v′ that is the restriction of Aiv,v′ to those stringsiv (w11 , . . . , wi1 ) · · · (w1m , . . . , wim ) over alphabet {v i } ∪ (Σ⊥ × V )i that satisfy the following:— For each 1 ≤ ℓ ≤ i, if for some 1 ≤ j < m it is the case that wℓj = (⊥, v1 ), for somev1 ∈ V , then for each j < k ≤ m it is the case that wℓk = (⊥, v1 ).
— For each 1 ≤ ℓ, p ≤ i, if ℓ 6= p then the strings vwℓ1 · · · wℓm and vwp1 · · · wpm over alphabet{v} ∪ (Σ⊥ × V ) are different.
The first condition says that each projection of a string accepted by A′v,v′ representsa path in G from v to v ′ that loops only on v ′ and only at the end of the path. The
second condition ensures that any two distinct projections of a path accepted by A′v,v′
represent different strings.
It is not hard to prove that the language accepted by A′v,v′ is nonempty iff there exist
i distinct paths in G from v to v ′ . Further, it is also not hard to see that A′v,v′ is ofexponential size but the size of each one of its states is polynomial; and it is decidable
in polynomial time whether there exists a transition labeled t̄ from state q̄ to state q̄ ′in A′v,v′ .
Let AL be the automaton that accepts all those strings w̄ over Σ such that w̄ satisfies
L, for each L ∈ L, and does not satisfy L′ , for each L′ ∈ {L1 , . . . , Lm } \ L. Notice that thesize of AL is exponential in the size of ϕ, but each one of the states of AL is polynomialin the size of ϕ. Further, it is decidable in polynomial time whether there is a transition
labeled ā from a state r̄ to a state r̄′ of AL .
Let Q be the set of states of A′v,v′ and R be the set of states of AL . We define a newautomaton Afv,v′ over alphabet {v i } ∪ (Σ⊥ × V )i as follows: The set of states of Afv,v′ is
Q × Ri , the initial state is (q0 , r0 , . . . , r0 ), where q0 and r0 are the initial states of A′v,v′
and AL , respectively, and the final states are those of the form (qf , rf , . . . , rf ), where qf
and rf are final states of A′v,v′ and AL , respectively. Further, the automaton Afv,v′ has atransition from state (q, r11 , . . . , ri1 ) to (q ′ , r12 , . . . , ri2 ) (q, q ′ ∈ Q and {r11 , r12 , . . . , ri1 , ri2 } ⊆ R)
labeled w̄ = (w1 , . . . , wi ) iff (1) there is a transition from q to q ′ in A′v,v′ labeled w̄, (2) ifw̄ = v i then rj1 = rj2 , for each 1 ≤ j ≤ i, and (3) if w̄ = ((a1 , v1 ), . . . , (ai , vi )) ∈ (Σ⊥ × V )i ,then the following holds: (a) if aj = ⊥ (1 ≤ j ≤ i) then rj1 = rj2 , and (b) if aj 6= ⊥(1 ≤ j ≤ i) then there is a transition labeled aj from rj1 to rj2 in AL . Notice againthat the size Afv,v′ is exponential in the size of ϕ, but each one of the states of Afv,v′ ispolynomial in the size of ϕ. Further, it is decidable in polynomial time whether there
is a transition labeled w̄ from a state (q, r̄) to a state (q ′ , r̄′ ) of Afv,v′ .
It is not hard to prove that the language accepted by Afv,v′ is nonempty iff there
exist i distinct paths in G from v to v ′ that satisfy L. The former can be easily checked
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:29

in polynomial space using a standard “on-the-fly” verification procedure. This finishes
the proof of the claim.
✷
This completes the proof of the first part of the theorem.
Now we prove the second part of the theorem. We only prove decidability since thenon-elementary lower bound will follow from the second part of Theorem 8.2. The argument uses essentially the same kind of proof techniques applied in Section 5 toconstruct a compact representation of the set of answers to an ECRPQ. That is, weshow that for every ECRPQ¬ formula one can construct an automaton that represents
the set of “answers” to the formula for a given interpretation of the free node variables.
C LAIM 8.1.3. Let ϕ(x̄, π̄) be an ECRPQ¬ formula, G = (V, E) a Σ-labeled graphdatabase, and v̄ be tuple of nodes in G such that |v̄| = |x̄|. It is possible to effectively(G,v̄)
construct an automaton Aϕover alphabet V |π̄| ∪ (Σ⊥ )|π̄| that accepts precisely the set
ϕ(G, v̄) = {ρ̄ | (v̄, ρ̄) ∈ ϕ(G)}.
It is not hard to see that Claim 8.1.3 implies decidability of the ECRPQ¬ evaluation
problem. Indeed, an algorithm that checks whether (v̄, ρ̄) belongs to ϕ(G) can proceed(G,v̄)
as follows: It first constructs Aϕfrom G = (V, E), v̄ and ϕ. Then it constructs thestring ω̄ over alphabet V |π̄| ∪ (Σ⊥ )|π̄| that represents the tuple ρ̄ (this can be done in(G,v̄)
polynomial time). Finally, the algorithm checks whether ω̄ is accepted by Aϕ . If thelatter is the case, the procedure accepts.
Now we prove Claim 8.1.3. Let Σ be a finite alphabet, G = (V, E) be a Σ-labeledgraph database, ϕ(x̄, π̄) an ECRPQ¬ formula over alphabet Σ and v̄ a tuple of nodes(G,v̄)in G such that |v̄| = |x̄|. We first show how to construct the automaton Aϕfor the¬case when ϕ is an atom, i.e. an ECRPQ formula over Σ that is of the form x = y,π = π ′ , (x, π, y) or R(π1 , . . . , πn ), where R is a regular relation over (Σ⊥ )n (n ≥ 0) that
represents an n-ary regular relation over Σ.
— Assume first that ϕ is x = y. Then v̄ is of the form (v, v ′ ) ∈ V × V . If v = v ′ , we set(G,v̄)
Aϕ
to be the automaton that accepts all strings over alphabet V ∪ Σ. If v 6= v ′ we(G,v̄)
set Aϕto be the automaton that accepts no string over the alphabet V ∪ Σ.
— Assume second that ϕ is (x, π, y). Then v̄ is of the form (v, v ′ ) ∈ V × V . Let V =(G,v̄){v1 , . . . , vm }, and let U = {u1 , . . . , um } be a disjoint copy of V . The automaton Aϕis defined as follows: (1) V ∪ U ∪ {f } is the set of states, where f is a node neither in
U nor in V ; (2) for every edge (vi , a, vj ) ∈ E, the automaton has a transition labeled
a from state vi to state ui and a transition labeled vj from ui to vj ; (3) the automaton
has a transition from f to v labeled v; (4) the initial state is f ; and (5) the final stateis v ′ .
— Assume third that ϕ is R(π1 , . . . , πn ), where R is a regular relation over (Σ⊥ )n (n ≥ 0)that represents an n-ary regular relation over Σ. Then v̄ is the empty tuple.
Let
that recognizes R. Then take A′ to be the NFA A ×
S A be the automaton
n
G
(ū,
v̄)
over
alphabet (Σ⊥ )n . The states of A′ are of the form (q, ū),(ū,v̄)∈Gn ×Gn
where q is a state of A and ū is a node in Gn . It is not hard to construct (in particular, using techniques that are similar to the ones in the previous item) from
A′ an automaton A′′ over alphabet V n ∪ (Σ⊥ )n that accepts exactly those stringsū0 ā1 ū1 · · · ām ūm such that for some sequence q0 · · · qm of states in A, it is the casethat (q0 , ū0 ) · · · (qm , ūm ) is an accepting run of A′ over ā1 · · · ām .
(G,t̄)In this case we set Aϕto be A′′ .
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:30

Pablo Barceló et al.

— Assume finally that ϕ is π1 = π2 . Then v̄ is the empty tuple.
S(G,v̄)
We construct Aϕ
as follows. Take (ū,ū′ )∈G2 ×G2 G2 (ū, ū′ ) and construct from it(using techniques similar to the ones in the previous items) an automaton A overalphabet V 2 ∪ (Σ⊥ )2 that accepts
S exactly those strings v̄0 ā1 v̄1 · · · ām v̄m such thatv̄0 · · · v̄m is an accepting run of (ū,ū′ )∈G2 ×G2 G2 (ū, ū′ ), i.e. v̄0 ā1 v̄1 · · · ām v̄m is a pathin G2 . Finally, let A′′ be the restriction of A′ to the alphabet {(s, s) | s ∈ V ∪ Σ⊥ }.
(G,v̄)In this case we set Aϕto be A′′ .
It is straightforward to see that the following is the case: Let ϕ(x̄, π̄) be an atomic
ECRPQ¬ formula, G = (V, E) a graph database, and v̄ be tuple of nodes in G such that
(G,v̄)|v̄| = |x̄|. The automaton Aϕ , as defined above, can be effectively constructed from
(G,v̄)
accepts precisely the set ϕ(G, v̄).
ϕ, G and v̄. Further, Aϕ(G,v̄)
for the rest of the cases. In all these cases,
Now we show the construction of Aϕthe construction is given recursively:(G,v̄)— If ϕ is ¬ψ(x̄, π̄) then Aϕ(G,v̄)of Aψ .

is defined as the automaton that accepts the complement(G,v̄)— If ϕ is ψ(x̄, π̄) ∧ θ(x̄, π̄) then Aϕ(G,v̄)

is the intersection of Aψ
S(G,v̄,v ′ )(G,v̄).
— If ϕ is ∃yψ(x̄, y, π̄) then Aϕis defined as v′ ∈V Aψ
(G,v̄)— If ϕ is ∃π ′ ψ(x̄, π̄, π ′ ) then Aϕnent that represents π.

(G,v̄)and Aθ
(G,v̄)

is defined as the projection of Aψ

.

over the compo-

From here on the proof of the claim is almost straightforward, using the atomic caseand induction.
Data complexity. We now turn to data complexity, with the graph database as thesole input. That is, we look at problems CRPQ¬ - EVAL(ϕ) and ECRPQ¬ - EVAL(ϕ), foreach query ϕ. Again we see a significant gap between allowing regular languages andrelations. In the former case, the complexity matches that of the CRPQs, while in thelatter case the problem is non-elementary. That is, neither the combined nor the data
complexity of the problem of evaluating queries in ECRPQ¬ can be bounded by a stackof exponentials.
T HEOREM 8.2.
— For each CRPQ¬ formula ϕ, the problem CRPQ¬ - EVAL(ϕ) is in NL OGSPACE.
— There is a finite alphabet Σ and a family {ϕk }k∈N of Boolean ECRPQ¬ formulas over
Σ such that, for all k ∈ N, checking whether a Σ-labeled graph database G satisfies
ϕk necessarily requires k-fold exponential time.
P ROOF. It is not hard to see that the P SPACE algorithm used in the first part of theproof of Theorem 8.1 (to show an upper bound on the complexity of CRPQ¬ - EVAL) canbe performed in NL OGSPACE if we assume the formula to be fixed. This shows that
CRPQ¬ - EVAL(ϕ) is in NL OGSPACE, for each CRPQ¬ formula ϕ.
Now we prove the second part. We only need to prove the following lemma.
L EMMA 8.3. Fix the FO vocabulary σ = h<, U i, where < is binary and U is unary.
Let Ck stand for the class of all FO formulas over σ in prenex-normal form with quantifier type (∀+ ∃+ )k . Then there exists a fixed ECRPQ¬ formula ϕk such that satisfiabilityof Ck formulas over σ-structures is exponential-time reducible to checking whether an
input graph database G over Σ satisfies ϕk .
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:31

In fact, since there exists a small constant ε ∈ N such that satisfiability of Ck formulas over σ-structures is not solvable in (k − ε)-E XPTIME [Robertson 1974; Stockmeyer
1974], this lemma immediately gives the second part of Theorem 8.2.
We proceed with the proof of the above lemma. Each candidate σ-structure M =h{1, . . . , n}; <, U i for Ck formulas can be represented as a string w̄ = w1 . . . wn overalphabet {0, 1}, where wi = 1 iff i ∈ U . However, since we are only allowed to construct
a fixed ECRPQ¬ formula ϕk independent of the input Ck formulas, we can only embed
the information on quantifier type in the input formula in ϕk ; we will have to embed
the remaining information on the input Ck formula within the graph database G. To
this end, since the quantifiers in Ck formulas quantify over string positions, we will
“annotate” binary strings with this piece of information, which will then be checked
by a fixed regular relation in the formula in ϕk with the help of the non-fixed graphdatabase G. Annotated strings will be represented over the alphabet {0, 1, , ×}.
We illustrate our annotation schemes by an example. Suppose that the input is a
C1 formula ∀x1 ∀x2 ∃y1 ∃y2 ψ, where ψ is quantifier-free, and the input string is w̄ =01000101. We think of the input formula as a game with three rounds: (1) player ∀annotates two (not necessarily distinct) positions of w̄ with x1 and x2 , (2) player ∃annotates two (not necessarily distinct) positions of w̄ with y1 and y2 , and (3) checkthat the annotated string satisfies ψ. At the beginning of round 1, the annotated string
is
0

1

0

0

0

1

0

1

.

Notice that the number of next to a bit 0 or 1 is 4, which corresponds to the numberof variables in the input formula. Suppose that player ∀ assigns x1 (resp. x2 ) to position
1 (resp. 4). Then we cross the first box next to the bit at position 1 and the second box
next to the bit at position 4, resulting in the following annotated string:
0×

1

0

0 ×

0

1

0

1

.

Suppose that player ∃ assigns y1 (resp. y2 ) to position 6 (resp. 1). Then we cross the box
again appropriately, resulting in the following annotated string:
0×

×1

0

0 ×

0

1

× 0

1

.

From the above example, we see that the number of rounds of the game depends only
on the number of quantifier alternations (i.e. the value of k in Ck ), not on the numberof variables in the input Ck formula. In the general case of a formula in Ck of the form
∀x1 ∃y1 . . . ∀xk ∃yk ψ,
where ψ is quantifier-free, the Ck -game consists of 2k + 1 rounds, with rounds 2i − 1
and 2i (1 ≤ i ≤ k) corresponding to the annotation of i-th block ∀xi ∃yi of quantifiers in
the formula, and round 2k + 1 for checking whether the annotation satisfies ψ.
Therefore, we proceed with the proof of Lemma 8.3 as follows. The alphabet Σ ofedge labels is defined as:Σ := {0, 1, , ×, ℓ},where ℓ is a fresh distinguished symbol. The formula ϕk that we construct uses pathvariables {πi }2k+1
i=1 such that π1 captures the annotated string at the beginning of round
1, and πi (2 ≤ i ≤ 2k + 1) captures the annotated string at the end of round i − 1. The
way in which πi is quantified in the formula ϕk will depend on the parity of i. More
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:32

Pablo Barceló et al.

precisely, we define ϕk as follows:θk+1 (y, π) := (y = y) ∧ (π = π)θi (y, π2i−1 ) := ∃x ℓ(y, x) ∧ ∀z∀π2i (x, π2i , z) ∧ R(π2i−1 , π2i ) →∃u∃y∃π2i+1 ℓ(z, u) ∧ (u, π2i+1 , y) ∧ R(π2i , π2i+1 ) ∧ θi+1 (y, π2i+1 )
ϕk := ∃x∃y∃π1 (x, π1 , y) ∧ R′ (π1 ) ∧ θ1 (y, π1 ) ,(1 ≤ i ≤ k)where R(π, π ′ ) is a regular relation checking “consistencies” between π and π ′ in thefollowing sense (we denote by π[i] the i-th letter of λ(π)):(1) |π| = |π ′ |,(2) for each i ∈ N, if π[i] = 0, then π ′ [i] = 0(3) for each i ∈ N, if π[i] = 1, then π ′ [i] = 1,
(4) for each i ∈ N if π[i] = , then π ′ [i] ∈ { , ×}, and(5) for each i ∈ N, if π[i] = ×, then π ′ [i] = ×,∗)∗ that checks that the label of π repreand R′ (π) is the regular language (0 + 1) ·sents a potential initial annotation of a string.
For example, whenever k = 1, we obtain the formula ϕ1 defined as:∃x∃y∃π1 (x, π1 , y) ∧ R′ (π1 ) ∧.
∃x ℓ(y, x) ∧ ∀z∀π2 (x, π2 , z) ∧ R(π1 , π2 ) → ∃u∃y∃π3 (ℓ(z, u) ∧ (u, π3 , y) ∧ R(π2 , π3 )At this point, observe that ϕk is independent of the input Ck formula. We now needto take into account the input formula in the graph database G that we construct.
Suppose that the input formula Ψ ∈ Ck is∀x1 ∃y1 . . . ∀xk ∃yk ψPP
where ψ is quantifier-free. Let ri := |xi | and ti := |yi |. Let r := ki=1 ri and t := ki=1 ti .
We construct the graph database G from the disjoint 2k + 1 graph databases
G1 , . . . , G2k+1 defined below. Each graph database Gi has a predetermined source nodeci and a predetermined sink node c′i such that the set of paths from ci and c′i will
be used to restrict the range of the paths where the path variable πi in the formula
ϕk can be witnessed. For convenience, when defining Gi we allow the use of regularexpressions over Σ, as there is a standard polynomial-time translation from regularexpressions to NFAs.
The graph databases G1 , . . . , G2k+1 are defined as follows:
r+t(1) The graph G1 is defined by the regular expression (0 + 1))∗ . That is, the set of′the labels of paths that go from c1 into c1 in G1 is precisely the set of strings thatr+t ∗satisfy (0 + 1)
) , or, in other words, that represent annotations of strings in
the first round of the Ck -game for Ψ.
(2) The graph G2i (1 ≤ i ≤ k) is defined by the regular expression that defines all thosestrings in (0 + 1) · ( + ×)r+t )∗ that, in addition, satisfy the following: For eachPi−1Pi
1 ≤ j ≤ h=1 rh + h=1 th , exactly one box located j positions to the right of anPi
Pi−1
occurrence of 0 or 1 is ×, and for each h=1 rh + h=1 th < j ≤ r + t, each box
located j positions from a 0 or a 1 is .
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:33

That is, G2i (1 ≤ i ≤ k), seen as an NFA with initial state c2i and final state c′2i ,defines exactly those strings that represent valid annotations of strings in the Ck game for Ψ precisely after stage (2i − 1) of the game has been played. Indeed, eachvariable that appears in the first (i − 1) blocks ∀x1 ∃y1 · · · ∀xi−1 ∃yi−1 is assigned
to a unique position in the annotated string (represented by the fact that for each
Pi−1
Pi−1
1 ≤ j ≤ h=1 rh + h=1 th , exactly one box located j positions to the right of an
occurrence of 0 or 1 is ×), each quantifier in xi is assigned to a unique position in
Pi−1
Pi−1
the annotated string (represented by the fact that for each h=1 rh + h=1 th < j ≤Pi
Pi−1
h=1 rh +h=1 th , exactly one box located j positions right of an occurrence of 0
or 1 is ×), and no other variable is assigned to a position in the string (represented
by the fact that for each position located j positions to the right of a 0 or a 1 is ,Pi−1
Pi
where h=1 rh + h=1 th < j ≤ r + t).
(3) The graph G2i+1 (1 ≤ i < k) is defined by the regular expression that defines all
those strings in (0 + 1) · ( + ×)r+t )∗ that, in addition, satisfy the following: For
Pi
Pieach 1 ≤ j ≤ h=1 rh + h=1 th , exactly one box located j positions to the right ofPPan occurrence of 0 or 1 is ×, and for each ih=1 rh + ih=1 th < j ≤ r + t, each box
located j positions from a 0 or a 1 is .
That is, G2i+1 (1 ≤ i < k), seen as an NFA with initial state c2i+1 and final statec′2i+1 , defines exactly those strings that represent valid annotations of strings in
the Ck -game for Ψ precisely after round 2i of the game has been played. Indeed,each variable that appears in the first i blocks ∀x1 ∃y1 · · · ∀xi ∃yi is assigned to aunique position in the annotated string (represented by the fact that for each 1 ≤PiPij ≤ h=1 rh + h=1 th , exactly one box located j positions right of an occurrence of 0
or 1 is ×), and no other variable is assigned to a position in the string (represented
by the fact that for each position located j positions from a 0 or a 1 is , wherePi
Pi
h=1 rh +h=1 th < j ≤ r + t).
(4) Finally, we define the graph G2k+1 to be the intersection of the language defined by(0 + 1) · ( + ×)r+t )∗ and the regular language of annotated strings satisfying ψ,
for which there is a standard exponential-time construction of NFA from FO logic(recall that ψ is quantifier-free). That is, G2k+1 , when seen as an NFA with initialstate c2k+1 and final state c′2k+1 , accepts precisely the annotations of strings thatsatisfy ψ. As we shall see later, with the help of ϕk we can enforce that these correspond to valid annotations of strings in the Ck -game for Ψ precisely after round2k + 1 of the game has been played.
The graph database G is constructed from G1 , . . . , G2k+1 by adding an ℓ-labeled edge
from c′i into ci+1 , for each 1 ≤ i ≤ 2k, as shown in the following figure:

c1

G1

c′1

ℓ
c2

G2

c′2

ℓ

...

ℓ
c2k+1

G2k+1

c′2k+1

Clearly, each Gi can be constructed in exponential time from the Ck formula ψ, andhence G can also be constructed in exponential time.
To conclude, it is not hard to prove that there is a binary string w̄ that satisfies ψ if
and only if G |= ϕk , where G is as constructed above from Ψ. Indeed, assume first that
G |= ϕk . Then G |= ∃x∃y∃π1 ((x, π1 , y) ∧ R′ (π1 ) ∧ θ1 (y, π1 )), and θ1 (y, π1 ) is of the form∃z(ℓ(y, z) ∧ · · · ). Since π1 has to satisfy R, this implies that π1 can only be witnessed
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:34

Pablo Barceló et al.

in G by a path ρ1 inside G1 . Further, since there is an outgoing edge labeled ℓ fromthe endpoint of ρ1 , this path can only go from c1 into c′1 (and hence x and y can only
be witnessed in G by nodes c1 and c′1 , respectively). Thus, the label of ρ1 represents
the annotation of a string w̄ at the beginning of round 1 of the game for Ψ (that is, ther+t ∗“annotated” string belongs to the language defined by (0 + 1)
) ). We claim that w̄
satisfies Ψ, and hence that Ψ is satisfiable inside the class of σ-structures. We explain
below why this is the case.
One can prove the claim by a simple but rather cumbersome inductive argument.
We omit this argument for the sake of readability and rather provide its underlying
intuition. Since G |= θ1 (c′1 , ρ1 ), it means that
G |= ∃x ℓ(c′1 , x) ∧ ∀z∀π2 (x, π2 , z) ∧ R(ρ1 , π2 ) →∃u∃y∃π3 (ℓ(z, u) ∧ (u, π3 , y) ∧ R(π2 , π3 ) ∧ θ2 (y, π3 ) .
Thus, variable x in the previous formula can only be witnessed in c2 . Then for every
node z and every path ρ2 that goes from c2 to z in G and is in the relationship R to ρ1
the following holds:— z has an outgoing edge labeled ℓ to a node u;— there is a node y such that there is a path ρ3 from u to y that is in the relationship
R to ρ2 ; and— G |= θ2 (y, ρ3 ), in particular, G |= ∃xℓ(y, x).
Notice that there is a unique node z in G such that G |= ∃π2 (c2 , π2 , z) ∧ R(ρ1 , π2 ).
This node is precisely c′2 and π2 is any path ρ2 from c2 into c′2 that encodes precisely
the same binary string w̄ as ρ1 . The reason is that since R(ρ1 , ρ2 ) holds, ρ2 must encode
the same binary string as ρ1 . Further, ρ2 does not mention the letter ℓ, and hence it can
only be witnessed in G inside G2 . Moreover, ρ2 has the same length as ρ1 , and, thus,
its last node can only be c′2 . Since ρ2 goes from c2 into c′2 it encodes a proper annotationof the variables x1 over w̄.
Hence for every path ρ2 that encodes a proper annotation of x1 over w̄, there is path
ρ3 that starts in c3 and that is in the relationship R to π2 . Thus, for the same reasons
given in the previous paragraph, ρ3 goes from c3 into c′3 inside G3 , and it encodes thesame binary annotation of x1 over w̄ than ρ2 , but this time extended with a proper
annotation of y1 .
Summing up, we have that for every proper annotation x1 over w̄ there exists a
proper annotation of y1 over w̄, encoded by path ρ3 , such that G |= θ2 (c′3 , ρ3 ). By continuing this process iteratively, we can conclude that for every proper annotation of x1
over w̄ there exists a proper annotation of y1 over w̄, such that ... for every annotationof xk over w̄ there exists a proper annotation of yk over w̄, and that this final annotation of a string is encoded in the path ρ2k+1 that witnesses the variable π2k+1 in G. But
by following essentially the same arguments used above, one can show that π2k+1 canonly be witnessed in G by a path ρ2k+1 that goes from c2k+1 into c′2k+1 in G2k+1 . This
path must encode a valid annotation of w̄ that satisfies Ψ. Therefore, we conclude thatw̄ satisfies Ψ.
The opposite direction, that is, that G |= ϕk follows from the fact that ϕ is satisfiablein the class of σ-structures, can be proved with a similar argument.
We know of course that the containment problem is undecidable for ECRPQs, andthus for ECRPQ¬ queries. We remark that even a simpler satisfiability problem, asking whether for a Boolean ECRPQ¬ query ϕ there is a graph database G such that
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:35

ϕ(G) = true, is undecidable. This is because the finite satisfiability problem for arbitrary FO formulas over binary predicates can easily (and effectively) be encoded into
the satisfiability problem for ECRPQ¬ formulas.
8.2. Adding non-regular relations

A well-known class viewed as a natural extension of regular relations is the class ofrational relations. Binary rational relations can be viewed as sets of pairs (s, s′ ) ofstrings over Σ such that s′ is a possible output of a nondeterministic transducer on s.
However, a standard PCP reduction shows the following:
P ROPOSITION 8.4. If rational relations are allowed in place of regular relations in
ECRPQs, then the query evaluation problem becomes undecidable.
P ROOF. We reduce from the following version of the correspondence problem, which
is known as PCP. Given two equally long ordered lists a1 , a2 , . . . , an and b1 , b2 , . . . , bn ofstrings over alphabet Σ, decide whether there exists a sequence of indices i1 , i2 , . . . , ik
such that 1 ≤ ij ≤ n (1 ≤ j ≤ k) and ai1 ai2 · · · aik = bi1 bi2 · · · bik .
Assume without loss of generality that Σ is disjoint from N. Corresponding to every
input a1 , a2 , . . . , an and b1 , b2 , . . . , bn of PCP over alphabet Σ, we define the following:— An alphabet Σ(n) := Σ ∪ {1, 2,
S . . . , n};— a regular language Ra,n := ( 1≤i≤n ai · i)∗ ;S— a regular language Rb,n := ( 1≤j≤n bj · j)∗ ;— for each Σ′ ⊆ Σ(n), a binary rational relation RΣ′ that contains all pairs (w1 , w2 ) ofstrings over Σ(n) such that w1 is precisely the restriction to the alphabet Σ′ of thestring w2 .
We now define a Boolean ECRPQ Q, that makes use of rational relations over alphabet Σ(n), as follows:Ans() ←^

(xi , πi , yi ), Ra,n (π1 ), Rb,n (π2 ), R{1,2,...,n} (π3 , π1 ),1≤i≤4

R{1,2,...,n} (π4 , π2 ), π4 = π3 , RΣ (π5 , π1 ), RΣ (π6 , π2 ), π5 = π6 ,Σ(n)and a graph G, that is exactly the graph GR that is used in the proof of the hardness
Σ(n)part of Theorem 6.3. That is, for each node v ∈ GR and string w ∈ Σ(n), there is aΣ(n)path ρ ∈ GR that starts at v and such that λ(ρ) = w.
It is now straightforward to prove that G |= Q iff there is a solution for the PCP problem for the given input. This shows that the problem of query evaluation for ECRPQs
that make use of rational relations is undecidable.
Hence, we need to work with weaker extensions. We now look at two such examples.
Linear constraints on the number of occurrences of events. It is common
to have preferences for one event over another when querying graph databases. For
example, when planning an itinerary from London to Sydney, a Singaporean mightwant to find a sequence of flights with Singapore Airlines for at least 80% of the entire
journey duration. In this case, only the ratio on the number of occurrences of events
matter, not the order in which they occur. We will now extend ECRPQs with linear
constraints on the number of occurrences of events. Suppose that we deal with graphdatabases over the alphabet Σ = {a1 , . . . , ak }. Then, ECRPQs with linear constraints
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:36

Pablo Barceló et al.

on the number of occurrences of events are of the form:^^Ans(z̄, χ̄) ←(xi , πi , yi ),Rj (ω̄j ), Aℓ̄ ≥ b ,1≤i≤mwhere Ans(z̄, χ̄) ←V

1≤i≤m (xi , πi , yi ),

(7)

1≤j≤t

V

1≤j≤t Rj (ω̄j ) is a ECRPQ as in (2), and— A is a h × (k · m) matrix over Z, for some h > 0;
— b is a vector in Zh ; and— ℓ̄ = (ℓ1,1 , · · · , ℓ̄1,k , . . . , ℓm,1 , · · · , ℓm,k ).
The semantics is extended as follows: each ℓi,j (1 ≤ i ≤ m and 1 ≤ j ≤ k) is interpreted
as the number of occurrences of event (symbol) aj in the path πi . The last clause of thequery is true if Aℓ ≥ b under this interpretation. In an analogous way we define theclass of CRPQs with linear constraints on the number of occurrences of events.
Before proving our main results on CRPQs and ECRPQs extended with linear constraints on the number of occurrences of events, let us first revisit the above example
on finding an itinerary from London to Sydney with Singapore Airlines for 80% of theentire journey duration. One way to achieve this is to represent a graph database offlights in such a way that each aj -labeled edge constitutes a small fixed fraction (e.g.
10 minutes) of a flight with the airline aj . (If our graph database has cities as nodes
and “full” flights as edges, we could introduce “intermediate” nodes and edges to indicate time information). In fact, supposing that a1 indicates flights with Singapore
Airlines, we could replace a2 , . . . , ak with the event label a2 to indicate “flights withairlines other than Singapore Airlines”. The desired query is expressible as a CRPQ
with linear constraints on the number of occurrences of events as follows:Ans() ← (London, π1 , Sydney), (a1 − 4a2 ≥ 0).
T HEOREM 8.5.
— The combined complexity of ECRPQs with linear constraints on the number of occurrences of events is P SPACE-complete.
— The combined complexity of CRPQs with linear constraints on the number of occurrences of events is NP-complete.
— For both classes of queries, data complexity is in NL OGSPACE.
Thus, from the point of view of overall complexity, adding comparisons on the number of occurrences of events is free, as it does not increase the complexity of ECRPQs
and CRPQs.
P ROOF. We start by proving the second part of the theorem. To this end, we need
the notion of Parikh images of string languages. Fix an ordering of the alphabet Σ ={a1 , . . . , ak } of the language under consideration, say, a1 < . . . < ak . Given a string w
over Σ, the Parikh image par(w) of w is a tuple (|w|a1 , . . . , |w|ak ) ∈ Nk , where |w|a counts
the number of occurrences of a in the string w. The Parikh image of a language L over
Σ is simply the set Lpar := {par(w) : w ∈ L} ⊆ Nk . We will also use the linear timetranslation by Verma et al. [2005] from a given NFA A to an existential Presburger
formula ϕA (x1 , . . . , xk ) capturing the Parikh image of the language L of A, i.e., for eachtuple n̄ ∈ Nk it is the case that n̄ ∈ Lpar iff the formula ϕA (n̄) holds.
Let us assume that the input consists of a formula ϕ of the formAns(z̄, χ̄) ←m^(xi , πi , yi ),

i=1

t
^

Lr (ωr ), Aℓ̄ ≥ b ,r=1

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:37

a graph database G over the alphabet Σ = {a1 , . . . , ak }, and a mapping ν from nodevariables z̄ to nodes in G, and path variables χ̄ to paths in G. An NP procedure M forchecking whether (ν(z̄), ν(χ̄)) ∈ ϕ(G) works as follows. First, M guesses an assignment
σ to the node variables xi and yi , while making sure that σ agrees with ν. It thenconstructs in polynomial time an existential Presburger formula ψ with free variables
X = {xi,j }1≤i≤m,1≤j≤k such that, for any mapping α : X → N, it is the case that ψis true under α iff (ν(z̄), ν(χ̄)) ∈ ϕ(G) under the assignment (σ, µ), where µ is someassignment of path variables πi ’s to paths ρi such that |ρi |aj = α(xi,j ) for each j =1, . . . , k. Since checking satisfaction of existential Presburger formulas can itself bedone by an NP procedure (e.g. see [Scarpellini 1984]), this will prove that the procedure
M is an NP procedure. It remains to give the construction of ψ.
Without loss
i.e., each πi appears
Vm in the big
Vt of generality, we assume that m = t, Vtconjunction r=1 Lr (ωr ). That way, we may rewrite r=1 Lr (ωr ) as i=1 Li (πi ). For
each i = 1, . . . , m, the procedure M considers whether πi appears in χ̄. If it does, thenit checks in polynomial time that σ(xi ) reaches σ(x′i ) under the path ν(πi ), and thatν(πi ) ∈ Li . If the check is not successful, M rejects. If this check is successful, for eachj = 1, . . . , k, the variable ℓi,j in ℓ̄ is replaced by the number |ν(πi )|aj of times aj appears in ν(πi ). In the case when πi does not appear in χ̄, the procedure M applies thelinear-time translation of Verma et al. [2005] on the NFA Ai obtained via the standard product construction on the graph G construed as an NFA with initial state σ(xi )and final state σ(x′i ) and the NFA for Li yielding an existential Presburger formulaϕi (ℓi,1 , . . . , ℓi,k ) capturing the Parikh image of Ai . The desired formula is!
m^ϕi (ℓi,1 , . . . , ℓi,k ) ∧ Aℓ̄ ≥ b .
∃ℓ̄
i=1

Notice that this formula is of size polynomial in the size of the input. This completes
the proof of the second part of the theorem.
In order to prove the first and third parts of the theorem, we will use the notion ofreversal-bounded counter automata. A k-counter automaton over the alphabet Σ is atuple A = (Q, X, Σ, δ, q0 , qF ) where— Q is a finite set of control states,— X = {x1 , . . . , xk } is a set of k counter variables,— q0 ∈ Q is an initial state,— qF ∈ Q is a final state, and— δ is a finite subset of (Q × ConsX ) × Σǫ × (Q × {−1, 0, 1}k ), where Σǫ := Σ ∪ {ǫ} andVk
ConsX is the set of “counter tests” of the form i=1 xi ∼i 0, where ∼i ∈ {=, >} foreach i = 1, . . . , k.
A configuration of A is a tuple of the form (q, v) ∈ Q × Nk , which indicates the state A
is in and the values of the k counters. A run σ of A is a sequence of configurations(q0 , v0 ) →a1 . . . →an (qn , vn )where
— each qi ∈ Q, and q0 is the initial state,— v0 = 0, and— for each i = 0, . . . , n − 1, there exists a transition(qi , ϕ(x̄), ai , qi+1 , u)such that ϕ(vi ) holds and vi+1 = vi + u.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:38

Pablo Barceló et al.

The run σ is accepting if qn is the final state qF . In this case, we say that the string
a1 . . . an is accepted by A. The language L(A) of A is the set of strings accepted by A. For
each r ∈ N, the run σ is said to be r-reversal-bounded if, for each counter xi , the numberof reversals between non-incrementing and non-decrementing modes of the value of xi
in σ is at most r. For example, if the value of xi in σ is 0, 1, 1, 1, 2, 3, 4, 4, 4, 3, 2, 2, 3, then
the number of reversals of x is 2 (reversals occur in between the overlined positions).
An r-reversal k-counter automaton over Σ is a tuple (A, r), where A is k-counter automaton over Σ. The language of (A, r) is simply the set of strings accepted by A witha witnessing run that is r-reversal-bounded. When r is understood, we simply refer to(A, r) as A.
We proceed to the proof of the first and third parts of the theorem. Suppose that the
input consists of a query ϕAns(z̄, χ̄) ←

m
^

i=1

(xi , πi , x′i ),^Rj (ω̄j ), Aℓ̄ ≥ b ,1≤j≤t

a graph database G over Σ = {a1 , . . . , ak }, and a mapping ν from node variables z̄ tonodes in G, and path variables χ̄ to paths in G. We proceed by proving a technicallemma stating a “small model property” of the query ϕ.
L EMMA 8.6. If (ν(z̄), ν(χ̄)) ∈ ϕ(G), then there exists a satisfying assignment of pathvariables in {ω̄j }tj=1 of length at most polynomial in |G| + |ν| and exponential in |ϕ|.
We first show how the first and third parts of the theorem follow from this technicallemma. It suffices to give a nondeterministic polynomial (respectively, logarithmic)
space Turing machine M for combined (respectively, data) complexity. Initially, theTuring machine M guesses an assignment σ to the node variables, while making surethat σ is consistent with ν. Note that |σ| = O(m log(|G|)) = O(|ϕ| log(|G|)) since thenodes in the graphs can be named as numbers written in binary (and so requires
only log(|G|) many bits). The machine M now proceeds to the stage of simultaneously
guessing the paths {πi }mi=1 . To do so, it will “nondeterministically walk through” thegraph G (from different starting nodes simultaneously) and the NFAs {Rj }tj=1 . The
machine M has a variable vi stored on its working tape to remember the “current”
node in the path πi , initially setting vi to be σ(xi ). Likewise, M has a variable uj toremember the current state of the NFA Rj , initially setting uj to be the initial state of
Rj . Additionally, we need to keep track of the following information:— For each path variable π and each symbol a ∈ Σ, how many a’s have been seen so far
in π.
— The number of input letters that have been read so far.
Walking through this graph and the NFAs is simple: at each iteration stage, we nondeterministically guess a letter in Σm⊥ while making sure that they are consistent withthe path assignments in ν, which can be easily done since M keeps track of the numberof input letters that have been read so far. After this, we guess the next move for each
NFA and the graph G while incrementing the counters appropriately. The simulation
stops if any one of the following conditions is satisfied:(1) The number of input letters that have been guessed reaches the maximum limit
given by the above lemma.
(2) Each variable vi is set to σ(x′i ), each variable uj is set to the final state of the NFA
Rj , and the linear constraints evaluated against the variables as recorded in the
counters are satisfied.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:39

In the first case, the input formula is false. In the second case, the input formula
is true. Since numbers can be represented in binary in the work tape of the Turingmachine, this simulation takes space polynomial in |ϕ|, and logarithmic in |G| + |ν|.
This completes the proof of the first and third parts of the theorem.
We now proceed to the proof of the above technical lemma. Suppose that(ν(z̄), ν(χ̄)) ∈ ϕ(G), where the ground node variables in ϕ are satisfied by the nodevaluation σ. Suppose ϕ′ is obtained by dropping the linear constraints Aℓ̄ ≥ bfrom ϕ. We have shown in the proof of Theorem 6.3 that there exists an NFA A =(Q, (Σ⊥ )m , ∆, q0 , qF ) capturing ϕ′ (G) whose number of states is polynomial in |G| + |ν|and exponential in |ϕ′ |. Since the query ϕ has counting constraints, we modify theconstruction of the automaton A by introducing an unbounded counter xi,j (for eachi = 1, . . . , m and j = 1, . . . , k) for counting the numbers of occurrences of the letter aj inthe path ρi as the NFA A′ traverses the input strings ρ̄ = ρ1 ⊗. . .⊗ρm over the alphabet(Σ⊥ )m instantiating the path variables ϕ̄ = (π1 , . . . , πm ). Note that, in doing so, we do
not introduce extra states in A; we merely add appropriate counter increments in theoriginal transition relation ∆ in A. If we use non-succinct counter automaton representation, the modified transition relation will be of size at most |∆| × 2m+k ≤ |A| × 2m+k .
After the entire input string has been fully read and qF is reached, we need to additionally ensure that Aℓ̄ ≥ b is satisfied. To this end, let us assume that qF is a “deadend”, i.e., has no outgoing transition in ∆. Bringing each summand with negative coefficient to the left hand side of the inequality ensures that each summand in the system
of inequalities has a positive coefficient. Let us now add to A an extra counter for eachside of each inequality, i.e., a total of 2h extra counters y1 , . . . , yh and y1′ , . . . , yh′ for, respectively, left and right sides of the inequalities. From qF , the automaton A will start
decrementing each of the xi,j until all of them are zero. Additionally, while decrementing the counter xi,j by one, for each r = 1, . . . , h the automaton A adds the absolutevalue of A[r, i × j] (i.e. the coefficient of the variable ℓi,j in the rth inequality counting
the number of occurrences of event ai in ρj ) to the new counter yr or yr′ depending
whether or not A[r, i × j] is positive. Likewise, we need to add the absolute value of br
to either yr or yr′ depending whether or not br is positive. After all of the xi,j counters
have been decremented to zero, we make sure that yr ≥ yr′ holds for each r = 1, . . . , hby stepping through each pair yr and yr′ of variables and decrementing yr and yr′ at thesame time making sure at the end we have yr′ = 0∧yr = 0 or yr′ = 0∧yr > 0. Notice thatthe resulting non-succinct counter automaton A is 1-reversal-bounded (i.e. all runs of
A are 1-reversal-bounded) and has 2h + mk counters. Furthermore, since we assume abinary representation of numbers in the matrix A and vector b, the number of statesin A is polynomial in |G| + |ν| and exponential in the size |ϕ| of the input query ϕ.
We now make use of the following recent result on the Parikh images of non-succinct
reversal-bounded counter automata from [To 2010]:
P ROPOSITION 8.7. Given an r-reversal-bounded k-counter automaton B with nstates over an alphabet of size m, the Parikh image of its language can be represented as a disjunction of existential Presburger formulas each of size polynomial inr + k + m + log(n) with at most O(rk + m) variables.
In this proposition, the (in)equalities inside the Presburger formulas allow arbitrarily many summands on both sides of the (in)equalities, where each summand allows
multiplication by an integer constant represented in binary. This proposition is a paraphrase of [To 2010, Proposition 7.5.2], where integer constants are represented inunary. For the sake of completeness, we provide a proof in the appendix. Now, applying this proposition on the counter automaton A that we just constructed, it follows
that the Parikh image of the language L of A can be represented as a disjunction ofexistential Presburger formulas each of size polynomial in 2h + mk + |ϕ| log(|G| + |ν|)ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:40

Pablo Barceló et al.

with at most O(2h+mk) variables. Scarpellini [Scarpellini 1984, Theorem 6 (a)] provedthat a satisfiable existential Presburger formula θ with c variables has solutions where
each variable is assigned a number that is exponential in |θ| and in c. Using this result, it follows that if the Parikh image of L is nonempty, then it contains a tuplen̄ = (n̄1 , . . . , n̄m ) with each n̄i = (ni,1 , . . . , ni,k ) and each ni,j is polynomial in |G| + |ν|Pk
and exponential in |ϕ|. Note that j=1 ni,j equals the length of the path assignment inΣ∗ for the path variable πi witnessing the tuple n̄ in the Parikh image of L. Therefore,
the above lemma immediately follows.
Theorem 8.5 shows that comparisons on the number of occurrences of events can be
added “for free” to ECRPQs, at least in terms of the complexity of query evaluation.
A natural question at this point is whether this is also true for the class ECRPQ¬ .
That is, can linear constraints on the number of occurrences of events can be added to
ECRPQ¬ without making query evaluation more expensive? We provide next a strong
negative answer to this question. Indeed, we show in Theorem 8.8 that the problem ofquery evaluation for the class ECRPQ¬ , extended with a very light form of counting
the number of occurrences of events, becomes undecidable. Recall that Theorem 8.1
states, on the other hand, that query evaluation for the class ECRPQ¬ is decidable.
Linear constraints on lengths of paths. One important application of ECRPQs
with linear constraints on the number of occurrences of events is for comparing path
lengths. We define a class of CRPQs with linear constraints on lengths of paths as^^
Ans(z̄, χ̄) ←(xi , πi , yi ),Lj (ωj ), Aℓ̄ ≥ b ,1≤i≤mwhere Ans(z̄, χ̄) ←V

1≤i≤m (xi , πi , yi ),

1≤j≤t

V

1≤j≤t Lj (ωj ) is a CRPQ as in (1), and— A is a k × m matrix over Z, for some k > 0;
— b is a vector in Zk ; and— ℓ̄ = (ℓ1 , . . . , ℓm ).
The semantics is extended as follows: each ℓi is interpreted as the length of the path
πi , for i ≤ m. The last clause of the query is true if Aℓ ≥ b under this interpretation.
That is, we extend CRPQs with the ability to add k > 0 linear constraints on lengthsof paths. Observe that the length of a path ρ in a graph database over the alphabetPΣ = {a1 , . . . , ak } coincides with the sum kj=1 |ρ|aj . This implies that ECRPQs withlinear constraints on lengths of paths can be easily expressed as ECRPQs with linear
constraints on the number of occurrences of events, but the contrary is not true. Hencethe former class of queries can be considered to be a proper restriction of the latter.
In the same way that ECRPQs were extended with negation in Section 8.1, we can
add negation to the class of ECRPQs with linear constraints on the lengths of paths.
We omit the definition of such an extension for the sake of simplicity, but both thesyntax and the semantics can be easily obtained from the corresponding syntax andsemantics of the following classes of queries: ECRPQs with linear constraints on thelengths of paths and ECRPQ¬ .
We shall conclude this section by showing that adding both negation and linear constraints on path lengths to ECRPQs yields undecidability, therefore showing the tightness of the extensions that we obtained earlier in this section. In fact, undecidability
holds for a fixed formula in this extended query language.
T HEOREM 8.8. There exists a fixed and Boolean ECRPQ query ϕ with negation andlinear constraints on lengths of paths, such that it is undecidable to check whether ϕholds in a graph database G.
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:41

P ROOF. The reduction is from the acceptance problem for a fixed and deterministic
Turing machine (TM). Suppose that the fixed TM is M = (Σ, Γ, Q, δ, q0 , qF ), whereΣ = {0, 1} is the input alphabet, Γ = Σ ∪ {B} is the tape alphabet consisting of the
input alphabet and the blank symbol B, Q is a finite set of control states, q0 ∈ Q (resp.
qF ∈ Q) is the initial (resp. final) state, and δ : Q × Γ → (Q × Γ × D) is the transition
function where D = {L, R} indicates the direction of the movement of the head of theTM (L for left and R for right). We assume without loss of generality that q0 6= qF .
A configuration C of M is a string in the regular language Σ∗ QΣ∗ B∗ . For convenience,a configuration vqwB · · · B, where v, w ∈ Σ∗ and q ∈ Q, may be thought of as follows. The
tape of M contains the word vw and the head of M is scanning the last letter of v instate q. The length of C is the number of symbols in C that are not in Q. A sequenceof configurations of M representing a computation of M on an input word w ∈ Σ∗
can then be represented as a string of the form π = C1 #γ1 C2 #γ2 . . . #γm−1 Cm , where
each #γ is a delimiter symbol with γ ∈ {L, R}, C1 is q0 wBk , the initial configuration oflength n = |w| + k (for some k ≥ 0 depending on w), Cm is qF Bn , the final configurationof length n (we assume that on acceptance the tape content is erased), and each Ci
is a configuration of M of length n. Since the number k is existentially quantified,
imposing a space upper bound on the tape of the TM of size k is not a limitation.
As we will soon see, the subscript γ (i.e. left/right) for a delimiter symbol is used toindicate the direction of the movement of the head of the TM. In particular, given a
substring Ci #γ Ci+1 of π, we shall use γ to indicate that the position of the head of
the TM in Ci+1 has moved in the direction γ with respect to the head of the TM in Ci .
In the following, we use the symbol # as an abbreviation (or macro) for the regularexpression (#L + #R ).
We now proceed with the reduction. The input to the problem is a string w ∈ {0, 1}∗
and the problem is to check whether w is accepted by M. We construct a graph G over
the alphabet Γ ∪ Q ∪ {#L , #R } and a fixed formula ϕ such that w is in the language of
M iff G |= ϕ. The main trick for the reduction is to “hardwire” w into the graph G andmake the formula ϕ guess an accepting computation π of M on w. Notice that such a
computation is a string in the regular language generated by the regular expression
E := q0 wB∗ #(Σ∗ QΣ∗ B∗ #)∗ qF B∗ .
We will embed E (construed as an NFA) into G as a subgraph with distinguishednodes. In addition to checking that the guessed computation π is in L(E), we also needto check that each configuration in π has the same length n. This can be expressed in
the fixed formula ϕ as follows:(1) Let v0 be the longest prefix of π of the form q0 Σ∗ B∗ . (This will ensure that v0 coincides with the first configuration in π before any occurrence of the symbol #. Thisrequires at least three path quantifiers which alternate).
(2) Assert that the last configuration is of length |v0 |: if v is the longest prefix of π with# as the last symbol, then |π| − |v| = |v0 |.
(3) Assert that each intermediate configuration is of length |v0 |: for each pair of prefixes v ≺ v ′ of π both ending withthe symbol # such that there is precisely⊥
one occurrence of the symbol #in the convolution v ⊗ v ′ , it is the case that|v ′ | − |v| − 1 = |v0 |.
(4) Assert that for each substring C#γ C ′ of π, where C, C ′ are configurations of A, it
is the case that the head position in C ′ is one position to the left/right of the head
position in C and agrees with γ. To this end, we universally guess two prefixesv  v ′ of π such that (i) v ends with #γ , (ii) the convolution v ⊗ v ′ has precisely⊥
one symbol of the form #and (iii) the smallest prefix v ′′ of π such that v ′ ≺ v ′′ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:42

Pablo Barceló et al.

ends with the symbol # (i.e. the next letter after v ′ is a delimiter symbol). Thismeans that v ends with C#γ and the suffix of v ′ that comes after v represents
the configuration C ′ . We shall only show how to express this assertion for the casewhen the state symbol in C is not in the left/right-most cell of the tape leaving thereader to handle the exceptions as simple exercises. Let u and u′ be the longest
prefixes of v and v ′ ending in symbols in Q. In the case when γ = L, we assert that|u′ | = |u| + |v0 | − 1 + 1 (note that there is the delimiter symbol #γ ). In the case whenγ = R, we assert that |u′ | = |u| + |v0 | + 2.
(5) Assert that for each substring C#γ C ′ of π, where C, C ′ are configurations of A,
it is the case that the configuration C ′ follows from its previous configuration C(with respect to the transition function δ). We first give the rough idea of how toassert this. Suppose that abqc (resp. a′ b′ q ′ c′ ) is a substring of C (resp. C ′ ), wherea, a′ , b, b′ c, c′ ∈ Γ and q, q ′ ∈ Q (of course, we also need to take into account sometedious exceptions, e.g., if C ends with a state symbol, then we may assume that cis the symbol #). Leaving the reader to handle the exceptions as exercises, we may
assume that all a, b, c are in Γ. Then, we will make the first assertion (A1): either
δ(q, b) = (q ′ , c′ , L) and γ = L OR δ(q, b) = (q ′ , a′ , R) and γ = R. The second assertion(A2) is that: other symbols in C must stay the same in C ′ . The first assertion canbe done by guessing two prefixes v and v ′ of π, where v ends with C#γ and v ′ends with C ′ , and constructing a fixed1 NFA running on the convolution v ⊗ v ′ , i.e.,
the NFA will need to remember the symbols abqc and a′ b′ q ′ c′ in the finite control
and check these against the transition function δ as we previously described, while
making sure of seeing precisely one occurrence of #⊥γ (and no occurrence of #⊥ ′γ
where γ ′ ∈ D − {γ}). The second assertion can be expressed in the same way as theprevious item.
Correctness of our reduction is immediate. Observe also that the construction of theformula ϕ depends solely on the TM A, which is not part of the input. Therefore, theconstructed formula ϕ is fixed and takes constant time to compute. Notice also thatthe input string w is now part of the graph database G.
9. COMPARISON WITH OTHER LANGUAGES

The language of ECRPQs was motivated by recent proposals of graph database queries
that can compare and output paths. One of them is the language of ρ-queries [Anyanwu
and Sheth 2003], which allows to specify and check properties based on specific semantic associations. It is not possible to directly compare the language of ρ-queries with thelanguages of ECRPQs, since the former is defined over a different data model (namely,
RDF/S). However, at a high level we can see that ECRPQs have more flexibility whenit comes to defining semantic associations among paths. In fact, we can make use of arbitrary regular relations, while ρ-queries are defined with respect to a predetermined
set of similarity measures.
Several other navigational languages for path specifications can be found in thegraph database and RDF literature. While many of these languages can check whether
the label of a path belongs to a particular regular language, none of them have the facilities for comparing labels of different paths, which is a distinctive feature of the ECRPQs. An example is the language of nested regular expressions [Barceló et al. 2012],
which forms the basis of the navigational RDF language nSPARQL [Pérez et al. 2010].
It is not hard to see that nested regular expressions and ECRPQs are incomparable
in terms of their expressive power. In fact, while nested regular expressions permit
1 Recall that the TM is not part of the input.

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

Complexity
data
combined

Complexity
data
combined

A:43

Acyclic
CQs
CRPQ
ECRPQ
CRPQ
ECRPQ
AC0
NL-c.
NL-c.
NL-c.
NL-c.
NP-c.
NP-c. P SPACE-c. P TIME P SPACE-c.
(a) CQs, CRPQs, ECRPQs, and subclasses

ECRPQ
Qlen
NL-c.
NP-c.

with repetitions
CRPQ
ECRPQ

CRPQ +
linearconstraints
P TIME
NP-c.

with negation
CRPQ
ECRPQ

NL-c.
NL-c.
NL-c.
nonP SPACE-c. P SPACE-c. P SPACE-c. elementary(b) Extensions of CRPQs and ECRPQs
Fig. 1. Summary of complexity results for classes of queries

complex branching patterns over graph-structured data that are inexpressible in thelanguage of ECRPQs, even the simplest path comparisons are beyond reach for the
language of nested regular expressions. The same is true for several other importantnavigational RDF languages, such as the language of SPARQL extended with regularexpression patterns, PSPARQL [Alkhateeb et al. 2009], and its extended version withconstraints, CPSPARQL [Alkhateeb et al. 2008].
While the usual RDF query language SPARQL provides limited navigational capabilities over the data, its more recent version, SPARQL 1.1, allows the specification ofproperty paths. These are essentially regular expressions that specify pairs of nodes
linked by a path whose label belongs to the expression. While SPARQL 1.1 can specify
complex path expressions, in its current form it completely lacks operations for pathcomparisons. One of the goals of our work is to sufficiently advance the foundations of
the query languages that compare paths, in order to draw a clear picture of what could
and could not be implemented by the W3C (and others) in the future.
10. SUMMARY

The tables in Figure 1 give a summary of the complexity results; they also include,for comparison, known results on CQs and CRPQs in the first two columns of (a). We
use the abbreviation NL for NL OGSPACE; ’-c.’ means, of course, that the problem iscomplete for the class. In the case of data complexity, it means that the problem isin a given class for all queries, and can be hard for the class for some of them. In
addition to these complexity results, our technical results also include algorithms forquery evaluation and representation of paths in the output as well as results on querycontainment.
Acknowledgments We thank the referees of both this paper and its conference version for their helpful comments. Supported in part by: Fondecyt grant 1110171 (Barceló), EPSRC grants G049165 and J015377, and FET-Open project FoX, grant agreement FP7-ICT-233599 (Libkin), and EPSRC grant H026878 (Lin).
ELECTRONIC APPENDIX

The electronic appendix for this article can be accessed in the ACM Digital Library.
REFERENCES
A BITEBOUL , S., B UNEMAN, P., AND S UCIU, D. 1999. Data on the Web: From Relations to Semistructured
Data and XML. Morgan Kauffman.

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:44

Pablo Barceló et al.

A BITEBOUL , S., Q UASS, D., M C H UGH , J., W IDOM , J., AND W IENER , J. 1997. The LOREL query language
for semistructured data. International Journal on Digital Libraries 1, 1, 68–88.
A BULLA , P., J ONNSON, B., N ILSSON, M., AND S AKSENA , M. 2003. A survey of regular model checking. In
5th International Conference on Concurrence Theory (CONCUR). 35–48.
A LKHATEEB, F., B AGET, J.-F., AND E UZENAT, J. 2008. Constrained regular expressions in SPARQL. In
2008 International Conference on Semantic Web & Web Services (SWWS). 91–99.
A LKHATEEB, F., B AGET, J.-F., AND E UZENAT, J. 2009. Extending SPARQL with regular expression patterns(for querying RDF). Journal of Web Semantics 7, 2, 57–73.
A NYANWU, K., M ADUKO, A., AND S HETH , A. P. 2007. SPARQ2L: Towards support for subgraph extraction
queries in RDF databases. In 16th International World Wide Web Conference (WWW). 797–806.
A NYANWU, K. AND S HETH , A. 2003. ρ-queries: enabling querying for semantic associations on the semantic
web. In 12th International World Wide Web Conference (WWW). 690–699.
B ARCEL Ó , P., H URTADO, C. A., L IBKIN, L., AND W OOD, P. T. 2010. Expressive languages for path queries
over graph-structured data. In 29th ACM Symposium on Principles of Database Systems (PODS). 3–14.
B ARCEL Ó , P., P ÉREZ , J., AND R EUTTER , J. 2012. Relative expressiveness of nested regular expressions. In
6th Alberto Mendelzon Workshop on the Foundations of Data Management and the Web (AMW). 180–195.
B ARRETT, C., J ACOB, R., AND M ARATHE , M. 2000. Formal-language-constrained path problems. SIAM
Journal on Computing 30, 3, 809–837.
B ENEDIKT, M., L IBKIN, L., S CHWENTICK , T., AND S EGOUFIN, L. 2003. Definable relations and first-orderquery languages over strings. Journal of the ACM 50, 5, 694–751.
B ERSTEL , J. 1979. Transductions and Context-Free Languages. B. G. Teubner.
B LUMENSATH , A. AND G R ÄDEL , E. 2000. Automatic structures. In 15th Annual IEEE Symposium on Logicin Computer Science (LICS). 51–62.
B RUY ÈRE , V., H ANSEL , G., M ICHAUX , C., AND V ILLEMAIRE , R. 1994. Logic and p-recognizable sets ofintegers. Bulletin of the Belgian Mathematical Society 1, 191–238.
C ALVANESE , D., D E G IACOMO, G., L ENZERINI , M., AND VARDI , M. 2000. Containment of conjunctive regular path queries with inverse. In 7th International Conference on Principles of Knowledge Representation
and Reasoning (KR). 176–185.
C ALVANESE , D., D E G IACOMO, G., L ENZERINI , M., AND VARDI , M. 2002. Rewriting of regular expressions
and regular path queries. Journal of Computer and Systems Sciences 64, 3, 443–465.
C HROBAK , M. 1986. Finite automata and unary languages. Theoretical Computer Science 47, 2, 149–158.
C ONSENS, M. AND M ENDELZON, A. 1990. GraphLog: A visual formalism for real life recursion. In 9th ACM
Symposium on Principles of Database Systems (PODS). 404–416.
D EUTSCH , A. AND T ANNEN, V. 2001. Optimization properties for classes of conjunctive regular path queries.
In 8th International Workshop on Database Programming Languages (DBPL). 21–39.
E LGOT, C. AND M EZEI , J. 1965. On relations defined by generalized finite automata. IBM Journal of Research and Development 9, 1, 47–68.
F LORESCU, D., L EVY, A., AND S UCIU, D. 1998. Query containment for conjunctive queries with regularexpressions. In 17th ACM Symposium on Principles of Database Systems (PODS). 139–148.
F REYDENBERGER , D. AND R EIDENBACH , D. 2010. Bad news on decision problems for patterns. Information
and Computation 208, 1, 83–96.
F REYDENBERGER , D. AND S CHWEIKARDT, N. 2011. Expressiveness and static analysis of extended conjunctive regular path queries. In 5th Alberto Mendelzon International Workshop on Foundations of DataManagement (AMW).
F ROUGNY, C. AND S AKAROVITCH , J. 1991. Rational relations with bounded delay. In 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 50–63.
G RAHNE , G. AND T HOMO, A. 2004. Query answering and containment for regular path queries under distortions. In 3rd International Symposium on the Foundations of Information and Knowledge Systems(FoIKS). 98–115.
G USFIELD, D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational
Biology. Cambridge University Press.
H OLLAND, D., B RAUN, U., M ACLEAN, D., M UNISWAMY-R EDDY, K., AND S ELTZER , M. 2008. Choosing adata model and query language for provenance. In 2nd International Provenance and Annotation Workshop (IPAW).
I BARRA , H., S U, J., D ANG, Z., B ULTAN, T., AND K EMMERER , R. 2002. Counter machines and verification
problems. Theoretical Computer Science 289, 1, 165–189.

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

A:45

K ANZA , Y. AND S AGIV, Y. 2001. Flexible queries over semistructured data. In 20th ACM Symposium on
Principles of Database Systems (PODS). 40–51.
K OCHUT, K. AND J ANIK , M. 2007. SPARQLeR: Extended SPARQL for semantic association discovery. In
4th European Semantic Web Conference (ESWC). 145–159.
K OZEN, D. 1977. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations ofComputer Science (FOCS). 254–266.
L EE , W., R ASCHID, L., S RINIVASAN, P., S HAH , N., R UBIN, D., AND N OY, N. 2007. Using annotations fromcontrolled vocabularies to find meaningful associations. In 4th International Workshop on Data Integration in the Life Sciences (DILS). 247–263.
L EHMANN, J., S CH ÜPELL , J., AND A UER , S. 2007. Discovering unknown connections—the DBpedia relationship finder. In 1st SABRE Conference on Social Semantic Web. 99–110.
L ENSTRA , H. 1983. Integer programming in a fixed number of variables. Mathematical Operational Research 8, 4, 538–548.
M ENDELZON, A. AND W OOD, P. 1995. Finding regular simple paths in graph databases. SIAM Journal on
Computing 24, 6, 1235–1258.
M ILO, T. AND S UCIU, D. 1999. Index structures for path expressions. In 7th International Conference on
Database Theory (ICDT). 277–295.
PAPADIMITRIOU, C. 1981. On the complexity of integer programming. Journal of the ACM 28, 4, 765–768.
P ÉREZ , J., A RENAS, M., AND G UTIERREZ , C. 2010. nSPARQL: A navigational language for RDF. Journalof Web Semantics 8, 4, 255–270.
R OBERTSON, E. L. 1974. Structure of complexity in the weak monadic second-order theories of the natural
numbers. In Conference Record of Sixth Annual ACM Symposium on Theory of Computing. 161–171.
S CARPELLINI , B. 1984. Complexity of subcases of Presburger arithmetic. Transactions of the AMS 284,
203–218.
S HETH , A., A LEMAN -M EZA , A. B., B., A. I., B ERTRAM , C., WARKE , Y., R AMAKRISHNAN, C., H ALASCHEK ,C., A NYANWU, K., AVANT, D., A RPINAR , F., AND K OCHUT, K. 2005. Semantic association identificationand knowledge discovery for national security applications. Journal of Database Management 16, 1,
33–53.
S TOCKMEYER , L. J. 1974. The complexity of decision problems in automata theory and logic. Ph.D. thesis,
Massachusetts Institute of Technology.
T O, A. 2009. Unary finite automata vs. arithmetic progressions. Information Processing Letters 109, 17,1010–1014.
T O, A. 2010. Model checking infinite-state systems: Generic and specific approaches. Ph.D. thesis, LFCS,
School of Informatics, University of Edinburgh.
V ERMA , K., S EIDL , H., AND S CHWENTICK , T. 2005. On the complexity of equational Horn clauses. In 20th
International Conference on Automated Deduction (CADE). 337–352.
W EIKUM , G., K ASNECI , G., R AMANATH , M., AND S UCHANEK , F. 2009. Database and information-retrieval
methods for knowledge discovery. Communications of the ACM 52, 4, 56–64.
Received Month Year; revised Month Year; accepted Month YearACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Online Appendix to:
Expressive Languages for Path Queries over Graph-Structured Data
PABLO BARCELÓ, University of Chile
LEONID LIBKIN, University of Edinburgh
ANTHONY W. LIN, Univerity of Oxford
PETER T. WOOD, Birkbeck, University of London
A. PROOF OF PROPOSITION 3.2 FOR BOOLEAN QUERIESThe alphabet is Σ = {a, b, c, d} and the query is^
Q := Ans() ←(xi , πi , xi+1 ), (yi , πi′ , yi+1 ),1≤i≤3c(π1 ), c(π3 ), d(π1′ ), d(π3′ ), a+ (π2 ), b+ (π2′ ), el(π2 , π2′ ).

Given a Σ-labeled graph database G, this query asks whether there exist nodesu, v, u′ , v ′ ∈ V such that:(i). v is reachable from u in G by a path ρ1 labeled in a+ ;(ii). v ′ is reachable from u′ in G by a path ρ2 labeled in b+ ;(iii). the length of ρ1 equals the length of ρ2 ;(iv). there exists a c-labeled edge entering u (resp. v) in G; and(v). there exists a d-labeled edge leaving u′ (resp. v ′ ) in G.
Assume, for the sake of contradiction, that there is CRPQ Q′ that is equivalent to Q;
that is, Q(G) = true ⇔ Q′ (G) = true for
V every Σ-labeledVgraph database G. Further,
suppose that Q′ is of the form Ans() ← 1≤i≤m (xi , πi , yi ), 1≤j≤t Lj (ωj ).
For each n, p > 0, let Gn,p be the following Σ-labeled graph database. First, its set ofnodes V is{e0 , e1 , . . . , en , en+1 , f0 , f1 , . . . , fp , fp+1 }.
Second, there is an edge in G from ej to ej+1 , for each 0 ≤ j ≤ n, and from fj to fj+1 , foreach 0 ≤ j ≤ p. Third, the edges (e0 , e1 ) and (en , en+1 ) are labeled c, the edges (f0 , f1 )and (fp , fp+1 ) are labeled d, each edge (ej , ej+1 ) is labeled a (1 ≤ j ≤ n), and each edge
(fj , fj+1 ) is labeled b (1 ≤ j ≤ p). Clearly, Q(Gn,n ) = true, for each n > 1, and, thus, byassumption, also Q′ (Gn,n ) = true.
We denote by Gen,p and Gfn,p the subgraphs of Gn,p induced by {e0 , e1 , . . . , en+1 } and{f0 , f1 , . . . , fp+1 }, respectively. Recall that m and t are, respectively, the number ofatoms in the relational part of Q and the number of regular languages used in Q. Let
S ⊆ {1, . . . , m}. We denote by Sreg the subset of {1, . . . , t} that contains all those indexes
i such that ωi = πj , for some j ∈ S. It is not hard to see that for each S ⊆ {1, . . . , m}there exist regular languages RS and RS̄ over Σ such that^^^^
Li (ωi ))Li (ωi ) (resp.
Ans() ←
(xj , πj , yj ),(xj , πj , yj ),j∈Si∈Sregj6∈S

i6∈Sreg

evaluates to true over Gen,p (resp. Gfn,p ) iff the label of the path from e0 to en+1 in Gen,p(resp. from f0 to fp+1 in Gfn,p ) belongs to RS (resp. RS̄ ).
c YYYY ACM 0362-5915/YYYY/01-ARTA $10.00
DOI 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

App–2

Pablo Barceló et al.

Let AS and AS̄ be NFAs recognizing RS and RS̄ , for S ⊆ {1, . . . , m}. Let q be
the maximum number of states in an automaton of the form AS or AS̄ , for S ⊆{1, . . . , m}. Choose an arbitrary r > q. Since Q′ (Gr,r ) = true and Gr,r is formedby the disjoint union V
of Ger,r and Gfr,rV, there exists an S r ⊆ {1, . . . , m} such that
Li (ωi ) in Ger,r is true, (2) the evalua(1) the evaluation of j∈S r (xj , πj , yj ), i∈Sregr
V
Vtion of j6∈S r (xj , πj , yj ), i6∈S r Li (ωi ) in Gfr,r is also true, and (3) for every two atoms
reg(xj , πj , yj ) and (xj ′ , πj ′ , yj ′ ) (1 ≤ j, j ′ ≤ m) that share at least one node variable, it is
the case that (xj , πj , yj ) ∈ S r ⇔ (xj ′ , πj ′ , yj ′ ) ∈ S r .
It follows from conditions (1) and (2) that the label of the unique maximal path inGer,r belongs to RS r and the label of the unique maximal path in Gfr,r belongs to RS r .
By using a standard pumping argument there exists r′ > r such that the label of theunique maximal path in Ger′ ,r belongs to RS r and the label of the unique maximal pathin Gfr′ ,r belongs to RS r . From condition (3) it follows that Q′ evaluated on Gr′ ,r is true,
and, thus, that Q(Gr′ ,r ) = true, which is a contradiction.
B. PROOF OF PROPOSITION 6.2.

We only have to prove membership since the query evaluation problem is NP-hardalready for the class of conjunctive queries over directed graphs. Let Σ be a finite
alphabet, G = (V, E) a Σ-labeled graph database, Q an CRPQ over Σ of the form,^^Ans(z̄, χ̄) ←(xi , πi , yi ),Lj (ωj ),
1≤i≤m

1≤j≤t

v̄ a tuple of nodes in G such that |v̄| = |z̄|, and ρ̄ a tuple of paths in G such that |χ̄| = |ρ̄|.
A witness for (v̄, ρ̄) wrt Q and G is a tuple (u1 , . . . , um , u′1 , . . . , u′m , η1 , . . . , ηm ) thatsatisfies the following:(1) Each ui and u′i (i ∈ [1, m]) is a node of G and the pair ((u1 , . . . , um ), (u′1 , . . . , u′m )) of
nodes in Gm is Q-compatible.
(2) Each ηi (i ∈ [1, m]) is a path in G from ui to u′i .
(3) If the variable z is the j-th element of z̄ and z = xi (resp. yi ), for i ∈ [1, m], then ui(resp. u′i ) corresponds to the j-th element of v̄.
(4) If the variable χ is the j-th element of χ̄ and χ = πi , for i ∈ [1, m], then ηi corresponds to the j-th element of ρ̄;(5) For each 1 ≤ i ≤ m, λ(ηi ) satisfies each regular expression Lj (1 ≤ j ≤ t) such thatωj = πi .
It is not hard to see that (v̄, ρ̄) ∈ Q(G) if and only if there is a witness for (v̄, ρ̄) wrt Q
and G.
It is well known that an NFA Aj that accepts exactly the set strings that satisfy Lj
can be constructed in polynomial time from Lj , for each 1 ≤ j ≤ m. We denote by Qj
the set of states of Aj . In particular, Qj is of polynomial size in Lj .
We first prove that if there is a witness for (v̄, ρ̄) wrt Q and G then there is a witness
in which each path is of length at most |V | × max {|Qj | | j ∈ [1, t]} × Σ + 3 (by the lengthof the path we mean the number of nodes from G in the path).
Let (u1 , . . . , um , u′1 , . . . , u′m , η1 , . . . , ηm ) be a witness for (v̄, ρ̄) wrt Q and G, and assume for the for 1 ≤ i ≤ m the path ηi = v1 a1 v2 a2 v3 · · · vℓi aℓi vℓi +1 is of lengthℓi + 1 > |V | × max {|Qi | | i ∈ [1, m]} × Σ + 3. (Notice that v1 = ui and vℓi+1 = u′i ). Let
θi : {0, 1, . . . , ℓi } → Qi be an accepting run of Ai over λ(ηi ) (we assume that θi (0)is the initial state of Ai ). Since ℓi + 1 > |V | × max {|Qi | | i ∈ [1, m]} × Σ + 3 there
are two integers 1 ≤ j < j ′ < ℓi such that θi (j − 1) = θi (j ′ − 1), vj = vj ′ andaj = aj ′ . Thus, ηi′ = v1 a1 v1 · · · vj−1 aj−1 vj aj ′ vj ′ +1 · · · vℓi aℓi vℓi +1 is also a path from ui
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Expressive Languages for Path Queries over Graph-Structured Data

App–3

to u′i that satisfies Li , and the length of ηi′ is strictly less than the length of ηi . Thus,(u1 , . . . , um , u′1 , . . . , u′m , η1 , . . . , ηi′ , ηi+1 , . . . , ηm ) is also a witness for (v̄, ρ̄) wrt Q and G.
By iteratively continuing with this process we will end up with a witness for (v̄, ρ̄) wrt
Q and G in which each path is of length at most |V | × max {|Qi | | i ∈ [1, m]} × Σ + 3.
It is now easy to define an algorithm that works in nondeterministic polynomial timeand checks whether (v̄, ρ̄) ∈ Q(G). The algorithm first guesses a tuple of the form
(u1 , . . . , um , u′1 , . . . , u′m , η1 , . . . , ηm ),such that each ui and u′i (i ∈ [1, m]) is a node in V and each ηi (i ∈ [1, m]) is a path fromui to u′i of length at most |V | × max {|Qi | | i ∈ [1, m]} × Σ + 3. Then the algorithm checks
whether (u1 , . . . , um , u′1 , . . . , u′m , η1 , . . . , ηm ) is a witness for (v̄, ρ̄) wrt Q and G. This caneasily be done in polynomial time.
C. PROOF OF PROPOSITION 8.7

The proof follows the main ideas used in the proofs of Theorems 6.7 and 8.5, but instead
we use a representation of Parikh images by Presburger formulae more complex thanunions of arithmetic progressions. Let Γ be an arbitrary k-letter alphabet, and L a regular language over Γ. Then the Parikh image of L, i.e., par(L) = {par(s) | s ∈ L} ⊆ Nk
is known to be a semi-linear set and thus definable in Presburger arithmetic. According to [Verma et al. 2005], this image is definable by an existential Presburger formulaL(x1 , . . . , xn ) which can be computed in polynomial time from an NFA defining L.
ψparSuppose we have an m-ary regular relation R over an alphabet Σ. Applying theprevious observation to the alphabet (Σ⊥ )m with N = (|Σ| + 1)m symbols, we get an
R
existential Presburger formula ψpar(x1 , . . . , xN ) for the Parikh image. From this formula we easily obtain another existential formula ψR (x11 , . . . , xnk ), where k = |Σ|,which is satisfied on a tuple (aij ) iff for some (s1 , . . . , sm ) ∈ R, it is the case that aij isthe number of occurrences of the jth letter of Σ in si . Indeed, ψR starts with a blockof existential quantifiers ∃x1 , . . . , ∃xN followed by a conjunction of linear constraints
stating that xij is the sum of xl ’s corresponding to those symbols in (Σ⊥ )m that containthe jth letter of Σ in the ith position. Note that for each fixed m, the formula ψR isconstructed in polynomial time.
We next proceed as in the proof of Theorem 6.7. For a given ECRPQ in which all relations R were replaced with Rpar , we guess a set of nodes witnessing the query as wellas an ordered partition for the set of paths and assume that witnessing paths lengthconform to it. Then, again as in that proof, we guess nodes on every path that mark thelengths of smaller paths in the set, and split each variable xij into several according
to those points. Again, taking as an example an ordered partition {1, 2} < {3} < {4}for paths π1 , π2 , π3 , π4 , for each x4j we introduce variables x′4j , x′′4j , and x′′′
4j to indicate
the numbers of occurrences of the jth letter in the portion of the path π4 consisting of
the first |π1 | positions, then positions from |π1 | + 1 to |π3 |, and finally the remaining
positions. We modify ψR accordingly by quantifying over these new variables and thenstating that x4j = x′4j + x′′4j + x′′′
4j , and likewise for all other variables. Note that theresulting modification is still an existential Presburger formula, which is polynomial
in size if the arities of relations are fixed.
As before, introducing these intermediate points lets us compare path lengths forequality only, under the assumption that they length-conform to a given ordered partition. We thus reduce the problem to the following. Given nodes a1 , . . . , an in a graphdatabase, an existential Presburger ψ formula over variables xijp , where i, j ≤ n, andp ≤ |Σ|, and a family S of subsets of {1, . . . , n} × {1, . . . , n}, do there exist paths πij between ai and aj for i, j ≤ n so that ψ holds when each xijp is interpreted as the numberof occurrences of the pth letter in πij , and for every (i, j) and (i′ , j ′ ) in the same set of
ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

App–4

Pablo Barceló et al.

S, the length of the paths between ai and aj and between ai′ and aj ′ are the same? Wemust now show that this problem is solvable in NP.
To do so, for every i, j we look at the graph as an automaton (G, ai , aj ) and use
the algorithm of [Verma et al. 2005] to produce an existential Presburger formulaψij (xij1 , . . . , xijk ) for the Parikh image of paths between ai and aj . We then check if
the formula^n
ψij (xij1 , . . . , xijk ) ∧ ψ (xijp )ijp ∧∃(xijp )i,j≤n, p≤k
i,j=1

^

^

S∈S (i,j),(i′ ,j ′ )∈SXp≤kxijp =

Xp≤kx

i′ j ′ p(8)is satisfiable. This is an existential formula, and by the above, it is constructible inpolynomial time for fixed arities of regular relations. Thus one can check satisfiability
in NP. Again, as in the proof of Theorem 6.7, all the guesses can be combined, and thewhole algorithm runs in NP.
For data complexity, note that the number of guessed tuples of nodes and partitions
is fixed if the query is fixed, and so we need to check a fixed number of formulae of theform (8). Note that in that formula, the number n comes from the query, and k is thesize of the alphabet, so the number of variables is fixed. Then the formula is reduced
to solving integer linear programs in fixed dimension [Lenstra 1983], which therefore
implies the P TIME bound on data complexity.
The proof for queries of the form Q◦par follows closely the proof of Theorem 8.5. We
start by computing in polynomial time automata defining every projection of every regular relation R, followed by applying the algorithm of [Verma et al. 2005] to computeexistential Presburger formulae for Parikh images of such automata, and then essentially follow the proof of Theorem 8.5, in which the condition Aℓ̄ ≥ b can be replacedby an existential Presburger formula without affecting the complexity. This completes
the proof of the proposition.

ACM Transactions on Database Systems, Vol. V, No. N, Article A, Publication date: January YYYY.