Finding Regular Simple Paths in Graph Databases.
We consider the following problem: given a labelled directed graph $G$  and a regular expression $R$, find all pairs of nodes connected by a  simple path such that the concatenation of the labels along the path  satisfies $R$. The problem is motivated by the observation that many  recursive queries in relational databases can be expressed in this  form, and by the implementation of a query language, ${\bf G}^+$, based on  this observation.  We show that the problem is in general intractable,  but present an algorithm than runs in polynomial time in the size of  the graph when the regular expression and the graph are free of   conflicts.  We also present a class of languages whose expressions  can always be evaluated in time polynomial in the size of both the  graph and the expression, and characterize syntactically the  expressions for such languages.
Introduction
. Much of the success of the relational model of data can be attributed
to its simplicity, which makes it both amenable to mathematical analysis and easy for users
to comprehend. In this latter respect, the availability of non-procedural query languages
has been a great asset. However, the fact that queries which are especially useful in new
application domains are not expressible in traditional query languages has led to proposals
for more powerful query languages, such as the logic-based language Datalog [23] and our
query language G
The original proposal for the relational model included two query languages of equivalent
expressive power: the relational calculus and the relational algebra [7]. These languages
have been used as the yardstick bywhich other query languages are classified; a query language
is said to be relationally complete if it has (at least) the expressive power of the relational
calculus. However, this notion of completeness has been questioned since it was shown that
certain reasonable queries, such as finding the transitive closure of a binary relation, cannot
be expressed in the calculus [3, 4]. This particular limitation is overcome in the languages
and Datalog through their ability to express recursive queries.
The design of G + is based on the observation that many of the recursive queries that
arise in practice-and in the literature-amount to graph traversals (for example, [1, 12, 19]).
In G + , we view the database as a directed, labelled graph, and pose queries which are
graph patterns; the answer to a query is the set of subgraphs of the database that match the
given pattern. Useful applications for such a language can be found in systems representing
transportation networks, communication networks, hypertext documents, and so on. In our
prototype implementation, queries are drawn on a workstation screen and the database and
query results are also displayed pictorially.
Example 1. Let G be a graph describing a hypertext document: nodes are chunks of text
and edges are links (cross-references). Readers read the document by following links. In this
context, one might be interested in a query such as: Is there a way to get from Section 3.1
to Section 5.2 and then to the Conclusion, without reading any node more than once? The
corresponding G + query is shown in Figure 1. The left-hand box in the figure contains the
pattern graph, while the right-hand box contains the summary graph which specifies how the
A preliminary version of sections of this paper appeared in Proceedings of the 15th International Conference
on Very Large Data Bases (Amsterdam, The Netherlands, August 22-25, 1989), pages 185-193.
y Computer Systems Research Institute, University of Toronto, Toronto, Ont. M5S 1A4, Canada.
z Department of Computer Science, University of Cape Town, Rondebosch 7700, South Africa
ae-
ae-
ae-
Conc
link
ae-
ae-
Conc
FIG. 1. Query to test for the existence of a simple path in a hypertext document.
ae-
ae-
AC
ae-
ae-
FIG. 2. Query to find pairs of cities connected by some Air Canada flight.
output is to be presented to the user. The nodes in this case are labelled with constants to be
matched with those in the database. The edges of a pattern graph can be labelled with regular
expressions; in this case the desired expression is link representing a nonzero sequence
of links. This regular expression is used to match the edge labels along simple paths in G,
thereby satisfying our original request.
Example 2. Let G be a graph representing airline flights: the nodes of G denote cities,
and an edge labelled a from city b to city c means that there is a flight from b to c with airline
a. Assume that we want to find all pairs of cities that are connected by a sequence of flights
such that (a) at least one flight is with Air Canada (AC), and (b) no city is visited more than
once. This query can be expressed by the graph pattern of Figure 2. The pattern graph in
this example comprises only two nodes, this time labelled with variables, while the edge is
labelled with the regular expression   AC   (where the underscore matches any edge label
in G, and AC is regarded as a single symbol). Once again, the fact that only simple paths are
matched during query evaluation ensures that the desired answer is computed.
Although queries in G + can be a lot more general than exemplified in the above two
examples, the special case suggested by Example 2 is challenging enough from an algorithmic
point of view if we want to process queries efficiently. The problem addressed in this paper is:
given a regular expression R and a graph G, find all pairs of nodes in G which are connected
by a simple path p, where the concatenation of edge labels comprising p is in the language
denoted by R.
When trying to find an efficient solution for this problem to incorporate in our implementation
of G + , we were somewhat surprised to discover that the queries of Examples 1
and 2 are in fact both NP-complete. Using results in [11, 17], we show in x2 that for certain
fixed regular expressions (such as R in Example 2), the problem of deciding whether a pair
of nodes is in the answer of a query is NP-complete, making the general problem NP-hard.
We first attacked this problem by determining what it is in the language of R that makes the
problem hard. In x3, we present a class of languages for which query evaluation is solvable
in time polynomial in both the length of the regular expression and the size of the graph.
We characterize these languages syntactically in terms of the regular expressions that denote
them and the finite automata that recognize them. This characterization assumes we have no
knowledge concerning the structure of the graph being queried. In x4, we consider extensions
where we are given a constraint which the cycles of the input graph are known to satisfy. This
knowledge allows us to characterize potentially larger classes of queries which can be solved
in polynomial time.
We then designed a general algorithm, presented in x5, which is correct for arbitrary
graphs and queries, and is guaranteed to run in polynomial time in the size of the graph if
the regular expression and graph are free of "conflicts", in a sense to be defined precisely
in that section. As special cases, any query is free of conflicts with any acyclic database
graph and any restricted expression query is free of conflicts with any arbitrary graph. Since
we cannot restrict our prototype to work only on conflict-free queries and graphs, and it
is expensive to test for conflict-freedom beforehand, it is quite convenient to have a single
algorithm that works in all cases, and we have in fact incorporated the algorithm of x5 into
our implementation.
2. Intractability Results. In this section, we prove some negative results regarding the
complexity of finding certain types of simple paths in a particular class of directed graphs.
We begin by defining the graph structures as well as the class of queries over these structures
in which we are interested.
DEFINITION 1. A database graph (db-graph, for short) is a directed,
labelled graph, where N is a set of nodes, E is a set of edges, and is an incidence function
mapping E to N \Theta N . Note that multiple edges between a pair of nodes are permitted in
db-graphs. The labels of G are drawn from the finite set of symbols S, called the alphabet,
and - is an edge labelling function mapping E to S.
DEFINITION 2. Let S be a finite alphabet disjoint from fffl; ; (; )g. A regular expression
R over S is defined as follows.
1. The empty string ffl, the empty set ;, and each a 2 S are regular expressions.
2. If A and B are regular expressions, then are regular
expressions.
3. Nothing else is a regular expression.
The expression (A+B) is called the alternationof A and B, (AB) is called the concatenation
of A and B, and (A)   is called the closure of A. We use the underscore ( ) to denote the
alternation of all elements of S. Also, A + denotes AA   , the positive closure of A.
The language L(R) denoted by R is defined as follows.
1. ffflg.
2.
3.
4. L(B)g.
5. L(B)g.
6.
Regular expressions R 1 and R 2 are equivalent, written R 1
length of regular expression R, denoted jRj, is the number of symbols appearing in the string
R.
DEFINITION 3. Let G = (N; E; /; S; -) be a db-graph and
be a path (not necessarily a simple
path) in G. We call the string -(e 1 the path label of p, denoted by -(p) 2 S   .
Let R be a regular expression over S. We say that the path p satisfies R if -(p) 2 L(R). The
query QR on db-graph G is defined as the set of pairs (x; y) such that there is a simple path
from x to y in G which satisfies R. If (x; y) 2 QR (G), then (x; y) satisfies QR .
A naive method for evaluating a query QR on a db-graph G is to traverse every simple
path satisfying R in G exactly once. The penalty for this is that such an algorithm takes
exponential time when G has an exponential number of simple paths. Nevertheless, we
will see below that in general we cannot expect an algorithm to perform much better, since
we prove that, for particular regular expressions, the problem of deciding whether a pair
of nodes is in the answer of a query is NP-complete. On the other hand, refinements can
lead to guaranteed polynomial time evaluation under conditions studied in the following two
sections.
Consider the following decision problem.
REGULAR SIMPLE PATH
Instance: Db-graph regular expression R over S.
Question: Does G contain a directed simple path from x to y such that p
satisfies R, that is, -(e
This is equivalent to asking "Is (x; y) 2 QR (G)?". When the instance comprises only the
db-graph, we refer to the problem as FIXED REGULAR PATH(R), that is, for FIXED REGULAR
PATH(R) we measure the complexity only in terms of the size of the db-graph. We first prove
below that, for certain regular expressions R, FIXED REGULAR PATH(R) is NP-complete. In
doing so, we will refer to the following two decision problems.
Instance: Directed graph E), and nodes x; y 2 N .
Question: Is there a directed simple path of even length (that is, with an even number of
edges) from x to y?
Instance: Directed graph E), and two pairs of distinct nodes (w; x); (y; z) 2 N \Theta N .
Question: Is there a pair of disjoint directed simple paths in G, one from w to x and the other
from y to z?
The following theorem uses the above two decision problems to prove the NP-completeness
of FIXED REGULAR PATH(R) for two particular regular expressions.
THEOREM 1. Let 0 and 1 be distinct symbols in S. FIXED REGULAR PATH(R), in which R
is either (1) (00)   , or (2) 0   10   , is NP-complete.
Proof. (1) In [17], EVEN PATH is shown to be NP-complete. We can reduce EVEN PATH
to FIXED REGULAR PATH(R), where Given an instance G; x; y of
EVEN PATH, construct a db-graph H isomorphic to G, except that every edge in H is labelled
with 0. There is an even simple path from x to y in G if and only if there is a simple path
from x to y in H which satisfies R. It is easy to see that FIXED REGULAR PATH(R) is in NP;
we conclude that FIXED REGULAR PATH(R), where
(2) The fact that DISJOINT PATHS is NP-complete follows immediately from results in
[11]. We reduce DISJOINT PATHS to FIXED REGULAR PATH(R), where Given
an instance G; w; x; y; z of DISJOINT PATHS, construct a db-graph H isomorphic to G, except
that every edge of H is labelled with 0. Now add a new edge (x; y) labelled 1 to H. There is
a simple path from w to z satisfying R in H if and only if there are disjoint simple paths from
w to x and from y to z in G. We conclude that FIXED REGULAR PATH(R), where
is also NP-complete.
COROLLARY 1. REGULAR SIMPLE PATH is NP-complete.
Proof. NP-hardness follows from Theorem 1. To show that REGULAR SIMPLE PATH is
in NP, we observe that, for an arbitrary regular expression R, given a simple path from x to y
in G with path label w, we can check in polynomial time in the lengths of R and w whether
or not w is in L(R) [2].
It is interesting to note that if G is undirected, then both EVEN PATH and DISJOINT PATHS
can be solved in polynomial time. EVEN PATH can be solved in polynomial time by using
matching techniques [17], while a polynomial time algorithm for DISJOINT PATHS is given
in [20].
Each of the two NP-completeness results of Theorem 1 can be generalized. We first
generalize from the regular expression (00)   to expressions of the form w   , for any w 2 S
such that jwj - 2. For this we use the following NP-complete problem from [17], which was
used there to show the NP-completeness of EVEN PATH.
PATH VIA A NODE
Instance: Directed graph E), and nodes x;
Question: Is there a directed simple path from x to y via m?
THEOREM 2. FIXED REGULAR PATH(R), in which R = w   , for any w 2 S   such that
Proof. Once again, membership in NP is easy to demonstrate. We reduce PATH VIA A
NODE to FIXED REGULAR PATH(R) using a variation of the construction from [17]. Given
an instance G; of PATH VIA A NODE, construct a db-graph
(1)
f
(2)
f
f
The proof now divides into two parts, depending on whether w is of even or odd length.
Rather than introducing additional nodes into the above structure, which we believe would
obscure the proof, below we allow edges to be labelled with strings of symbols. The length
of a path is the length of its concatenated edge labels.
Assume that 1. There are two copies of
each edge of types 1 and labelled with w 1 , the other with w 2 . Edges of
type 3 are labelled with w 2 , while edges of type 4 are labelled with w 1 . We claim that there
is a simple path from x to y through m in G if and only if there is a simple path from (x; 1)
to (y; 2) satisfying R in H.
If there is a path p from x to y through m in G, then let p 1 be the subpath of p from x
to m, and p 2 be the subpath of p from m to y. Let u be the predecessor of m on p 1 and v
be the successor of m on p 2 . Then in H we can traverse a simple path from (x; 1) to (u; 2)
which satisfies (w 1 followed by the edges labelled w 2 and w 1 from (u; 2) to m and
from m to (v; 1), respectively, followed by a simple path from (v; 1) to (y; 2) which satisfies
(w . The overall path thus satisfies (w 1 w 2 )   and is guaranteed to be simple.
Now assume there is a simple path p from (x; 1) to (y; 2) in H which satisfies R. All
strings in L(R) are of length mn, where m is even. Any path from (x; 1) to (y; 2) which
does not pass through m must be of length kn, where k is odd. We conclude that p must pass
through m in H; hence, there is a simple path from x to y via m in G.
We now consider the case in which
One copy of each edge of type 1 in H is labelled with a 0 ,
the other with a 2n . One copy of each edge of type 2 is labelled with w 1 , the other with w 2 .
Type 3 edges are labelled with w 1 , while type 4 edges are labelled with w 2 .
It is easy to see that if there is a simple path from x to y via m in G, there must be a simple
path satisfying R in H . For the other direction, it suffices to note that simple paths in H from
(x; 1) to (y; 2) which do not pass through m have length m(2n those
which do pass through m have length k(2n are also the lengths of strings
in L(R). These two can never be equal for n - 0. We conclude that if there is a simple path
from (x; 1) to (y; 2) in H satisfying R, there must be a simple path from x to y via m in G.
We now generalize the NP-completeness result for FIXED REGULAR PATH(R) where
. If S ' S, let S also denote the alternation of its elements.
THEOREM 3. Let R be a regular expression of the form S   wT   , where S and T are
subsets of S and w In addition, assume that either (1) some a in w appears in neither
nor T , or (2) there are symbols b 2 S and c 2 T such that neither appears in w. Then
FIXED REGULAR PATH(R) is NP-complete.
Proof. Once again, FIXED REGULAR PATH(R) is obviously in NP. We use essentially the
same reduction from DISJOINT PATHS to FIXED REGULAR PATH(R) as in Theorem 1 for this
more general case.
Given an instance G; w; x; y; z of DISJOINT PATHS, construct a db-graph H isomorphic
to G, except that two copies of each edge of H are made, one labelled with b 2 S, and one
labelled with c 2 T . For case (2), b and c are those symbols mentioned in the statement of the
theorem; for case (1), we choose b 6= a and c 6= a. Assume that an . Now add
along with the path
where e i is labelled with a
If there are disjoint simple paths from w to x and from y to z in G, it is easy to see that
there must be a simple path from w to z satisfying R in H . Assume now that there is a simple
path p from w to z satisfying R in H . Then p must be of the form p 1 pw p 2 , since, in both cases
(1) and (2), pw contains an edge label which appears nowhere else in H and has to appear on
any path in H satisfying R. We conclude that there must be disjoint simple paths from w to
x and from y to z in H, and hence in G.
Theorems 2 and 3 are rather negative results, since they imply that queries might require
time which is exponential in the size of the db-graph, not only the regular expression, for their
evaluation. Thus, for regular expressions such as those in Theorems 2 and 3, we certainly
would not expect an evaluation algorithm to run in polynomial time. One such example is
the "Air Canada" query used in Example 2 (as long as the alphabet S contains at least two
symbols). These results, however, are not a function of the particular regular expression but
rather of the nature of the language denoted by the regular expression. A class of languages
for which REGULAR SIMPLE PATH is in P is the subject of the next section.
3. Restricted Regular Expressions. In this section, we characterize a class of queries
about regular simple paths which can be evaluated in polynomial time. We first introduce
some terminology and definitions.
DEFINITION 4. A nondeterministic finite automaton (NDFA)M is a 5-tuple (S;
where S is a finite set of states, S is the input alphabet, ffi is the state transition function which
maps S \Theta (S [ ffflg) to the set of subsets of S, s 0 2 S is the initial state, and F ' S is the set
of final states. The extended transition function ffi   is defined as follows. For s; t 2 S, a 2 S,
and w 2 S
The NDFA M accepts w ;. The language L(M ) accepted by M is
the set of all strings accepted by M . A deterministic finite automaton (DFA) is an NDFA in
which the state transition function is a mapping from S \Theta S to S.
DEFINITION 5. Let be an NDFA. The transition graph associated
with M is a directed, labelled graph
a 2 S, then there is an edge e in EM with /M confusing
representations, we will sometimes say there is a transition from state s to state t in M (or
t is a successor of S) if t 2 ffi (s; a), and there is a path from s to t if t 2 ffi   (s; w) for some
ae-
ff \Phi
s 0-ae-
ff \Phi
s 1-ae-
ff \Phi
s 2FIG. 3. Transition graph T of a DFA.
definitions apply for a DFA.
DEFINITION 6. Given an NDFA each pair of states s; t 2 S,
we define the language from s to t, denoted by L st , as the set of strings that take M from
state s to state t. Then, for state s and set of states T , we can define the language from s to
denoted by L sT , as S
st . In particular, for a state s 2 S, the suffix language of s,
denoted by L sF (or [s], for short), is the set of strings that take M from s to some final state.
Clearly, definitions apply for a DFA.
Given a regular expression R over S, an ffl-free
L(R) can be constructed in polynomialtime [2]. From now on, we will assume that all NDFAs
are ffl-free.
Example 3. Figure 3 shows the transition graph T of a DFA M . State s 0 is the initial
state of M , while all states are final (denoted by a double circle). (We do not show (reject)
states which are not on some path from the initial state to a final state.) L(M ) is denoted by
the regular expression 0   1   0   . The suffix language of state s 1 is [s 1
regular expressions. In the subsequent analysis, it will be useful to refer
to an NDFA which accepts the language L(R 1 " R 2 ). The construction of such an NDFA is
defined as follows.
DEFINITION 7. Let M
The NDFA for
We call the transition graph of
I the intersection graph of M 1 and M 2 .
We saw in the previous section that, for certain regular expressions R, it is very unlikely
that we will find an algorithm for evaluating QR on an arbitrary graph G which will always
run in time polynomial in the size of G. One such regular expression is 0   10   . However,
it turns out that if the regular expression specified instead, then QR is
evaluable in polynomial time on any db-graph G. The reason is that if there is an arbitrary
path from node x to node y in G which satisfies R, then there is a simple path from x to y
satisfying R. In such a case, we need not restrict ourselves to looking only for simple paths
in G, but can instead look for any path satisfying R. We define the corresponding decision
problem below.
REGULAR PATH
Instance: Db-graph regular expression R over S.
Question: Does G contain a directed path (not necessarily simple)
to y such that p satisfies R, that is, -(e
LEMMA 1. REGULAR PATH can be decided in polynomial time.
ae-
x
ae-
ff \Phi
z
a
y
ae-
FIG. 4. A graph containing a non-simple path.
Proof. Given db-graph G along with nodes x and y in G, we can view G as an
NDFA with initial state x and final state y. Construct the intersection graph I of G and
an NDFA accepting L(R). There is a path from x to y satisfying R if
and only if there is a path in I from (x; s 0 ) to (y; s f ), for some s f 2 F . All this can be done
in polynomial time [14].
In [22], Tarjan provides a polynomial-time algorithm for constructing a regular expression
which represents the set of all paths between two nodes of a given graph. As an alternative to
the above procedure, one could decide in polynomial time whether there was a path between x
and y in G satisfying R by first using Tarjan's algorithm to construct a regular expression R xy
representing all paths between x and y in G, and then determining whether the intersection
of L(R) and L(R xy ) was nonempty using NDFAs. The results of the previous section show
that it is unlikely that a polynomial-time analogue of Tarjan's algorithm exists for describing
the set of all simple paths between two nodes.
DEFINITION 8. Let G be a db-graph, or NDFA, and I the
intersection graph of G and M . We call a node (x; s 0 ) in I an initial node, and a node (y; s f ),
final node.
We are interested in conditions under which REGULAR SIMPLE PATH (which is appropriate
because of our semantics) can be reduced to REGULAR PATH. The following lemma
states one such condition.
LEMMA 2. REGULAR SIMPLE PATH can be decided in polynomial time on acyclic db-
graphs.
Proof. Follows immediately from Lemma 1 and the fact that every path in an acyclic
graph is simple.
Suppose that we want to characterize a class of regular expressions for which we can
guarantee that REGULAR SIMPLE PATH is solvable in polynomial time. If we assume that we
know nothing about the structure of the db-graphs, we have to ensure that, for such a regular
expression R, whenever string w is in L(R), every string obtainable from w by removing one
or more symbols must also be in L(R). Otherwise, if xay is in L(R) but xy is not in
L(R) (where a 2 S and x; y 2 S   ), we can construct a graph G comprising a single simple
path from u to v and passing through z, in which there is a loop at z labelled a, the path from
u to z is labelled x, and the path from z to v is labelled y (see Figure 4). There is a non-simple
path from u to v in G which satisfies R but no simple path from u to v satisfying R.
DEFINITION 9. An abbreviation of a string w is any string which can be obtained from
w by removing one or more symbols of w [6].
So we are looking for a class of regular expressions which denote languages that are
closed under abbreviation. Now consider the following definition for the class of restricted
regular expressions.
DEFINITION 10. For a 2 S, denote the regular expression (a (as is done in
the grep utility of Unix 1 , for example). Given a regular expression R, let R 0 be the regular
expression obtained by replacing some occurrence of a symbol a 2 S in R by (a?). R is
restricted if and only if R j R 0 , for any R 0 obtained from R as defined above.
Note that the above definition of restricted regular expressions is semantic rather than
syntactic. This has two significant consequences: on the one hand, we are able to prove an
equivalence theorem below (Theorem relating restricted regular expressions to languages
and automata; on the other, the recognition problem for restricted regular expressions becomes
difficult (Corollary 3).
Example 4. The regular expression 0   1   0   is restricted: it is equivalent to (0?)   (1?)   (0?)   .
Recall, from Theorem 1, that FIXED REGULAR PATH(R) is NP-complete for
is not restricted, but R is restricted, since R 0 can be written as 0   (1
which is equivalent to (0?)   (1?)(0?)   .
DEFINITION 11. A DFA exhibits the Suffix Language Containment
Property (the Containment Property, for short) if, for each pair s; t 2 S such that s and t are
on a path from s 0 to some final state and t is a successor of s, [s] ' [t] (that is, L sF ' L tF ).
The following result, although not used elsewhere, provides some interesting restrictions
on the structure of DFAs that exhibit the Containment Property.
PROPOSITION 1. Let exhibits the Containment
Property, then
1. every state in M , which is on a path from s 0 to a state in F , is final,
2. the minimum DFA for M exhibits the Containment Property, and
3. if M is minimum, then every cycle in M is a loop.
Proof. (1) Every final state in M accepts ffl. By the transitivity of ""', every state which
is on a path from s 0 to a state in F must also accept ffl, and hence must be final.
be the minimum DFA equivalent to M . Each state in M 0
represents a set of equivalent states in M . Assume that s 2 S 0 represents fs
There
is a transition only if, for each s i there is a transition
In M , [s i
equivalent to M ,
that [s] ' [t].
(3) Consider a cycle in M which is not a loop, and let s and t be two states on the
cycle. Since [u] ' [v] for every pair of consecutive states on the cycle, we conclude from the
transitivity of ""' that [s] ' [t] and that [t] ' [s]. But then s j t, and so M is not minimum,
a contradiction.
Example 5. Consider the regular expression and the DFA M accepting
whose transition graph T is given in Figure 3. We can verify that M exhibits the
Containment Property by noting that [s 2 ] is denoted by 0   ,
Obviously, It is easy to check that [s 1
Note also that, by Proposition 1, each state is final and, since M is minimal, every
cycle in M is a loop. The fact that M exhibits the Containment Property and R is restricted
is no coincidence, as we demonstrate below.
THEOREM 4. Let R be a regular expression over S, and
accepting L(R). The following three statements are equivalent:
1. R is a restricted regular expression,
2. L(R) is closed under abbreviations, and
3. M exhibits the Containment Property.
1 Unix is a trademark of AT&T.
Proof. In our proof, we will use the NDFA E) constructed from
regular expression R (such that L(MR detailed in [2], and in which ffl-transitions
are usually present. There is a one-to-one correspondence between non-ffl-transitions in MR
and occurrences of symbols in R, so that it makes sense to refer to the transition in MR
corresponding to an occurrence of symbol a in R, and vice versa. Furthermore, replacing an
occurrence of a in R by (a?) is equivalent to including an ffl-transition from the source state
to the target state of the transition in MR corresponding to the occurrence of a.
Assume that R is restricted but that L(R) is not closed under abbreviations.
Then there is a symbol a 2 S and strings x; y 2 S   such that xay 2 L(R) but xy 62 L(R).
Now consider MR . Let T that is, the set of states MR can be in after reading
x. Since L(MR can y be in [r]. On the other hand,
xay 2 L(MR ), so there is a state p 2 T 0 such that q 2 -(p; a) and y 2 [q]. Since R is
restricted, adding an ffl-transition from p to q leaves L(MR ) unchanged. But if we do so, then
longer equal to L(R), which is a contradiction. We
conclude that L(R) is closed under abbreviations.
We prove the contrapositive. Assume that [s] 6' [t] for some pair s; t of
reachable states in M such that ffi (s; a) = t, for some a 2 S. That is, there is a string y 2 S
for which y 2 [t] but y 62 [s]. Let x 2 S   be a string for which ffi   It follows
that xay 2 L(M ), but that xy 62 L(M ). Since L(M we conclude that L(R) is not
closed under abbreviations.
Once again we prove the contrapositive. Assume that R is not restricted. Then
there is an a-transition in MR from s to t for which adding an ffl-transition from s to t alters
be a string for which s 2 -   That is, there is a string y 2 [t] such
that y 62 [r] for any r 2 -   Now consider the DFA M . Assume
that there must be a state q in
M such that ffi (p; a) = q and y 2 [q]. However, y 62 [p], for otherwise xy 2 L(M ) which
would mean that L(M does not exhibit the Containment
Property.
THEOREM 5. REGULAR SIMPLE PATH can be decided in polynomial time for restricted
regular expressions.
Proof. Let the db-graph G and the regular expression R, where R is restricted, constitute
an instance of REGULAR SIMPLE PATH. By Lemma 1, it is sufficient to show that whenever
there is a path from x to y in G which satisfies R, there is a simple path from x to y satisfying
R. Assume that non-simple path from
in G. Since p is non-simple, Assume that i ! j, that
L(R). The path label -(p 0 ) is an abbreviation of -(p). By
Theorem 4, L(R) is closed under abbreviations; hence, -(p 0
Removing all such cycles from p will leave a simple path from x to y which satisfies R.
Thus the class of restricted regular expressions is one for which query evaluation can
be performed efficiently. We now show that, even though the classes of restricted regular
expressions and regular languages closed under abbreviations are subclasses of their regular
counterparts, at least they are closed under the regular operators.
THEOREM 6. Let S be an alphabet. The class of regular languages over S which is closed
under abbreviations is also closed under alternation, concatenation and closure.
Proof. Let L 1 and L 2 be regular languages closed under abbreviations. It is immediate that
closed under abbreviations too. Now let
such that w
2 be an abbreviation of w. Clearly, string
i is an abbreviation of w and since L 1 and L 2 are closed under abbreviations,
Algorithm S: Compute the suffix language containment relation for a DFA.
INPUT:
OUTPUT:
For each pair s; t 2 S, whether [s] ' [t] or not.
1. for s do mark (s; t) od
2. for each ordered pair of distinct states (s; do
3. if for some a 2 S (ffi(s; a); ffi (t; a)) is marked then
4. mark (s; t)
5. recursively mark all unmarked pairs on the list for (s; t) and
on the lists of other pairs that are marked at this step
else /* no pair (ffi(s; a); ffi (t; a)) is marked */
6. for all a 2 S do
7. put (s; t) on the list for (ffi(s; a);
od
od
FIG. 5. Computing the suffix language containment relation for DFA
is in L, allowing us to conclude that L is closed
under abbreviations.
Let L be a regular language closed under abbreviations. Since ffl 2 L and regular
languages closed under abbreviations are also closed under concatenation, L   must be closed
under abbreviations.
COROLLARY 2. The class of restricted regular expressions over S is closed under
alternation, concatenation and closure.
Example 6. One of the simplest restricted regular expressions is 0   . Since the class of
restricted regular expressions is closed under alternation, concatenation and closure, 0
and 0   1   0   (which we have already seen) are restricted. On the other hand, restricted
expressions can also sometimes be built from expressions which are not restricted; examples
include (which we have already seen), (00)
Given a query QR , we would like to test whether R is restricted in order to know that it
is safe to use a polynomial time evaluation algorithm. By adapting an algorithm to minimize
the number of states of a DFA [13], we can compute the suffix language containment relation
for all pairs of states in a DFA M . The suffix language containment relation will be used in
subsequent sections; it also provides an obvious method for testing whether or not a regular
expression R is restricted (using Theorem 4). The algorithm for computing the suffix language
containment relation, Algorithm S, is shown in Figure 5. Lines 3 to 7 of Algorithm S are taken
directly from the algorithm in [13]. That algorithm marks pairs of inequivalent states, so it
considers unordered pairs of states. Lines 1 and 2 of our algorithm are altered appropriately
in order to consider ordered pairs of states. If (s; t) is marked by Algorithm S, then [s] 6' [t].
If M has n states, then Algorithm S runs in O(n 2 (assuming a constant alphabet)
[13]. (An alternative, almost linear-time algorithm is given in [2].) Since the construction
of a DFA M accepting L(R) may take exponential time (in the size of R), using Algorithm
S to test whether a regular expression is restricted is not efficient. However, it is important
to stress that we are trying to avoid the possibility of spending exponential time in the size
of the db-graph in answering a query. Also, it turns out that determining whether or not R is
restricted is a hard problem. Consider the following result.
PROPOSITION 2 ([21]). Determining whether a regular expression over alphabet f0g does
not denote 0   is NP-complete.
We will use this result to show that the problem of deciding whether a regular expression
over alphabet S is not restricted is NP-hard. To do so, we first prove the following.
THEOREM 7. Let R be a starred regular expression over alphabet f0g. Deciding whether
R is not restricted is NP-complete.
Proof. We first show that the problem is in NP. If R is not restricted, then L(R) is not
closed under abbreviations (Theorem 4). Thus, there is a string in 0   that is not in L(R). If
by considering a DFA accepting L(R), it can be seen that there must be an
jRj such that 0 n 62 L(R). A nondeterministic polynomial time algorithm can verify that
R is not restricted by first guessing the binary representation of n, and then testing whether
there is a path in the transition graph of an NDFA accepting L(R) of length n to a final state.
The latter step can be done deterministically in time polynomial in the length of R [21].
We reduce the problem of Proposition 2 to the present problem by showing that R is
not restricted if and only if R does not denote 0   . We have already shown that if R is not
restricted, then L(R) 6= 0   . Conversely, assume that R does not denote 0   . Let x be the
shortest string in 0   that is not in L(R). Since R is starred, L(R) is infinite, so there is a string
xy 2 L(R) for which y 6= ffl. But x is an abbreviation of xy; hence, by Theorem 4, R is not
restricted.
COROLLARY 3. Deciding whether a regular expression over alphabet S is not restricted
is NP-hard.
4. Constrained Cycles in Db-Graphs. In some instances, knowledge about the cyclic
structure of a db-graph G allows us to determine (without consulting G itself) that a particular
query QR can be evaluated in polynomial time on G. We have already shown that, in the
extreme case when G is acyclic, QR is always evaluable in polynomial time. Let us assume
that we know that the cyclic structure of G is constrained by a regular expression C; that is,
every cycle label in G is in L(C).
DEFINITION 12. Let C be a regular expression over S, and -) be a
db-graph. Let Y be the set of cycle labels in G, namely
is a cycle in Gg:
We say that G complies with C if Y ae L(C). The regular expression C is called a cycle
constraint.
Each cycle constraint C defines a class of db-graphs whose cyclic structure satisfies C .
For example, in this way we can define the classes of bipartite graphs, loop-free graphs, and
acyclic graphs by specifying the regular expressions respectively 2 . The
class of db-graphs with unconstrained cycles is defined by the expression + , which denotes
Before continuing, we need to introduce some terminology regarding properties of the
intersection graph of a db-graph and a transition graph.
DEFINITION 13. Let I be the intersection graph of db-graph
graph T of We say that a path
2 Recall that if then (underscore) is shorthand for a an .
in I is db-simple if v i In other words, p is
db-simple if and only if (v simple path in G. In addition, we call I simplicial
if whenever there is a path there is
a db-simple path from (v
, in which the first components of nodes
form a subset of the first components of nodes on p.
From the above definition and Lemma 1, it is clear that if the intersection graph I of a
db-graph and the transition graph corresponding to a regular expression R is simplicial, then
QR can be evaluated in polynomial time in the size of I . The following theorem characterizes
simplicial intersection graphs in the presence of cycle constraints.
THEOREM 8. Let C be a cycle constraint. For query QR , let
accepting L(R) and T be the transition graph of M . For every db-graph G complying
with C , the intersection graph I of G and T is simplicial if and only if whenever there is a
path from a reachable state s to t in T satisfying C , [s] ' [t].
Proof. (If) be a db-graph complying with C and
be a non-simple path satisfying R in G. Hence, there is a path q from (v
in I. For notational simplicity, let w
and w complies with C , w
Assume that ffi   (s t. So there is a path in T from s to t satisfying
C and a path from (v in I; hence, by assumption, [s] ' [t]. The string w 3 is in
[t] because p satisfies R, so w 3 2 [s] as well. It follows that w 1 w 3 2 L(R) and therefore that
satisfies R. This process can be repeated to obtain a db-simple path q 0 from (v
, such that the first components of q 0 form a subset of the first components of q. We
conclude that I is simplicial.
(Only if) Assume that there is a path p from s to t in T which satisfies C but for which
[t]. The constraint C cannot be , for otherwise p would not satisfy C . Since s is
reachable in T , there is a string w 1 such that ffi   (s cannot be , for
otherwise [s] ' [t]. So let w 3 be a string in [t] but not in [s], and w 2 be the path label of p.
The string w 2 cannot be ffl since p must be of length greater than zero. We can construct a
db-graph comprising a single non-simple path
such that -(e 1
complies with C since the only cycle in G is labelled with w 2 which is in L(C). The path q
L(R). Hence, there is a path from (v
in I. However, the path
does not satisfy R since w 1 w 3 62 L(R) (otherwise w 3 would be in [s]). Consequently, there
is no db-simple path from (v
I , and we conclude that I is not
simplicial.
The above result does not depend on the particular DFA accepting L(R). Consider two
accepting L(R), and let s
and t 2 S 2 be a pair of states such that there is a string x for which ffi
G complies with a cycle constraint compatible with R
R restricted
G acyclic
FIG. 6. Relationship between regular expression R and db-graph G for query QR .
t. Because L(M 1 must be the case that
In other words, the fact that Theorem 8 is true independent of the particular DFA chosen is
a consequence of the Myhill-Nerode theorem, which states that a language is accepted by
a DFA if and only if it is the union of some of the equivalence classes of a right-invariant
equivalence relation of finite index [13]. This leads us to the following definition.
DEFINITION 14. Let R be a regular expression and T be the transition graph for a DFA
accepting L(R). We say that R is compatible with cycle constraint C if whenever there is a
path from (a reachable state) s to t in T satisfying C, [s] ' [t].
Theorem 8 generalizes our previous results. For the case when G is acyclic, C =, and no
path in T satisfies C so the result holds vacuously. In other words, every regular expression
is compatible with . When the cyclic structure of G is unconstrained, C denotes S + , and
every path in T satisfies C , so [s] must contain [t] for all pairs of reachable states in T . This
corresponds to the case of restricted regular expressions; that is, a regular expression R is
compatible with C (where C denotes only if R is restricted. The relationship
among these properties is shown in Figure 6.
By appealing once again to the result of Lemma 1, we obtain the following corollary to
Theorem 8.
COROLLARY 4. Let C be a cycle constraint and G be a db-graph that complies with C .
A query QR on G can be evaluated in polynomial time in the size of both R and G if R is
compatible with C.
A simple algorithm for testing whether a regular expression is compatible with a cycle
constraint is given in Figure 7. Because it constructs DFAs from regular expressions R and C ,
the algorithm can take exponential time in the length of R and C . However, deciding whether
R and C are compatible is NP-hard, since deciding whether R is restricted is a special case
of testing compatibility.
THEOREM 9. Given a regular expression R and a cycle constraint C , deciding whether
R and C are compatible is NP-hard.
Example 7. Let R = (00)   . A DFA MR accepting L(R) is shown in Figure 8(a).
Because [a] 6' [b], we know that R is not restricted. In fact, we saw in Theorem 1 that
deciding if (x; y) 2 QR (G) is NP-complete for db-graphs in general. However, QR can
be evaluated in polynomial time on bipartite graphs. As we have already seen, the regular
defines the class of bipartite graphs. A DFA MC accepting L(C) is
shown in Figure 8(b), while the intersection graph I of MR and MC is given in Figure 9. The
only paths in I satisfying C which start from a node containing the initial state of MC and end
at a node containing a final state of MC are from (a; A) to (a; D) and from (b; A) to (b; D).
Since [a] ' [a] and [b] ' [b], Corollary 4 tells us that QR can be evaluated in polynomial time
on any bipartite graph.
Given a query QR and a db-graph G, if we know that G complies with cycle constraint
C , we can test whether R is compatible with C using the above algorithm. If so, we can
use a polynomial time algorithm to evaluate QR on G. On the other hand, if we do not
know about the cyclic structure of G, it seems that we might have to resort to an exponential
Algorithm: Testing whether a regular expression is compatible with a cycle constraint.
INPUT:
Regular expression R and cycle constraint C .
OUTPUT:
Whether or not R is compatible with C .
1. Construct DFAs accepting L(R) and
accepting L(C).
2. Compute the suffix containment relation for MR (Algorithm S in x3).
3. Construct the intersection graph I of MR \Theta MC .
4. Compute the transitive closure I + of I .
5. If [s] ' [t] for each edge ((s;
otherwise answer "no".
FIG. 7. Testing whether a regular expression is compatible with a cycle constraint.
ae-
O
ae-
(a)
ae-
ae-
ae -
O
ae-
--(b)
FIG. 8. DFAs (a) MR for
(b,B)
ae -
O
ae-
(a,D)
ae-
ae -
O
ae-
(b,D)
FIG. 9. The intersection graph I of MR and MC (Figure 8).
ae-
ff \Phi
a-ae-
ff \Phi
b-ae-
ff \Phi
ff \Phi
\Omega \Psi
O
ae-
ff \Phi
\Omega \Psi
O
ae-
ae-
A -\Omega \Omega \Omega \Omega \Omega \Omega AE
ae-
\Omega \Omega \Omega \Omega \Omega \Omega OE J
J-
a b
FIG. 10. A DFA M and db-graph G.
time algorithm if R is not restricted. In the next section, however, we describe an evaluation
algorithm which runs in polynomial time in the size of G if G happens to comply with a cyclic
constraint with which R is compatible.
5. An Evaluation Algorithm. In this section, we describe an algorithm for evaluating
a query QR on a db-graph G. As is to be expected from the results of x2, the algorithm does
not run in polynomial time in general. It does, however, run in polynomial time under the
sufficient conditions identified in x3 and x4, namely, when G is acyclic, R is restricted, or G
complies with a cycle constraint compatible with R. In fact, we show that the algorithm runs
in polynomial time if G and R are conflict-free, a condition implied by those above.
The evaluation algorithm traverses paths in G, using a DFA M accepting L(R) to control
the search by marking nodes as they are visited. We must record with which state of M a node
is visited, since we must allow a node to be visited with different states (which correspond to
distinct nodes in the intersection graph of G and M ). In order to avoid visiting a node twice
in the same state, we would like to retain the state markings on nodes as long as possible.
Unfortunately, the following example shows that, in general, requiring answer nodes to be
connected by simple paths in G and retaining state markings can lead to incompleteness in
query evaluation.
Example 8. Consider the query QR , where accepting
L(R) and a db-graph G are shown in Figure 10. Note the similarity between M and the
automaton of Figure 3 in x3. Assume that we start traversal from node A in G, and follow the
path to B, C and D. Nodes A, B, C and D are marked with states a, a, b and b, respectively,
and the answers (A; C) and (A; D) are found, since b is a final state. We cannot mark C with
state c because (A; B; C; D;C) is a non-simple path. If we now backtrack to node C , we can
resulting in the answer (A; E) being found. Node D is still marked with b
(as shown in Figure 10), so we backtrack to C . However, once again we cannot mark B with
state c because (A; B; C; B) is a non-simple path. So we backtrack to A, and find that E is
G and R are conflict-free
G complies with a cycle constraint compatible with R
R restricted
G acyclic
FIG. 11. Relationship between regular expression R and db-graph G for query QR .
already marked with state b. Consequently, the search terminates without the answer (A; B)
being found.
It turns out that it is safe to retain markings when G is acyclic or R is restricted. However,
because of the structure of a particular db-graph G, it might be the case that we can retain
markings and evaluate QR in polynomial time even if G is not acyclic and R is not restricted.
DEFINITION 15. Let I be the intersection graph of a db-graph G and a DFA
path in I is any path of the form ((v )). The
initial path p is conflict-free if (1) p is db-simple, or (2) p is q \Delta (v; s), where q is conflict-free
and if v appears in q, then for some (v; t) in q, [t] ' [s]. If for no (v; t) in q is it the case that
then there is a conflict at v.
If every simple initial path in I is conflict-free, then I is said to be conflict-free 3 , as are
G and R.
It is obvious that if G is acyclic, then I is conflict-free no matter what regular expression
R appears in QR . Also, if R is restricted, then, by Theorem 4, M exhibits the Containment
hence, I is conflict-free irrespective of the structure of G. Finally, if G complies
with a cycle constraint compatible with R, then, by Theorem 8, G and R are conflict-free. We
will show that QR can be evaluated in polynomial time if I is conflict-free. Hence, conflict-
freedom is another (weaker) sufficient condition for QR to be polynomial time evaluable (see

Figure

11).
The result of the following lemma is used in our evaluation algorithm.
LEMMA 3. Let I be the intersection graph of a db-graph
accepting L(R). An initial path p in I is conflict-free if and only if (1) p is db-simple or (2) p
is q \Delta (v; s), where q is conflict-free and if v appears in q, then for the first (v; t) in q, [t] ' [s].
Proof. The "if" direction is trivial. Assume that p is conflict-free but not db-simple.
Furthermore, assume that p is q \Delta (v; s), where q is conflict-free and v appears in q. We prove,
by induction on the number of occurrences of v in q, that [t] ' [s] where (v; t) is the first
occurrence of v in q.
The basis in which v occurs only once in q is trivial. Assume that the inductive hypothesis
is true for fewer than n occurrences of v in q, and let p be q \Delta (v; s). Since p is conflict-free,
we know from the definition that for some (v; r) in q, [r] ' [s]. By the inductive hypothesis,
Example 9. Consider again the DFA M and the db-graph G of Example 8 shown in

Figure

10. The intersection graph I of G and M is shown in Figure 12. Recall that, if
markings were retained, the answer (A; B) would not be found. However, there is a conflict
in I. This is because there is an initial path in I from (A; a) via (B; a) to (B; c), but [a] 6' [c].
3 This is a strictly weaker definition of conflict-freedom than that given in [18].
(C,c)
ae-
(B,a) -ae-
(C,b) -ae-
(B,c)
\Gamma\Psi
@
@
@ @R @
@
@
@I
FIG. 12. The intersection graph I of db-graph G and DFA M of Figure 10.
Algorithm C: Evaluation of a query on a db-graph.
INPUT:
Db-graph query QR .
OUTPUT:
QR (G), the value of QR on G.
1. Construct an DFA accepting L(R).
2. Initialize QR (G) to ;.
3. For each node v 2 N , set CM [v] and PM [v] to ;.
4. Test for each pair of states s and t in M .
5. For each node v 2 N ,
(a) call SEARCH(v; v; s 0 ,conflict) (see Figure 14)
(b) reset PM [w] to ; for any marked node w 2 N .
FIG. 13. Evaluation of a query on a db-graph.
Algorithm C detects such conflicts and unmarks nodes on backtracking, enabling the answer
B) to be found.
We now proceed with a description of Algorithm C, shown in Figure 13. The algorithm
uses a DFA accepting L(R) to control a depth-first search of the db-
graph G (Line 1). There are two reasons why a DFA rather than an NDFA is used. The first
is to ensure that no conflicts are encountered when R is restricted. The second reason is to
avoid detecting unnecessary conflicts in I . In an NDFA, if [s] 6' [t], it might be the case that
there is a state q such that both s and q are in ffi
node v in G is first marked with s, following which a cycle at v satisfying L st is traversed, a
conflict would be registered. This is unnecessary since v would subsequently be marked with
q, and any simple path from v satisfying [t] would be found because [q] ' [t].
Algorithm C traverses the transition graph of M and the db-graph G simultaneously,
in effect performing a depth-first search of the intersection graph I of G and M . We will
often refer to trees of the depth-first search forest generated by Algorithm C. Because of
Line 5(a), each tree T in the forest is rooted at an initial node of I . When a final node of I is
reached, Line 8 adds the appropriate pair of nodes from G to QR (G). Lines 9 and 10 force
the algorithm to consider only paths in G which satisfy R, that is, paths in I.
While the traversal of I is restricted to simple paths, it is not necessarily restricted to
db-simple paths; we will prove below that it is safe to traverse non-db-simple paths in the
procedure SEARCH (u; v; s, var conflict)
u and v are nodes in the db-graph
s is a state in the DFA
db-cycle is a Boolean flag
*/
6. conflict / false
7. CM [v] / CM [v] [ fsg
8. if s 2 F then QR (G) /
9. for each edge in G from v to w with label a do
11. if FIRST(CM
12. conflict / true
else /* CM
13. SEARCH (u; w; t, new-conflict)
14. conflict / conflict or new-conflict
od
15. CM [v] / CM
16. if not conflict then PM [v] / PM [v] [ fsg fi
FIG. 14. Search procedure for query evaluation.
absence of conflicts. Nodes in G are marked with states of M when they are visited. Two
sets of markings are used for each node v: (1) a set of current markings (CM [v]) which
indicates the states with which v is associated on the current path on the stack of procedure
(Lines 7 and 15), and (2) a set of previous markings (PM [v]) which represents
earlier markings of v, excluding the current path (Line 16). Current markings are used to
avoid cycles in I and to detect conflicts, while previous markings are used where possible
to prevent a node in G from being visited more than once in the same state during a single
execution of Line 5(a). The function FIRST applied to marking set CM [v] returns the first
state marking for v on the current path, or false if there is no marking.
A node w is visited in state t only if t is not in the previous markings of w and either w
is currently unmarked (CM [w] is empty) or the first state marking q for v on the current path
is such that [q] ' [t], that is, there is no conflict between q and t at (Lines 10 to 13). Note
that there may in fact be a conflict between t and some later marking of v on the current path,
but this does not affect the correctness of the algorithm, as we will demonstrate below.
Lines 6, 11 and 12 implement the conflict detection; that is, conflict is true if there is a
conflict between states q and t at node w. If conflict is set to true at Line 12, then Lines 14,
15 and 16 ensure that the marking of any node which was on the stack at the time the conflict
was detected is removed once that node is unstacked. If no conflict occurs on any path rooted
at (v; s), then s is added to the previous markings of v in Line 16.
In the proofs that follow, we will often say that (v; s), for example, is on the stack of
procedure SEARCH. The variables v and s refer to the middle two parameters of SEARCH
and correspond to the node (v; s) in the corresponding intersection graph. The reason for
excluding the other two parameters of SEARCH is that u (the first) remains unchanged during
an execution of Line 5(a), while we are not always concerned about the value of conflict. We
a)
(B; a)
@ @
@ @
(D; b) (B; c) (E; b) (C; c)
(C; c) (D; b) (B; c)
(B; c) (C; c)
(B; c)
(a)
a)
a)
(C; c)
(B; c)
(b)
FIG. 15. Two possible depth-first search trees.
will also sometimes exclude conflict when referring to a particular invocation of SEARCH, for
example, SEARCH(u; v; s). Before proving the correctness of Algorithm C, we demonstrate
its behaviour by means of an example.
Example 10. Consider again the intersection graph I of Figure 12. Two possible depth-first
search trees (DFSTs) traversed by Algorithm C are shown in Figure 15. Note that nodes
in a DFST can be repeated because of unmarking; for example, node (D; b) appears three
times in Figure 15(a). Dotted edges in the figure lead to nodes for which SEARCH is not
called, either because of a conflict (those in (a)), or because the node is already marked via
either CM or PM (as in (b)). These latter edges correspond to forward, back and cross edges
in a conventional DFST [2].
Assume that Algorithm C starts traversal from node (A; a), that is, SEARCH(A; A; a))
is called at Line 5(a), and that the order of traversal is according to the DFST in Figure 15(a).
Since initially nodes B, C and D have no current marking, Line 11 evaluates to false and
SEARCH is called successively with (B; a), (C; b) and (D; b). Because b is a final state,
C) and (A; D) are added to QR (G) by Line 8. Although C already has a current marking
(namely b), the fact that [b] ' [c] means that Line 11 again evaluates to false and SEARCH
is called with (C; c). Now because the first marking for B is a and [a] 6' [c], a conflict is
registered at Line 12. The algorithm now backtracks, removing current markings (Line 15)
and not assigning previous markings (Line 16).
Considering (B; c) from (C; b) again gives rise to a conflict, so the algorithm tries the
path via (E; b). Note that (D; b) and (C; c) are no longer marked so they are revisited, once
again giving rise to a conflict. By the time the algorithm backtracks to (A; a) all nodes (other
than are unmarked, so that the db-simple path to (B; c) can finally be found and (A; B)
added to QR (G).
If the path to (B; c) via (E; b) had been chosen first by Algorithm C (as in Figure 15(b)),
then no conflicts would have been detected, resulting in previous markings being kept for
B, D and E. On traversing the path to (C; b), Line 10 would ensure that (B; c), (D; b) and
are not revisited and no conflicts are registered.
LEMMA 4. If conflict is false at Line 16 of SEARCH(u; v; s), then Algorithm C has
performed an entire depth-first search of I from node (v; s).
Proof. The proof proceeds by induction on the length of the longest simple path p from
(v; s) in I . If p is of length zero, the result follows trivially. Assume the result holds for
nodes in I from which the longest simple path is of length
which the longest simple path in I is of length n.
For conflict to be false at Line 16 of SEARCH(u; v; s), it must be that, for each successor
(w; t) of (v; s) in I, either (1) t 2 PM [w] at Line 10, or (2) new-conflict must have been
false at Line 14. In case (1), conflict must have been false at Line 16 of SEARCH(u;w; t)
in order for t to be added to PM [w]. In case (2), conflict must have been false at Line 16
of SEARCH(u;w; t) so that new-conflict is false at Line 14. Since the longest simple path
from (w; t) in I must be of length less than or equal to n \Gamma 1, we conclude from the inductive
hypothesis that an entire depth-first search from (w; t) has been performed by Algorithm C.
Clearly, Lines 9 and 10 consider every successor of (v; s) in I, so the result follows.
DEFINITION 16. A node (v; s) in depth-first search tree T is called a conflict predecessor
if, for some successor (w; t) of (v; s) in I, w appears in an ancestor of (v; s) in T and, for the
first such occurrence (from the root), say (w; q), it is the case that [q] 6' [t]. In other words,
there is a conflict between q and t at w.
LEMMA 5. Consider the execution of SEARCH(u; v; s) in DFS tree T . State s is added
to PM [v] in Line 16 if and only if no descendant of (v; s) in T is a conflict predecessor.
Proof. If s is added to PM [v] in Line 16, then conflict must be false. Hence, by
Lemma 4, an entire depth-first search of I from (v; s) must have been performed. But a
conflict predecessor is a node (w; t) in T which has a successor in I that does not appear as
a successor of (w; t) in T . Thus, no conflict predecessor can appear as a descendant of (v; s)
in T .
If no descendant of (v; s) in T is a conflict predecessor, then conflict is false for all such
descendants and hence for (v; s) itself. Thus, s is added to PM [v] in Line 16.
be a db-graph, and R be a regular expression
over S. Let accepting L(R), and I be the intersection graph
of G and M . Algorithm C is correct; that is, Algorithm C adds (u; z) to QR (G) if and only if
there is a db-simple path from (u; s 0 ) to (z; s f ), s f 2 F , in I (that is, there is a simple path
from u to z in G satisfying R).
Proof. Algorithm C clearly terminates, since Line 10 ensures that only simple paths in I
are considered, and no simple path from an initial node is considered more than once.
(Only if ) If the algorithm adds (u; z) to QR (G), then it must traverse a depth-first search
tree T rooted at (u; s 0 ) in which there is a simple path p from (u; s 0 ) to (z; r), r 2 F .
Assume that p is not db-simple, and that the db-node v appears more than once on p. Let
the first occurrence of v on p be in I-node (v; s) and the last such occurrence be in (v; t).
Thus s was the first state added to CM [v], and in order for SEARCH(u; v; t) to have been
called in Line 13, Line 11 must have ensured that [s] ' [t]. Hence, there is a path p 0 from
(v; s) to (z; q), q 2 F , in I such that the sequence of db-nodes on p 0 is identical to that on
the path from (v; t) to (z; r) on p. Since (v; s) and (v; t) are the first and last occurrences,
respectively, of v on p, there is a path from (u; s 0 ) to (z; q), q 2 F , in I which is db-simple
with respect to v.
A simple induction on the number of repeated db-nodes on p shows that there is a
db-simple path from (u; s 0 ) to (z; s f
Assume there is a db-simple path p from (u; s 0 ) to (z; s f ), s f 2 F , in I. Obviously,
if the algorithm traverses p we are done. Assume that it does not. Let (v; s) be the last node
on p that is traversed, and (w; t) be the successor of (v; s) on p. The reason (w; t) is not
visited cannot be because of a conflict, since p is db-simple. So it must have been the case that
at Line 10. By Lemmas 4 and 5, an entire depth-first search of I from (v; s) must
have been performed. Since there is a path from (v; s) to (z; s f ) in I, SEARCH(u; z; s f )
must have been called in which case (u; z) would have been added to QR (G) in Line 8.
THEOREM 11. In the absence of conflicts, Algorithm C runs in an amount of time which
is bounded by a polynomial in the size of the db-graph.
Proof. The essential point is that, in the absence of conflicts, Algorithm C performs
a normal depth-first search of the intersection graph which is polynomial in the size of the
db-graph. A detailed analysis of the time complexity of the algorithm follows.
Let QR be a query where R is of length m, and G be a db-graph with n nodes and e
edges. Although there can be as many as O(2 m ) states in a DFA accepting L(R), this is just
a constant in terms of the size of G. Nevertheless, we will assume that M has q states and
will include q in our analysis of the time complexity of Algorithm C. Since M has at most
the intersection graph I for G and M has O(qn) nodes and O(q 2 e) edges.
Line 1 of Algorithm C can be done in O(q 2 ) time, while Line 2 requires only constant
time. Line 3 takes O(n) time and Line 4 O(q 2 ) time. Line 5 is executed n times, and, in any
execution, each node in I is visited at most once if I is conflict-free. This is because when
(v; s) is stacked s is added to CM [v] and Line 10 ensures that (v; s) cannot be restacked;
when (v; s) is unstacked, s is added to PM [v] (Line 16) and is not removed from PM [v]
until the present execution of Line 5(a) has terminated. Once again, Line 10 ensures that
(v; s) cannot be revisited during the present execution of 5(a).
Only constant time is needed for Lines 6, 12 and 14. For each db-node v, CM [v] can be
implemented as a stack with access to its bottom element through the function FIRST. Hence,
Lines 7, 11 and 15 can be performed in constant time, as can Line 16 since fsg and PM [v]
are disjoint (by Line 10). Line 8 can be implemented to take O(q) time: the pair (u; v) is
added to QR (G) if and only if there is no other final state in PM [v]. Line 10 can also be
done in O(q) time. Lines 9 and 10 inspect each edge leaving a node in I, and since no node
in I can be revisited, SEARCH can be called times. Each call takes O(q) time, so a
single execution of Line 5(a) takes O(q 3 e) time. A single execution of Line 5(b) takes O(n)
time, so the total time spent in Line 5 is O(n(q 3 e Consequently, Algorithm C runs in
In terms of the size of G, Algorithm C runs in O(ne) time (under the
assumption that there are more edges than isolated nodes).
From the relationship depicted in Figure 11, we obtain the following.
COROLLARY 5. Algorithm C evaluates QR on G in time polynomial in the size of G if
1. R is restricted,
2. G is acyclic, or
3. G complies with a cycle constraint compatible with R.
Even in the presence of conflicts, Algorithm C can run in polynomial time in the size of
G. This is the case, for example, if R is a (*)-free regular expression. Let q be the length
of R. If R is (*)-free, there are only a finite number of strings in L(R) and the length of the
longest such string is q. This then is also then an upper bound on the length of the longest
db-simple path in I. Hence, there can be at most O(n q ) db-simple paths in I . So even if
Algorithm C traverses every db-simple path in I exactly once (the worst case), it still runs in
polynomial time in the size of G.
A number of circumstances other than those identified above can lead to polynomial-time
solutions. For example, there are certainly queries that can be evaluated in polynomialtime on
arbitrary db-graphs but whose regular expressions are not restricted. One such class of regular
expressions are those of the form wa   , where w is a string of fixed length. Unfortunately,
there are db-graphs on which Algorithm C takes exponential time to evaluate the associated
queries.
Clearly, there is much scope for further investigation. Additional classes of queries/db-
graphs for which polynomial-time evaluation is possible should be identified and appropriate,
more general evaluation algorithms developed. Algorithm C itself could be enhanced so that
it reacts in a more sophisticated manner on detecting a conflict. One possibility is to flag the
source of the conflict and not to unmark nodes until the algorithm backtracks from the flagged
node.
6. Conclusions. We have addressed the problem of finding nodes in a labelled, directed
graph which are connected by a simple path satisfying a given regular expression. This
study was motivated by the observation that many recursive queries on relational databases
can be expressed in this form, and by the implementation of a query language based on this
observation.
We began by describing how a naive algorithm might evaluate such queries. Although
this algorithm runs in exponential time in the worst case, we showed that we cannot expect
to do better since the evaluation problem is in general NP-hard. Using the fact that the
associated problem for paths in general (as opposed to simple paths) is solvable in polynomial
time, we characterized the class of restricted regular expressions, whose associated queries
can be evaluated in polynomial time.
Having considered restrictions on the structure of regular expressions, we turned our
attention to the cyclic structure of the graphs being queried. We introduced the notion of a
cycle constraint, and showed that if a graph G complied with a cycle constraint which was
compatible with a regular expression R, then QR (G) could be evaluated in polynomial time.
Finally, we presented an algorithm for evaluating arbitrary expressions on arbitrary graphs.
This algorithm runs in polynomial time if (a) the regular expression is restricted or closure-
free, (b) the graph complies with a cycle constraint compatible with the regular expression
(a special case being when the graph is acyclic), or (c) the regular expression and graph are
conflict-free.
While it is difficult to say how often the above conditions will be encountered in practice,
we did show that the class of restricted regular expressions is closed under the regular
operators. A good starting point for investigation into larger classes of expressions and
graphs with polynomial-time evaluation algorithms would be to attempt to identify the class
of expressions and graphs which are not conflict-free, but on which Algorithm C runs in
polynomial time.
Our emphasis in this paper has been on identifying circumstances in which the regular
simple path problem can be solved in polynomial time, rather than designing the most efficient
algorithm for these cases. We believe this is a topic for future research. For example, it would
be interesting to see whether techniques used on sparse graphs, such as those in [16], could
be employed in our algorithm in order to improve its efficiency on sparse graphs.
We should point out that the analysis in this paper, and the implementation itself, assume
the graph can be entirely stored in main memory. This is a reasonable assumption in many
cases, especially because in the intended applications of our query language G + the graph
is often only the fraction of the database that can be presented visually in a natural way.
Relaxing this assumption provides an interesting area for further study. Other researchers,
investigating similar algorithms for transitive closure, have claimed that they are amenable to
efficient secondary storage implementation [15].
Finally, we note that research has been done on the expressive power of graph-based
query languages in which the restriction of simple path semantics is dropped. One such
language that captures exactly the queries computable in nondeterministic logarithmic space
is presented in [8]. On-line algorithms for regular path finding are given in [5], while a survey
of many results can be found in [24].



--R

Alpha: An extension of relational algebra to express a class of recursive queries
The Design and Analysis of Computer Algorithms
Universality of data retrieval languages
On the completeness of query languages for relational databases
A data structure for arc insertion and regular path finding

Relational completeness of data base sublanguages
Graphlog: a visual formalism for real life recursion
A graphical query language supporting recursion

The directed subgraph homeomorphism problem
Efficient evaluation for a subset of recursive queries
Introduction to Automata Theory
On the equivalence
Efficient transitive closure algorithms
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
The even-path problem for graphs and digraphs
Finding regular simple paths in graph databases
a practical approach to supporting recursive applications
A polynomial solution to the undirected two paths problem
Word problems requiring exponential time
Fast algorithms for solving path problems
Implementation of logical query languages for databases

--TR

--CTR
Kemafor Anyanwu , Amit Sheth, The  operator: discovering and ranking associations on the semantic web, ACM SIGMOD Record, v.31 n.4, December 2002
Kemafor Anyanwu , Amit Sheth, The  operator: discovering and ranking associations on the semantic web, ACM SIGMOD Record, v.31 n.4, December 2002
Dan C. Stefanescu , Alex Thomo , Lida Thomo, Distributed evaluation of generalized path queries, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Weighted path queries on semistructured databases, Information and Computation, v.204 n.5, p.679-696, May 2006
Gsta Grahne , Alex Thomo, Regular path queries under approximate semantics, Annals of Mathematics and Artificial Intelligence, v.46 n.1-2, p.165-190, February  2006
Phillip G. Bradford, Language constrained graph problems: a microcosm of engineering research and development, Proceedings of the 2nd WSEAS International Conference on Computer Engineering and Applications, p.71-76, January 25-27, 2008, Acapulco, Mexico
Makoto Murata, Extended path expressions of XML, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 2001, Santa Barbara, California, United States
Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States
Tae-Sun Chung , Hyoung-Joo Kim, XML query processing using document type definitions, Journal of Systems and Software, v.64 n.3, p.195-205, 15 December 2002
Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States
Gsta Grahne , Alex Thomo, Query containment and rewriting using views for regular path queries under constraints, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.111-122, June 09-11, 2003, San Diego, California
Partially ordered regular languages for graph queries, Journal of Computer and System Sciences, v.70 n.1, p.1-25, February 2005
Sergio Flesca , Filippo Furfaro , Sergio Greco, A graph grammars based framework for querying graph-like data, Data & Knowledge Engineering, v.59 n.3, p.652-680, December 2006
Yaron Kanza , Yehoshua Sagiv, Flexible queries over semistructured data, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.40-51, May 2001, Santa Barbara, California, United States
Sangwon Park , Hyoung-Joo Kim, SigDAQ: an enhanced XML query optimization technique, Journal of Systems and Software, v.61 n.2, p.91-103, March 2002
Gsta Grahne , Alex Thomo, Algebraic rewritings for optimizing regular path queries, Theoretical Computer Science, v.296 n.3, p.453-471, 14 March
Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
George A. Mihaila , Louiqa Raschid , Anthony Tomasic, Locating and accessing data repositories with WebSemantics, The VLDB Journal  The International Journal on Very Large Data Bases, v.11 n.1, p.47-57, August 2002
Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , D. Sivakumar , Andrew Tompkins , Eli Upfal, The Web as a graph, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-10, May 15-18, 2000, Dallas, Texas, United States
Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States
Elisa Bertino , Mohand-Sad Hacid , Farouk Toumani, Retrieval of semistructured Web data, Intelligent exploration of the web, Physica-Verlag GmbH, Heidelberg, Germany,
Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002
Stephen Dill , Ravi Kumar , Kevin S. McCurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.69-78, September 11-14, 2001
fine-grained access control system for XML documents, ACM Transactions on Information and System Security (TISSEC), v.5 n.2, p.169-202, May 2002
Mohand-Sad Hacid , Farouk Toumani , Ahmed K. Elmagarmid, Constraint-Based Approach to Semistructured Data, Fundamenta Informaticae, v.47 n.1-2, p.53-73, January 2001
Kemafor Anyanwu , Amit Sheth, -Queries: enabling querying for semantic associations on the semantic web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
Elisa Bertino , Ahmed K. Elmagarmid , Mohand-Sad Hacid, Ordering and Path Constraints over Semistructured Data, Journal of Intelligent Information Systems, v.20 n.2, p.181-206, March
Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Journal of the ACM (JACM), v.45 n.5, p.798-842, Sept. 1998
Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
regular expressions;NP-completeness;labelled directed graphs;simple paths;polynomial-time algorithms