Barbara Fila
email: fila@univ-orleans.fr

Siva Anantharaman

Automata for Analyzing and Querying Compressed Documents

Keywords: Tree automata, Tree grammars, Dags, XML, Core XPath

In a first part of this work, tree/dag automata are defined as extensions of (unranked) tree automata which can run indifferently on trees or dags; they can thus serve as tools for analyzing or querying any semi-structured document, whether or not given in a compressed format. In a second part of the work, we present a method for evaluating positive unary queries, expressed in terms of Core XPath axes, on any dag t representing an XML document possibly given in a compressed form; the evaluation is done directly on t, without unfolding it into a tree. To each Core XPath query of a certain basic type, we associate a word automaton; these automata run on the graph of dependency between the non-terminals of the minimal straightline regular tree grammar associated to the given dag t, or along complete sibling chains in this grammar. Any given positive Core XPath query can be decomposed into queries of the basic type, and the answer to the query, on the dag t, can then be expressed as a sub-dag of t whose nodes are suitably labeled under the runs of such automata.

Introduction

Several algorithms have been optimized in the past, by using structures over dags instead of over trees. Tree automata are widely used for querying XML documents (e.g., [START_REF] Gottlob | Monadic Queries over Tree-Structured Data[END_REF][START_REF] Gottlob | Monadic Datalog and the Expressive Power of Languages for Web Information Extraction[END_REF][START_REF] Neven | Automata Theory for XML Researchers[END_REF][START_REF] Neven | Query automata over finite trees[END_REF]); on the other hand, the notion of a compressed XML document has been introduced in [START_REF] Buneman | Path queries on compressed XML[END_REF][START_REF] Frick | Query Evaluation of Compressed Trees[END_REF][START_REF] Marx | XPath and Modal Logics for Finite DAGs[END_REF], and a possible advantage of using dag structures for the manipulation of such documents has been brought out in [START_REF] Marx | XPath and Modal Logics for Finite DAGs[END_REF]. It is legitimate then to investigate the possibility of using automata over dags instead of over trees, for querying compressed XML documents.

Dag automata (DA) were first introduced and studied in [START_REF] Charatonik | Automata on DAG Representations of Finite Trees[END_REF]; a DA was defined there as a natural extension of tree automaton, i.e. as a bottom-up tree automaton running on dags; and the language of a DA was defined as the set of dags that get accepted under (bottom-up) runs, defined in the usual sense; the emptiness problem for DAs was shown there to be NP-complete, and the membership problem proved to be in NP; but the problem of stability under complementation of the class of dag automata -closely linked with that of determinization-was left open. These two issues have since been settled negatively in [START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF]: the reason is that the set of all terms (trees) represented by the set of dags accepted by a non-deterministic DA is not necessarily a regular tree language; a consequence is that the class of tree languages recognized by DAs (as sets of accepted dags) is a strict superclass of the class of regular tree languages. It is well-known however, that answers to MSO-definable queries on (semi-)structured trees form regular tree languages ( [START_REF] Thatcher | Generalized finite automata theory with an application to a decision problem of second-order logic[END_REF]); it is thus necessary to define the languages of DAs in a manner different from that of [START_REF] Charatonik | Automata on DAG Representations of Finite Trees[END_REF][START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF], if they are to serve as tools for analyzing and querying a document, independently of whether it is given in a (partially or fully) compressed format, or as a tree. Our first aim in this work is therefore to redefine the notion of the language of a DA suitably, with such an objective.

For achieving that, we first present (in Section 2) the notion of a compressed document as a tree/dag (trdag, for short), designating a directed acyclic graph that may be partially or fully compressed. The terminology trdag has been chosen to distinguish it from that of tdag employed in [START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF]; this latter term will be employed in this paper when referring to a fully compressed dag. A Tree/Dag automaton (TDA, for short) is then defined as an automaton which runs on trdags. The essential differences with the DAs of [START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF] are the following: (i) our TDAs can be unranked, and (ii) although the transition rules of a TDA look quite like those of the DAs in [START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF], or those of TAs, a run of a TDA on any given trdag t will carry with it not only assignments of states to the nodes of t, but also to the edges of t; runs will be so defined that a TDA accepts any given trdag t if and only if it accepts the tree t obtained by uncompressing t, as a tree automaton running on the tree t, in the usual sense.

In the second part of the paper, we present an approach based on word automata for evaluating queries on trdags that represent XML documents in a partially or fully compressed format; the terms 'trdag' and 'document' will therefore be considered synonymous in the sequel. Any given trdag t is first seen as equivalent to a minimal straightline regular tree grammar L t , that one can naturally associate with t, cf. e.g., [START_REF] Busatto | Grammar-Based Tree Compression[END_REF][START_REF] Busatto | Efficient Memory Representation of XML Documents[END_REF]. From the grammar L t , we construct the graph of dependency D t between its non-terminals, and also the chiblings (linear graphs formed of complete chains of sibling non-terminals) of L t . The word automata that we build below will run on D t or the chiblings of L t , rather than on the document t itself.

We shall only consider positive unary queries expressed in terms of Core XPath axes. (The view we adopt allows us to define the various axes of Core XPath on compressed documents, in a manner which does not modify their semantics on trees.) For evaluating any such query on any document (trdag) t, we proceed as follows. We first break up the given query into basic sub-queries of the form Q= //*[axis::σ] where axis is a Core XPath axis of a certain type. To each such basic query Q, we associate a word automaton A Q . The automaton A Q runs on the graph D t when axis is non-sibling, and on the chiblings of L t when axis is a sibling axis. An essential point in our method is that the runs of A Q are guided by some well-defined semantics for the nodes traversed, indicating whether the current node answers Q, or is on a path leading to some other node answering Q. The automaton is not deterministic, but its runs are made effectively unambiguous by defining a suitable priority relation between the transitions, based on the semantics. A basic query Q can then be evaluated in one single top-down pass of A Q , under such an unambiguous run. An arbitrary positive unary Core XPath query can be evaluated on t by combining the answers to its various basic sub-queries, and its answer set is expressed as a sub-trdag of t, whose nodes get labeled in conformity with the semantics. It is important to note that the evaluation is performed on the given trdag t; as such, on two different trdags corresponding to two different compressions of a same XML tree, the answers obtained may not be the same, in general.

The paper is structured as follows: Section 2 presents the notions of trdags, and of Tree/Dag automata. In Section 3, we construct from any trdag t its normalized straightline regular tree grammar L t , as well as the dependency graph D t and the chiblings of L t ; these will be seen as rooted labeled acyclic graphs (rlags, for short); the basic notions of Core XPath are also recalled. Section 4 is devoted to the construction of the word automata for any basic Core XPath query, based on the semantics, and an illustrative example. In Section 5 we prove that the runs of these automata, uniquely and effectively determined under a maximal priority condition, generate the answers to the queries. Section 6 shows how a non basic (composite, or imbricated) Core XPath query can be evaluated in a stepwise fashion. In Section 7, we show how to refine our approach, so as to derive from the answer for any given Core XPath query Q on a trdag t, the answer set for the same query Q on the tree-equivalent t of t (without resorting to any uncompressing operation). In the appendices, we show how to translate the 'usual' Core XPath queries into one in 'standard' form on which our approach is applicable; this translation is done in linear time on the size of the given query; we also present an algorithm for constructing the maximal priority run, for any basic query automaton over any given document (trdag), with a complexity bound of O(m), where m is the number of edges of the rlag D t associated to the trdag. (Note: the number m of edges on D t can be exponentially smaller than the number of edges on the trdag t. When t is a tree, D t is isomorphic to t, so the complexity of our algorithm reduces to O(n), where n is the number of nodes on the tree t.) A complete illustrative example, on a composite imbricated query, is given in the last appendix. (It is assumed that any trdag tis connected, and has a unique root node.) Given any node u on a trdag t, the notion of the sub-trdag of t rooted at u is defined as usual, and denoted as t| u . If v is any node, γ(v) = u 1 . . . u n will denote the string of all its not necessarily distinct children nodes; for every 1 ≤ i ≤ n, the i-th outgoing edge from v to its i-th child node u i ∈ γ(v) will be denoted as e(v, i); we shall also write then v i -→ u i ; the set of all outgoing (resp. incoming) edges at any node v will be denoted as Out v (t), or Out v (resp. In v (t), or In v ); and for any node u, we set: P arents(u) = {v ∈ N odes(t) | u is a child of v}.

Tree/Dag Automata

A trdag t is said to be a tree iff In v (t) is empty if v is root, and In v (t) is singleton otherwise. On any trdag t, we define the set P os(t) as the set of all the positions pos t (u) of all its nodes u, these being defined recursively, as follows: if u is the root node on t, then pos t (u) = , otherwise, pos t (u) = {α.i | α ∈ pos t (v), v is a parent of u, u is an i-th child of v}. The set P os(t) consists of (some of the) words over natural integers. To any edge e : u i -→ v on a trdag t, is naturally associated the subset pos t (e) = pos t (u).i of P os(t).

The function name t is extended naturally to the positions in P os(t) as follows: for every u ∈ N odes(t) and α ∈ pos t (u), we set name t (α) = name t (u). Given a trdag t, we define its tree-equivalent as a tree t such that: P os( t) = P os(t), and for every α ∈ P os(t) we have name t (α) = name t(α). It is immediate that t is uniquely determined, up to a tree isomorphism; it can actually be constructed canonically (cf. [START_REF] Frick | Query Evaluation of Compressed Trees[END_REF]), by taking for nodes the set P os(t), and for directed edges the set {(α, α.i) | α, α.i ∈ P os(t)}, each node α being named with name t (α). There is then a natural, name preserving, surjective map from N odes( t) onto N odes(t); it will be referred to in the sequel as the compression map, and denoted as c.

A trdag is said to be a tdag, or fully compressed, iff for any two different nodes u, u on t, the two sub-dags t| u and t| u have non-isomorphic tree-equivalents; otherwise, the trdag is said to be partially compressed when it is not a tree. For example, the tree to the left of Figure 1 is the tree-equivalent of the partially compressed trdag to the right, and also to the fully compressed tdag to the middle. We define now the notion of a Tree/Dag automaton, first over a ranked alphabet Σ, to facilitate understanding. The definition is then easily extended to the unranked case.

Compressed

Definition 2 A Tree/Dag automaton (TDA, for short) over a ranked alphabet Σ is a tuple (Σ, Q, F, Δ), where Q is a finite non-empty set of states, F ⊆ Q is the set of final (or accepting) states, and Δ is a set of transition rules of the form: f (q 1 , ..., q k ) → q, where f ∈ Σ is of rank k, and q 1 , . . . , q k , q ∈ Q.

It will be convenient to write the transition rules of a TDA in a different (but equivalent) form: a transition of the form f (q 1 , . . . , q k ) → q is also written as (f, q 1 . . . q k ) → q, where q 1 . . . q k is seen as a word in Q * , of length = rank(f ) in the ranked case. The notion of a TDA is then extended easily to the unranked case, i.e., where the signature symbols naming the nodes are not assumed to be of fixed rank: it suffices to define the transitions to be of the form (f, ω) → q, where ω is a regular expression on the alphabet set Q.

A TDA is said to be bottom-up deterministic iff whenever there are two transition rules of the form (f, ω) → q, (f, ω ) → q , with q = q , we have necessarily ω ∩ ω = ∅; otherwise it is said to be non-deterministic. We also agree to denote the transitions of the form (f, ∅) → q simply as f → q, and refer to them as initial transitions.

For defining the notion of runs of TDAs on a trdag in a bottom-up style, we need some preliminaries. Let A be a TDA with state set Q and transition set Δ. Suppose t is a trdag and assume given a map M : Edges(t) → Q. If u is any node on t with u 1 . . . u n as the string of all its (not necessarily distinct) children, the string M (e(u, 1)) . . . M(e(u, n)) ∈ Q * , formed of states assigned by M to the outgoing edges at u, will be denoted as M (Out u ). We then define, recursively in a bottom-up style, a binary relation at u on the states of Q, with respect to (w.r.t. or wrt, for short) the given map M ; this relation, denoted as M u = u , is defined as follows: Definition 3 Let A, t, M be as above, and u any given node on the trdag t.

• If u is a leaf with name(u) = a , then q u q iff whenever a → q ∈ Δ we also have a → q ∈ Δ; • otherwise q u q iff: (i) (name(u), M(Out u )) → q is an instance of a transition rule in Δ; i.e., Δ has a rule (name(u), ω) → q such that M (Out u ) is in ω; (ii) there exists a map σ q : Q → Q, such that:

-σ q (q) = q , and the rule (name(u), σ q (M (Out u ))) → q is also an instance of a transition rule in Δ; -for any edge e : u i -→ u ∈ Out u , we have: M (e) u σ q (M (e)). Definition 4 Let A = (Σ, Q, F, Δ) be any given TDA, and t any given trdag. A run of A on t is a pair (r, M ), where r : N odes(t) → Q and M : Edges(t) → Q are maps such that the following conditions hold, at any node u on t:

(1) if name(u) = f , then the rule (f, M (Out u )) → r(u) is an instance of a transition rule in Δ;

(2) there is an incoming edge e ∈ In u with M (e) = r(u); and for every e ∈ In u such that M (e ) = q = q = r(u), we have q M u q A run (r, M ) is accepting on a trdag t iff r( ) ∈ F , i.e, r maps the root-node of t to an accepting state. A trdag t is accepted by a TDA iff there is an accepting run on t. The language of a TDA is the set of all trdags that it accepts. Remark 1. i) Note that if t is a tree, then In u is singleton at every non-root node u on t, so a run (r, M ) of any TDA on t can be identified with its first component r; we get then the usual notion of runs of tree automata on trees. Example 1. Over the unranked signature {a, f, g} consider a TDA A, with the following transitions:

a → p, b → q , b → p, b → q,
(a, p) → q, (a, q) → p, (a, q ) → q, (g, q Q * ) → q, (g, p q) → p, (f, q p q) → q fin , (f, p Q * ) → q fin , with Q = {p, q, q , q fin }, and q fin as the unique accepting state. An accepting bottom-up run of A on a tdag is depicted on the left of Figure 2, and on its right, the "same" run as seen on the tree equivalent of the tdag. A few comments on the above run may be of help: we start with assigning state q to the leaf node b, under r; the assignments of state q under M to all the incoming edges at this node b poses no problem; we can then assign state p to node a, and subsequently also p to the node g, under r, via the transition rule (g, pq) → p; we then assign p under M to the first incoming edge at g; to assign state q under M to the second incoming edge at g, we just need to check that:

-for a map σ : Q → Q such that σ(p) = q, σ(q) = p, the rule (g, σ(p)σ(q)) → q is an instance of a transition rule of the TDA;

-for the outgoing edge g → a, labeled with p by M , we have p a q = σ(p); -for the outgoing edge g → b, labeled with q by M , we do have q b p = σ(q); reaching q fin at the root-node is trivial via the last transition rule. (Note that we could have as well assigned p under M to the second incoming edge at g, with no conditions to check, then reach q fin .) Remark 1 (contd.). ii) Unlike the DAs of [START_REF] Charatonik | Automata on DAG Representations of Finite Trees[END_REF] or [START_REF] Anantharaman | Closure Properties and Decision Problems of Dag Automata[END_REF], the following bottom-up non-deterministic TDA: a → q 1 , a → q 2 , f(q 1 , q 2 ) → q a , with q 0 , q 1 , q a as states where q a is accepting, has a non-empty language: as a TDA it accepts f (a, a).

For a deterministic TDA, we have the following result (as expected):

Proposition 1 Let A be a bottom-up deterministic TDA, and t any given trdag; then there is at most one run of A on t.

Proof. Let Q be the set of states of A, and M : Edges(t) → Q any given map assigning states to the edges on t. We shall show by induction that the hypothesis of determinism on A implies that, at any node u on t, the binary relation M u = u defined above (Definition 3), w.r.t. the map M , is the identity relation on the set Q. The proposition will then follow from conditions (1) and (2) on runs, cf. Definition 4; we will get, in particular, that for every incoming edge e at u, M (e) must be the same as r(u); so the run can be identified with its first component r (as on a tree).

The induction will be on a non-negative integer d u , that we define at any node u of t -and refer to as its height on t-as the maximal number of arcs on t from u to the leaf nodes. If d u = 0, then u is a leaf node; that u is the identity relation on Q in this case is immediate, from the determinism of A, and the definition of u . So, assume that d u > 0, and let v 1 . . . v n be the string of all the children nodes of u on t. By the inductive hypothesis, for every i, 1 ≤ i ≤ n, the relation vi is the identity relation on Q; it follows then, from the conditions (i) and (ii) on the relation u (Definition 3), that this latter must also be the identity relation on Q.

We may now formulate the principal result of the first part of this paper:

Proposition 2 A TDA accepts a trdag t if and only if it accepts the tree equivalent of t.

Proof. Let t be the tree equivalent of the trdag t, and c the natural surjective compression map from N odes( t) onto N odes(t).

For proving the 'only if' part of the assertion, one uses the following reasoning, coupled with induction on the height function at the nodes of t (defined in the proof of the previous proposition): Let (r, M ) be an accepting run of the given TDA on the trdag t; consider a node s on the tree equivalent t, of which the node u on t is the image under the compression map c; let r(u) = q under the given run of the TDA on t; then, for every state q of the TDA such that q M u q , one can construct a partial run of the TDA -seen as a usual tree automatonon the tree t, climbing up from a leaf below s on t to the node s, and assigning the state q to this node (for an illustrative example, see the tree to the right of Figure 2).

Proving the 'if' part of the assertion is a little more complex. We start with a given accepting run ρ of the given TDA, as a bottom-up tree automaton running in the usual sense on the tree t; from this run ρ, we shall construct a run (r, M ) of the TDA on the trdag t, by an inductive, top-down traversal of the tdag t; for this top-down traversal, we will be using an integer valued function defined at any node u of t -and referred to as its depth on t-as the maximal number of arcs on t from the root node on t to the node u. We shall also use the fact that the nodes of t are in natural bijection with the set P os(t) of positions on t. The topdown construction of the run (r, M ) is done by the following pseudo-algorithm, where d stands for the maximal depth on t at its leaf nodes. BEGIN /* define first r at the root node on t, and M on its outgoing edges */ r( t ) = ρ( t); For every outgoing edge e j , 1 ≤ j ≤ k, at t , set M (e j ) = ρ( .j); i = 1; /* Now go down */ while (i < d) do { For every node u at depth i do { choose e ∈ In u (t), and α ∈ pos t (e) such that M (e) = ρ(α); set r(u) = M (e);

For every

e j ∈ Out u (t), 1 ≤ j ≤ m, outgoing from u, set M (e j ) = ρ(α.j); } i = i + 1; } END.
It is not difficult to check then, that by construction, the pair of maps (r, M ) gives an accepting run of the TDA on the trdag t.

We illustrate here the reasoning employed in the proof of the 'if' part of the above proposition, with the tdag t of Example 1. We start with the run ρ on its tree-equivalent t, as depicted to the right of Figure 2. At start, to the root node on t (at depth 0) is assigned the state q fin , and to its three outgoing edges, are assigned the three states p, q, q respectively; at g, which is the only node on t at depth 1, we choose the first incoming edge (of position 1, and labeled with p by M ), and set r(u) = ρ(1) = p; the two outgoing edges at g on t have as positions the sets {11, 21}, {12, 22} respectively; to these two outgoing edges at g on t, we assign the states that ρ assigns to the two sons of the node g at position 1 on t, namely p, q respectively (this means in essence that we have 'selected' the positions 11 and 12 on the two outgoing edges at g on t); next, we go to depth 2 on t, where a is the unique node, to which we then have to assign the state ρ [START_REF] Lohrey | Word problems and membership problems on compressed words[END_REF] that M has already assigned to its incoming edge; the rest of the reasoning is obvious, so left out. Remark 2. i) Let t = t be two given trdags such that P os(t ) = P os(t), and there is a name preserving surjective map c from N odes(t ) onto N odes(t). We can then define t to be a compression, or compressed form, of t ; and refer to t as an uncompressed equivalent of t, and to the surjective map c on N odes(t ) as a compression map. It is easily checked that t and t have then the same tree-equivalent; and it follows from Proposition 2 above that any given TDA A accepts t if and only if it accepts t . It is legitimate then, to define the language of a TDA as the set of all tdags that it accepts (or trees that it accepts), or as the set of all trdags accepted, up to tree-equivalence.

ii) Unranked trees are often studied in the literature by transforming them into ranked binary trees, using the well-known "first-child, next-sibling" encoding for the transformation (done in linear time wrt the number of nodes of the given tree). However, such an encoding is meaningless on trdags, since a node can stand for several distinct nodes of its tree-equivalent, and the notions of first-child and next-sibling can be meaningful on trdags only when referring to the position sets of the nodes. What the above proposition says is that tree automata can run on trdags without any need for transforming the trdag into a (ranked) tree, or transforming the automaton itself in some way. In particular, the unranked query automata, e.g., as defined in [START_REF] Gottlob | Monadic Queries over Tree-Structured Data[END_REF], can be used for querying semi-structured documents that are given in the form of trdags. However, we shall propose, in the sections to come. an entirely different approach for query evaluation on trdags.

Querying Compressed Documents: Preliminaries

Given a trdag t, one can naturally construct a regular tree grammar associated with t, which is straightline (cf. [START_REF] Busatto | Efficient Memory Representation of XML Documents[END_REF]), in the sense that there are no cycles on the dependency relations between its non-terminals, and each non-terminal produces exactly one sub-trdag of t. Such a grammar will be denoted as L t , if it is normalized in the following sense:

(i) for every non-terminal A i of L t , there is exactly one production of the form A i → f (A j1 , . . . , A j k ), where i < j r for every 1 ≤ r ≤ k; we shall then set Sons(A i ) = {A j1 , . . . , A j k }, and symb Lt (A i ) = f ;

(ii) the number of non-terminals is the number of nodes on t. Such a normalized grammar L t is uniquely defined up to a renaming of the nonterminals. For instance, for the trdag t to the left of Figure 3 we get the following normalized grammar:

A 1 → f (A 2 , A 3 , A 4 , A 5 , A 2 ), A 2 → c, A 3 → a(A 5 ), A 4 → b, A 5 → b.
Such a grammar is easily constructed from t, for instance by using a standard algorithm which computes the 'depth' of any node (as the maximal distance from the root), to number the non-terminals so as to satisfy condition (i) above. The dependency graph of the normalized grammar L t associated with t, and denoted as D t , consists of nodes named with the non-terminals A i , 1 ≤ i ≤ n, and one single directed arc from any node A i to a node A j whenever A j is a son of A i . The root of D t is by definition the node named A 1 . The notion of Sons of the nodes on D t is derived in the obvious way from that defined above on L t .

F t D A 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( A 1 ) _ f ( , t: b b a f c A 2 (c, _ ) A 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( : 1 F A 5 b, ) _ ( A 1 ) _ f ( , 0 : F : 3 :
Furthermore, to any production A i → f (A j1 , . . . , A j k ) of L t , we associate a rooted linear graph composed of k nodes respectively named A j1 , . . . , A j k , with root at A j1 and such that for all l ∈ {2, . . . , k} the node named A j l is the son of the node named A j l-1 . This graph will be called the chibling of L t associated with the (unique) A i -production; it is denoted as F i . We also define a further chibling denoted F 0 , as the linear graph with a single node named A 1 , where A 1 is the axiom of L t .

In the sequel, we designate by G either D t or any of the chiblings F of L t . We complete any of these acyclic graphs G into a rooted labeled acyclic graph (rlag, for short), by attaching to each node u on G, with name(u) = A i , a label denoted label(u), and defined as label(u) = (symb Lt (A i ), -); cf. Figure 3.

Positive Core XPath Queries on trdags

In this paper we restrict our study to positive Core XPath queries on trdags. Recall that Core XPath is the navigational segment of XPath, and is based on the following axes of XPath (cf. [START_REF] Gottlob | The complexity of XPath query evaluation and XML typing In[END_REF][START_REF]World Wide Web Consortium, XML Path Language (XPath Recommendation[END_REF]): self, child, parent, ancestor, descendant, following-sibling, preceding-sibling. A location expression is defined as a predicate of the form [axis::b], where axis is one of the above axes, and b is a symbol of Σ. Given any trdag t over Σ, a context node u on t and b ∈ Σ, the semantics for axis is defined by evaluating this predicate at u. The semantics for the axes self, child, descendant are easily defined, exactly as on trees (cf. [START_REF]World Wide Web Consortium, XML Path Language (XPath Recommendation[END_REF]). For defining the semantics of the remaining axes, we first recall that P arents(u) = {v ∈ N odes(t) | u is a child of v}. For the 'composite' axes descendant-or-self and ancestor-or-self, the semantics are then deduced in an obvious manner. We shall also need position predicates of the form [position()= i]; their semantics is that the expression [child::b [position()= i]] evaluates to true at a context node u, iff: [child::b] evaluates to true at u, and u is an i-th child of some parent.

Positive Core XPath query expressions are usually defined in the literature (cf. e.g., [START_REF] Frick | Query Evaluation of Compressed Trees[END_REF]), as those generated by the following grammar:

A ::= self | child | descendant | parent | ancestor | preceding-sibling | following-sibling S can ::= A::σ | position()= i | S can and S can | S can or S can E can ::= A:: * [S can ] | E can [E can ] Q can ::= /S can | /E can | Q can /Q can
We shall refer to the query expressions generated by this grammar as canonical; they can be shown to be of the type /C 1 /C 2 / . . . /C n , where each C i is of the form A::σ[X can ], or of the form A::σ[X can ] conn A'::σ [X can ], with conn ∈ {and, or}, and X can , X can ∈ {S can , E can , true}; we agree here to identify A::σ[true] with A::σ.

Any such positive Core XPath query expression can be translated into one that is in "standard form", i.e., where the format of the sub-queries is of the type 'axis::b'; we formalize this idea now. We shall refer to the axes self, child, descendant, parent, ancestor, preceding-sibling, following-sibling as basic. A basic Core XPath query is a query of the form //*[axis::σ], where axis is a basic axis. More generally, the queries we propose to evaluate on trdags are defined formally as the expressions Q std generated by the following grammar, where σ stands for any node name on the documents, or for * (meaning 'any'):

A Core XPath queries Q std of the format generated by this grammar are said to be in standard form; to be able to handle any positive Core XPath query with such a grammar, we have introduced a special predicate called Root, deemed true only at the root node of the trdag considered.

By the evaluation of a given query expression Q on any trdag t, we mean the assignment: t → the set of all context nodes on t where the expression Q evaluates to true (following the conventions of Definition 2); this latter set is also called the answer for Q on t. Two given queries Q 1 , Q 2 are said to be equivalent iff, on any trdag t, the answer sets for Finally, following [START_REF] Buneman | Path queries on compressed XML[END_REF], for any set S of nodes on t, the sets of nodes following(S) and preceding(S) can now be defined formally, as follows:

following(S) = descendant-or-self(following-sibling(ancestor-or-self(S))), preceding(S) = descendant-or-self(preceding-sibling(ancestor-or-self(S))). Note: Unlike on a tree, the ancestor, descendant, following, self and preceding axes do not partition the set of nodes on a trdag t, in general.

Automata for the Basic Core XPath Queries

The Semantics of the Approach

We first consider basic Core XPath queries. Composite or imbricated queries will subsequently be evaluated in a stepwise fashion; see Section 6.

To any basic query Q = //*[axis::σ], we shall associate a word automaton (actually a transducer), referred to as A Q . It will run top-down, on the rlag D t if axis is non-sibling, and on each of the chiblings F of L t otherwise. In either case, a run will attach, to any node traversed, a pair of the form ( l, x), where the component l of the pair has the intended semantics of selection or not, by Q, of the corresponding node on t, and the component x will be a 1 or 0, with the intended semantics that x = 1 iff the corresponding node on t has a descendant answering Q. At the end of the run, label(u), at any node u of D t , will be replaced by a new label derived from the ll-pairs attached to u by the run.

To formalize these ideas, we introduce a set of new symbols L = {s, η, , } referred to as llabels (the term 'llabel' is used so as to avoid confusion with the term label). We define ll-pairs as elements of the set L × {0, 1}, and the states of A Q as elements of the set {init} ∪ (L × {0, 1}). For any Q, the automaton A Q is over the alphabet Σ ∪ {s, η}, has init as its initial state, and has no final state. The set Δ Q of transitions of A Q will consist of rules of the form (q, τ ) → q where q ∈ {init} ∪ (L × {0, 1}), q ∈ (L × {0, 1}), and τ ∈ Σ ∪ {s, η}.

For any rlag G, we define a function llab : N odes(G) → Σ ∪ {s, η}, by setting llab(u) = π 1 (label(u)), the first component of label(u). The automaton A Q associated to a basic query Q =//*[axis::σ] will run top-down on the rlag G, where G is D t if axis is a basic non-sibling axis, and G is any chibling F of L t if axis is a basic sibling axis. A run of A Q on G is a map r : N odes(G) → L×{0, 1}, such that, for every u ∈ N odes(G), the following holds:

-if u is root G , then the rule (init, llab(u)) → r(u) is in Δ Q ; -otherwise, for every v ∈ γ(u) the rules (r(u), llab(v)) → r(v) are all in Δ Q . (Note: when axis is non-sibling, this amounts to requiring that, for any node v, the state r(v) must be in conformity with the states r(u) for every parent node u of v, with respect to the rules in Δ Q .)

From the run of the automaton A Q and from the states it attaches to the nodes of D t , we will deduce, at every node u of t, a well-determined ll-pair as (a new) label at u, via the natural bijection between N odes(t) and N odes(D t ). The ll-pairs thus attached to the nodes of t will have the following semantics (where x stands for the name of the node u on t, corresponding to the 'current' node on D t ): -( , 1) : x = σ, current node on t is selected by (i.e., is an answer for) Q; -( , 1) : x = σ, current node is not selected, but has a selected descendant; -( , 0) : x = σ, current node is not selected, and has no selected descendant; -(s, 1) : x = σ, current node is selected; -(η, 1) : x = σ, current node is not selected, but has a selected descendant; -(η, 0) : x = σ, current node is not selected, and has no selected descendant.

Only the nodes on D t , to which the run of A Q associates the labels (s, 1) or ( , 1), correspond to the nodes of t that will get selected by the query Q. The ll-pairs with boolean component 1 will label the nodes of D t corresponding to the nodes of t which are on a path to an answer for the query Q; thus the automata A Q will have no transitions from any state with boolean component 0 to a state with boolean component 1. Moreover, with a view to define runs of such automata which are unique (or unambiguous in a sense that will be presently made clear), we define the following priority relations between the llpairs:

(η, 0) > (η, 1) > (s, 1), and ( , 0) > ( , 1) > ( , 1). A run of the automaton A Q will label any node u on G with an ll-pair either from the group {( , 0), ( , 1), ( , 1)} or from the group {(η, 0), (η, 1), (s, 1)}; and this group is determined by llab(u).

For ease of presentation, we agree to set η := s, and often denote either of the above two groups of ll-pairs under the uniform notation {(l, 0), (l, 1), (l , 1)}, where l ∈ {η, }, with the ordering (l, 0) > (l, 1) > (l , 1).

We shall construct a run r of A Q on G that will be uniquely determined by the following maximal priority condition:

(MP): at any node v on G, r(v) is the maximal ll-pair ( l , x) for the ordering > in the group {(l, 0), (l, 1), (l , 1)} determined by llab(v), such that A Q contains a transition rule of the form (r(u), llab(v)) → ( l , x), for every parent u of v.

Such a run will assign a label with boolean component 1 only to the nodes corresponding to those of the minimal sub-trdag t containing the root of t and all the answers to Q on t.

Re-labeling of D t by the Runs of A Q

We first consider a non-sibling basic query Q on a given document t, and a given run r of the automaton A Q on the D t ; at the end of the run, the nodes on D t will get re-labeled with new ll-pairs, computed as below for every u ∈ N odes(D t ): lab r (u) = (s, 1) iff r(u) ∈ {(s, 1), ( , 1)}, lab r (u) = (η, 1) iff r(u) ∈ {(η, 1), ( , 1)}, lab r (u) = (η, 0) iff r(u) ∈ {(η, 0), ( , 0)}. The rlag obtained in this manner from D t , following the run r and the associated re-labeling function lab r , will be denoted as r(D t ).

For a basic query Q over a sibling axis, the situation is a little more complex, because several different nodes on one chibling of L t can have the same name (non-terminal), or several different chiblings can have nodes named by the same non-terminal, or both. Thus, to any node of D t , named with a non-terminal A, will correspond in general a set of ll-pairs, assigned by the various runs of A Q to the A-named nodes on the various chiblings of L t . We therefore proceed as follows: for every complete set r of runs of A Q , formed of one run r F on each chibling F , we will define r(D t ) as the re-labeled rlag derived from D t , under r. With that purpose we associate to r and any u ∈ N odes(D t ), a set of ll-pairs:

ll b r (u) = rF ∈ b r {r F (v) | v ∈ N odes(F ), and name(v) = name(u)}.
We then derive, at each node of D t a unique ll-pair in conformity with the semantics of our approach, by using the following function:

λ b r (u) = s ⇐⇒ ll b r (u) ∩ {(s, 1), ( ,
1)} = ∅, λ b r (u) = η ⇐⇒ ll b r (u) ∩ {(s, 1), ( , 1)
} = ∅. From D t and this function λ b r , we next derive an rlag λ b r (D t ) by re-labeling each node u on D t with the pair (λ b r (u), -). And finally we define r(D t ) as the rlag obtained from λ b r (D t ), by running on it the automaton for the basic nonsibling query //*[self::s], as indicated at the beginning of this subsection. In practical terms, such a run amounts in essence to setting, as the second component of label(u) at any node u, the boolean 1 iff u is on a path to some node with llab s, and 0 otherwise. All these details are illustrated with an example in the following subsection.

The Automata

We first present the automata for the basic queries //*[self::σ] and for //*[following-sibling::σ], and give an illustrative example using the former for σ = s, and the latter for σ = b. The automata for the other basic queries are given after the example.

• Automata: for //*[self::σ] and for //*[following-sibling::σ] on the trdag t of Figure 3. We first use the automaton for the basic query //*[following-sibling::σ] with σ = b, and then the automaton for //*[self::σ] with σ = s. The sub-trdag of t, formed of nodes corresponding to those of r(D t ) with labels having boolean component 1, contains all the answers to Q on t. • Automaton for the query //*[parent::σ] A few words on some of the automata by way of explanation. First, the reason why the automaton for self does not have the states ( , 0), ( , 1), (s, 1): for ( , 0), ( , 1), by the semantics of subsection 4.1 we must have x = σ, where x is the name of the current node on t, but then the query //*[self::σ] should select the current node, so one cannot be at such a state; as for (s, 1), the reasoning is just the opposite. Next, the reason why the automaton for descendant does not have the states (η, 1), ( , 1): if the semantics attribute one of these pairs to any node u, that would mean the node u has a selected descendant u ; which means that u has some σ-descendant node, which would then be a σ-descendant for u too, so Q should select u.

σ init η , 1 ' T, 1 =σ γ =σ γ =σ γ =σ γ =σ γ =σ γ =σ γ η , 0 init η , 0 s, 1 T, 0 ' T, 1 = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ σ σ σ
s 2 A 3 A 5 4 A ) ( ( , ) ( , ) , ) (η A 1 ) ( , η 1 1 s s 1 , 0 s 1 A 1 A 3 A 2 A 5 4 A ) ( , _ η ( , _ ) s ( , _ ) s , ) _ (η , ) _ (s D t ) λ r ( : ( , ) η 1 , ) η 0 ( A 1 A 3 A 2 A 5 4 A T ',1) ( T ',1) ( T ',
A 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( A 1 ) _ f ( , s, ( )
1 η, ( ) 0 s, ( ) 1
T, ( ) 0
, ) η 0 ( T ',1) ( r 3 r 1 0 r , , o nD t : A 2 (c, _ ) s, ( )
1 η, ( ) 0 T, ( ) 0 s, ( )
1 A 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( T ',1) ( , ) η 0 ( A 1 ) _ f ( ,
σ init T, 1 s, 1 η , 0 T, 0 = ⁄ γ σ = ⁄ γ σ η , 1 ' T, 1 = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄
T, 0 T, 1 ' T, 1 init η , 1 η , 0 = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄
σ init η , 1 T, 1 = ⁄ γ σ ' T, 1 s, 1 = ⁄ γ σ = ⁄ γ σ T, 0 = ⁄ γ σ η , 0 = ⁄ γ σ = ⁄ γ σ = ⁄

Maximal Priority Runs of Basic Query Automata

Note that the following properties, required by our semantics of subsection 4.1, hold on the automata A Q constructed above, for any basic Core XPath query Q = //*[axis::σ]: i) There are no transitions from any state with boolean component 0 to a state with boolean component 1;

ii) The σ-transitions have all their target states in {( , 0), ( , 1), ( , 1)}; and for any γ = σ, the target states of γ-transitions are all in {(η, 0), (η, 1), (s, 1)}.

Theorem 1 Let Q be any basic Core XPath query, t any given trdag, and let G denote either the rlag D t , or any given chibling F of L t . Assume given a labeling function L from N odes(G) into the set of ll-pairs, which is correct with respect to Q, i.e., in conformity with the semantics of subsection 4.1. Then there is a run r of the automaton A Q on G, such that : i) r is compatible with L; i.e., r(u) = L(u) for every node u on G; ii) r satisfies the maximal priority condition (MP) of subsection 4.1.

Proof. We first construct, by induction, a 'complete' run (i.e., defined at all the nodes of G) satisfying property i). For that, we shall employ reasonings that will be specific to the axis of the basic query Q. We give here the details only for the axis parent; they are similar for the other axes. Q = //*[parent::σ]: (The axis considered is non-sibling so G = D t here.) At the root u node of D t , we set r(u) = L(u); we have to show that there is a transition rule in A Q of the form (init, llab(u)) → L(u). Obviously, for the axis parent, the root node u cannot correspond to a node on t selected by Q, so the only ll-pairs possible for L(u) are (l, 0), (l, 1), with l ∈ {η, }; for each of these choices, we do have a transition rule of the needed form, on A Q . Consider then a node v on D t such that, at each of its ancestor nodes u on D t , the part of the run r of A Q has been constructed such that r(u) = L(u); assume that the run cannot be extended at the node by setting r(v) = L(v). This means that there exists a parent node w of v, such that ( L(w), llab(v)) → L(v) is not a transition rule of A Q ; we shall then derive a contradiction. We only have to consider the cases where the boolean component of L(w) is greater than or equal to that of L(v). The possible couples L(w), L(v) are then respectively: L(w) :

( , 0) | ( , 1) | ( , 1) | ( , 1) | ( , 1) L(v) : (η, 0) | ( , 1) | (η, 1) | ( , 1) | (η, 1)
In all cases, we have llab(w) = σ because of the semantics, so the node (on t corresponding to the node) v has a σ-parent, so must be selected; thus the above choices for L(v) are not in conformity with the semantics; contradiction.

We now prove that the complete run r thus constructed, satisfies property ii). For this part of the proof, the reasoning does not need to be specific for each Q; so, write Q more generally, as //*[axis::σ] for some given σ. Suppose the run r does not satisfy the maximal priority condition at some node v on G; assume, for instance, that the run r made the choice, say of the ll-pair (l, 1), although the maximal labeling of the node v, in a manner compatible with the ll-pairs of all its parents, was the ll-pair (l, 0). Since L is assumed correct, and r is compatible with L, the maximal possible labeling (l, 0) would mean that the node (on t corresponding to the node) v has no descendant selected by Q; whereas, the choice that r is assumed to have made at v, namely the ll-pair (l, 1), has the opposite semantics whether or not llab(v) = σ; in other words, the labeling L would not be correct with respect to Q; contradiction. The other possibilities for the 'bad' labelings under r also get eliminated in a similar manner.

Theorem 2 Let Q, t, D t , F , G be as above. Let r be a (complete) run of the automaton A Q on G, which satisfies the maximal priority condition (MP) of subsection 4.1. Then the labeling function L on N odes(G), defined as L(u) = r(u) for any node u, is correct with respect to the semantics of subsection 4.1.

Proof. Let us suppose that the labeling L deduced from r is not correct with respect to Q; we shall then derive a contradiction. The reasoning will be by case analysis, which will be specific to the axis of the basic query Q considered. We give the details here for Q = //*[descendant::σ]. The axis is non-sibling, so we have G = D t here. The sets N odes(t), Nodes(D t ) are in a natural bijection, so for any node u on D t we shall also denote by u the corresponding node on t, in our reasonings below.

We saw that the automaton A Q for the descendant axis does not have the states (η, 1), ( , 1). Consider then a node u on D t such that: for all ancestor nodes w of u, the llabel r(w) is in conformity with the semantics, but the ll-pair r(u) is not in conformity. Now, A Q has only 5 states: (init), ( , 1), (s, 1), ( , 0), (η, 0), of which only the last four can llabel the nodes. So the possible 'bad' choices that r is assumed to have made at our node u, are as follows:

(a) r(u) = ( , 1), but the node u is not an answer to the query Q. Here name(u) must be σ, so the choice of r ought to have been ( , 0); (b) r(u) = (s, 1), but the node u is not an answer to the query Q. Here name(u) = σ, so the choice of r ought to have been (η, 0);

(c) r(u) = (η, 0), but the node u is an answer to the query Q. Here name(u) = σ, so the choice of r ought to have been (s, 1);

(d) r(u) = ( , 0), but the node u is an answer to the query Q. Here name(u) must be σ, so the choice of r ought to have been ( , 1).

In all the four cases, we have to show: i) that the "ought-to-have-been" choice ll-pair is reachable from all the parent nodes of u;

ii) and that, with such a new and 'correct' choice made at u, r can be completed from u, into a run on the entire dag D t . The reasoning will be similar for cases (a), (b), and for the cases (c), (d).

Here are the details for case (a): That u is not an answer to Q means that u has no σ-descendant node, so for all nodes v below u on D t , we have llab(v) = σ. Therefore, assertions i) and ii) above follow from the following observations on the automaton for Q= //*[descendant::σ]: i) if r could reach the state ( , 1) at node u (via a σ-transition) from any parent node of u, then ( , 0) is also reachable thus at u, from any of them;

ii) if, from the state ( , 1), r could reach all the nodes on D t below u (with state (η, 0)), via transitions over γ = σ, then it can do exactly the same now, with the 'correct' choice ll-pair ( , 0) at u.

As for case (c): Node u is an answer to Q here, so u has a σ-descendant; let v be a σ-node below u on D t ; the ll-pair r(v) that r assigns to v must then be either ( , 1) or ( , 0); this implies that r passed from the state (η, 0) -supposedly assigned by r to u -to ( , 1) or ( , 0) somewhere between u and v; which is impossible, as is easily seen on the automaton A Q for the axis descendant considered. The reasoning for case (d) is even easier: from state ( , 0), no state with an outgoing σ-transition is reachable.

Evaluating Composite Queries

A composite query is a query in standard form, but is not basic. We propose to evaluate such a query incrementally. For this, it suffices to consider queries that are of the form //*[A::x conn A'::x ], where conn ∈ {and, or}, or of the form //*[A 1 ::*[A 2 ::σ]]. For those of the former type, we observe first that the components in a disjunction (resp. conjunction) under a '*' can be evaluated separately. Indeed, the answer for Q = //*[A::x conn A'::x ] can be obtained as union (resp. intersection) of the answers for the two "component" queries //*[A::x], and //*[A'::x ], when conn is an or (resp. an and). We apply the method described earlier, separately for Q 1 = //*[A::x] and for Q 2 = //*[A'::x ], thus getting two respective evaluating runs r 1 , r 2 . Any node u of the dag D t will then be re-labeled, by the composite query Q, with ll-pairs computed by a function AND when conn = and (resp. OR when conn = or), in conformity with the semantics presented in the Section 4.1: We next consider the queries of the form Q = //*[A 1 ::*[A 2 ::σ]], with imbricated predicates. For their evaluation, we first consider a maximal priority run evaluating r 2 (resp. a set of runs r 2 ) of the automaton associated to the inner query //*[A 2 ::σ], on D t (resp. the set of all chiblings of L t ). This run (resp. set of runs) will output the rlag r 2 (D t ) (resp. r 2 (D t )), as described in Section 4.2. Evaluating the imbricated query Q on the dag t is then done by running the automaton for the basic outer query //*[A 1 ::s] on r 2 (D t ) (resp. r 2 (D t )).

AN D(u) = (s, 1) iff r 1 (u) = (l , 1) = r 2 (u); AN D(u) = (η, 0) iff r 1 (u) = (l, 0) or r 2 (u) = (l, 0); AN D(u) = (η, 1) otherwise. OR(u) = (s, 1) iff r 1 (u) = (l , 1) or r 2 (u) = (l , 1); OR(u) = (η, 0) iff r 1 (u) = (l, 0) = r 2 (u); OR(u) = (η, 1) otherwise.
Finally, the answer for a query of the type Q = //*[child::x[position()= k]], is the subset of the nodes answering //*[child::x], which correspond to a k-th node on some chibling.

//*[parent : : a] 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( A 1 ) _ f ( , η,0 ( ) η ( ,1) T, 1 ( ) ' T, 1 ( ) ' η ( ,1)
//*[self : : b] and(D t )

A 1 ) (η,1

A 2 ( , )

0 η A 3 ( ,1 η ) 4 A , ) ( 0 η A 5 , ) ( 1 s A 2 (c, _ ) ( , _ ) a A 3 b, ) _ ( 4 A A 5 b, ) _ ( A 1 ) _ f ( , η ( ,1) η,0 ( ) T, ( 1) s,1 ( ) η,0 ( )
A Fig. 5.

Deriving the Answer on the Tree-Equivalent

Given a Core XPath query Q and its answer set on a trdag t, we show here how to derive the answer for the same query Q on the tree-equivalent t of t; this is of importance, since the "standard model" for an XML document (even when given in a compressed form) is generally considered as the tree representation of the document. We observe, to start with, that the answer set for Q on t is in general a superset of the answer set for Q on the tree-equivalent t. This can be so for the following two reasons:

(i) If a certain node u on t is selected by Q, not all of the nodes u on t, that are 'lifts' of u under the compression map c on N odes( t), may answer the query Q on the tree t, even when Q is a basic query. For instance, consider the basic query //*[parent::a]; on the fully compressed tdag f (a(c), b(c)), the (unique) node named c is an answer; it has two c-named nodes as lifts on the tree-equivalent t, of which only one is an answer for the query.

(ii) A node u on a trdag t may answer a composite query Q, but none among the lifts of u on t may answer the same query Q on the tree t. For instance, the unique c-named node on the compressed tdag f (a(c), b(c)) answers the query //*[parent::a and parent::b], but there is no node on the tree-equivalent answering this query.

Actually, such situations arise only for queries involving the upward axes parent, ancestor, which define relations that are less trivial on trdags than on trees. We can formulate this observation more precisely, as follows: Lemma 1. Let A be one of the axes self, child, descendent, Q the basic query //*[A::x], t any given trdag, t its tree-equivalent, u any given node on t, and u ∈ c -1 (u) any node lift of u on t. Then:

• wrt the maximal priority runs of the automaton for the axis A, respectively on D t and D t, the nodes u on t, and u on t, get labeled by the same ll-pair;

• in particular, the node u answers Q on t if and only if the node u answers the same query Q on the tree t.

Proof. Follows by observing that the semantics of Section 4.1 have been defined in a manner which is top-down, and that the compression map c : N odes( t) → N odes(t) maps the set N odes( t| u ), of nodes below u on t, onto the set of nodes of the sub-trdag t| u .

The above lemma is a first step towards the objective of this section. As a second step, we propose to distinguish, on the automata for the two basic queries //*[parent::σ], //*[ancestor::σ], two special types of transitions, besides the usual ones.

(i) Type forget: The transitions that will not be firable on a tree; such transitions will be represented by dotted arcs on the automaton.

The transitions concerned are the ones from (η, 1) to ( , 1) and to (s, 1) on the automata for parent and descendant, as well as the one from (s, 1) to ( , 1) on the parent automaton. A word of explanation might help here: for instance, in order that the transition from state (η, 1) to state ( , 1) be firable on the parent automaton, we have to reach a node corresponding to a σ-named node on the trdag, which must then also have as (unique) parent on the tree -i.e., the node from which the transition is to be fired-a σ-named node; this parent node cannot correspond then to a node labeled with (η, 1). The reasoning is similar, although not identical, for the ancestor automaton.

In recovering the answer for a given (basic) query Q on the tree equivalent t, the role played by the dotted arc transitions is as follows: if the current node on t corresponds to a position α on D t that is reached (by the automaton for Q) via a dotted transition, then the position α does not answer Q on t. The idea then is that such a position α can then be "forgotten" along a given run, while looking for nodes answering Q. Nevertheless, such a position cannot be forgotten forever, in general: consider for instance, the basic query //*[ancestor::σ] on a trdag t containing (among others) two nodes u, v such that v is a child of u, u with a σ-ancestor, and the name at u is σ; then the run of the automaton for this query must attribute the label ( , 1) to u, and (s, 1) to v; and in such a case, all the positions of v that extend the positions of u on t have to be kept as answers, even if some of the transitions of the automaton have been "dotted" on the way from the root of D t to the parent node u. This remark leads us to distinguish a second type of transitions:

(ii) Type restore: Transitions that restore all the positions currently visited at a node, including the ones containing prefixes "forgotten" earlier under the given run; such transitions will be represented by thick arcs on the automaton.

The automata thus revised for the two upward axes, are as follows:

• Automaton for the query //*[parent::σ] -revised Our next step towards the objective of this section is to complete a maximal priority run r of the automaton for Q, by associating to any node u on D t , a partition of P os t (u) by two subsets, respectively denoted as L r u and L r u : if r(u) is (s, 1) or ( , 1) then the set L r u will contain all the positions at the node u that answer Q on the tree equivalent t of t. The rules for computing these sets will be given presently. Two observations are essential in building these rules properly, and optimally:

σ init T, 1 η , 0 T, 0 = ⁄ γ σ = ⁄ γ σ η , 1 = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ = ⁄ γ σ s, 1 = ⁄ γ σ = ⁄ γ σ ' T, 1 = ⁄ γ σ = ⁄
(i) The set of positions at any node u, on the given trdag t, can be computed symbolically and dynamically, under any top-down traversal of D t ; suffices to attach distinct "position symbols" X, X , • • • to the various arcs on D t ; if X is such a symbol attached to an arc on D t going from a non-terminal A of the grammar L t to a non-terminal B of L t , then X is meant to stand for the set of integers {j 1 , • • • , j m }, giving the positions where B appears on the rhs of the unique A-production of L t . Thus, for any node u on t, any of its positions is symbolically represented by a word over the position symbols.

(ii) The basic query considered Q can be the outer query in a non basic imbricated query Q 0 . Here, the partition of P os t (u) -say as L u ∪ L u -that results from the inner query Q immediately below Q in Q 0 , should be taken into account. For that purpose, note that at the end of the run r for the inner query Q , every node u of D t gets re-labeled as lab r (u), this latter being either an (s, -), or an (η, -), cf. Section 4.2; the basic outer query Q is then of the form //*[A::s] (cf. Section 6). Accounting for the partition L u ∪ L u of P os t (u) arising from the inner run r , is then done as follows:

• lab r (u) is (η, -): associate to u one llabel-position-set pair η, P os t (u) ;

• lab r (u) is (s, -): associate to u two llabel-position-set pairs: s, L u , η, L u . (Note: such a vision does not amount to unfolding the trdag into its treeequivalent; indeed, the number transitions consider between any two nodes of D t , for the automaton of the outer query, is at most 4.)

The rules for computing the position sets L r u and L r u , at any given node u on t, under a top-down traversal of t by a run r of the automaton for the current query, are then formulated as follows, where w is any parent node of u on t, α is a word over the position symbols standing for a position of w on t, X is the position symbol on the arc from w to u on D t ; all the position sets are seen here as unary predicates: Each rule is to be applied for the type of transition specified, used by the run for moving from w to u. (The semantics of these rules follow the considerations developed above.)

L r w (α) usual,forget -----→ L r u (α.X) L r w (α) restore -----→ L r u (α.X) L r w (α) usual,restore -----→ L r u (α.X) L r w (α) forget -----→ L r u (α.X)
We now consider the issue of retrieving the answer on the tree-equivalent of t, from the answer on t, for a query Q which is a conjunction or disjunction of two sub-queries Q 1 , Q 2 . In addition to the functions AN D and OR of Section 6, we need to formulate the conditions for computing the partitions of position sets at every node on t. Let r 1 , r 2 denote the runs evaluating the two respective sub-queries on t; for any node u on t, let us denote by

L AN D u , L AN D u (resp. by L OR u , L OR u )
, the partition of P os t (u) after the evaluation of

Q 1 ∧ Q 2 (resp. Q 1 ∨ Q 2 )
; these partitions are to be computed as indicated by the self-evident conditions below (notation same as above): , and its answer consists of all the nodes having an ancestor b with parent c. The aim here is to obtain the 'same' answer for Q on t and on its tree-equivalent t presented in the middle of Figure 6. To find such an answer, it is necessary to use the revised automata for the parent and ancestor axes. We will illustrate the evaluation of Q on the rlag D t presented to the right of Figure 6. Note that each node u of D t is represented by the name of corresponding node on t, and the set of positions of the nodes on t that are lifts of this node; so we set:

L AN D u (α.X) = L r1 u (α.X) ∩ L r2 u (α.X) L AN D u (α.X) = L r1 u (α.X) ∪ L r2 u (α.X) L OR u (
X = {1, 3}, Y = {2}, Z = {1}, L = {2}, T = {1}, K = {2}.
First, look at Figure 7 where we have presented the evaluation of Q using the non-revised automata. We obtain then an answer on t selecting nodes a and g (which are the nodes having an ancestor b with parent c on t); but, if we unfold this answer, we obtain the tree with as selected nodes: a at positions 11, 211, 31, and g at positions 12, 212, 22, 32. Obviously this set of nodes is not the answer for Q on t: indeed, only the nodes a at position 211 and g at position 212 have ancestor b (position 21) with parent c (position 2) on the tree t.

The Figure 8 presents the evaluation of Q on D t using the revised automata. First we evaluate in parallel the inner queries //*[self::b] and //*[parent::c]. Now, to any node u on D t , the run r of the revised automaton associate not only a state, but also the sets of positions L r u and L r u , computed using the rules given Tree equivalent of answer on t on t on tree eqivalent of t Run of revised automaton for Fig. 10. Evaluation of Q on t using the revised automaton this explains that their method works indifferently on the unfolded tree t, or on the dag t (cf. Algorithm 4.1, and Theorem 10, [START_REF] Frick | Query Evaluation of Compressed Trees[END_REF]). The method we have presented is more general, in that it returns all the positions on t (or t) answering the query.

f ε η, ) ( 1 ε { } η, ) ( 1 η, ) ( 1 , ) 1 ( T , ) 1 s ( , ) 1 s

Conclusion

Our concern in this paper has been two-fold. The first part addressed the problem of running any bottom-up (unranked) tree automaton indifferently on a tree or on any of the dags obtained from the tree by full or partial compression; this gave rise to the notions of Tree/Dags (trdags) and of Tree/Dag automata. The second part of the paper addressed the issue of retrieving information from a trdag representing an XML document possibly given in a compressed form. (Note: Information retrieval from compressed structures, without having to uncompress them, is a field of active research; cf. e.g., [START_REF] Rytter | Compressed and fully compressed pattern matching in one and two dimensions[END_REF][START_REF] Lohrey | Word problems and membership problems on compressed words[END_REF].) Limiting our concern here to the evaluation of queries formulated in terms of XPath axes, and more precisely to positive Core XPath queries, we have presented a method for evaluating them on any trdag t, without having to uncompress t, by breaking up the given query into sub-queries of a basic type; with each basic query, an automaton is associated such that an unambiguous maximal priority run of this automaton can evaluate the query. An algorithm constructing the maximal priority runs is given in Appendix II; it has just been implemented. It is of complexity O(n 3 ) on any trdag t, where n is the number of nodes of t; it reduces to O(n 2 ) if t is a tree, the relation P arents becoming trivial. (Note: our method of evaluation a priori gives the answers for the given query Q on the given trdag t, but we have shown how one can derive the answer set for Q on the tree-equivalent of t.)

An advantage of the approach presented in this paper seems to be that the basic sub-queries "composing" a given query can be evaluated in parallel, in several cases; a detailed analysis of this issue could be a direction for future work. We also expect to be able to extend our approach to the evaluation of more general XPath queries, such as those involving the data values, by adapting its underlying mechanism based on labeling.

FullyFig. 1 .

 1 Fig. 1. tree, tdag, and trdag

Fig. 2 .

 2 Fig. 2.A bottom-up accepting run of the TDA of Example 1 on a trdag, and the same seen on its tree equivalent.

Fig. 3 .

 3 Fig. 3. trdag t, associated rlag Dt, and chiblings of Lt

Definition 5

 5 Given a context node u on a trdag t, and b ∈ Σ: i) [parent::b] evaluates to true at u, if and only if there exists a b-named node in P arents(u); ii) [ancestor::b] evaluates to true at u, iff either [parent::b] evaluates to true at u, or there exists a node v ∈ P arents(u) such that [ancestor::b] evaluates to true at v; iii) [following-sibling::b] evaluates to true at u, iff there exists a b-named node u , and a node v on t such that γ(v) is of the form ...u...u ...; iv) [preceding-sibling::b] evaluates to true at u, iff there exists a b-named node u , and a node v on t such that γ(v) is of the form ...u ...u....

  ::= self | child | descendant | parent | ancestor | preceding-sibling | following-sibling S ::= A::σ | position()= i | S and S | S or S | Root E ::= A:: * [S] | E[E] Q std ::= //* | //*[S] | //*[E]

  Q 1 and Q 2 are the same. Any positive Core XPath query Q can can be translated into an equivalent one in standard form; e.g., /c[following-sibling::g]/d is equivalent to //*[self::d and parent::*[Root and self::c [following-sibling::g]]] in standard form. An inductive procedure performing such a translation in the general case (of linear complexity w.r.t. the number of location steps in Q can ) is given in Appendix I. The following proposition results from Definition 5. Proposition 3 (1) For any set of nodes X on a trdag t, and any axis A, we have: A(X) = x∈X, α∈pos t (x) α = i 1 ...i k {/child:: * [position()= i 1 ]/.../child:: * [position()= i k ]/A:: * } (2) For any trdag t, and any node with name b on t, we have: (i) //*[preceding::b] = u {descendant-or-self(following-sibling( //*[self::u and (descendant::b or self::b)] ))} (ii) //*[following::b] = u {descendant-or-self(preceding-sibling( //*[self::u and (descendant::b or self::b)] ))}

Figure 4

 4 Figure 4 below illustrates the evaluation of Q = //*[following-sibling::b], on the trdag t of Figure 3. We first use the automaton for the basic query

  Fig. 4.

••

  Automaton for the query //*[ancestor::σ] Automaton for the query //*[child::σ] σ , 1

•

  Automaton for the query //*[preceding-sibling::σ]

•

  Automaton for the query //*[descendant::σ]

Figure 5

 5 Figure 5 below illustrates the above reasoning, for the evaluation of the composite query Q = //*[self::b and parent::a], on the trdag t of Figure 3:We next consider the queries of the form Q = //*[A 1 ::*[A 2 ::σ]], with imbricated predicates. For their evaluation, we first consider a maximal priority run evaluating r 2 (resp. a set of runs r 2 ) of the automaton associated to the inner query //*[A 2 ::σ], on D t (resp. the set of all chiblings of L t ). This run (resp. set of runs) will output the rlag r 2 (D t ) (resp. r 2 (D t )), as described in Section 4.2. Evaluating the imbricated query Q on the dag t is then done by running the automaton for the basic outer query //*[A 1 ::s] on r 2 (D t ) (resp. r 2 (D t )).Finally, the answer for a query of the type Q = //*[child::x[position()= k]], is the subset of the nodes answering //*[child::x], which correspond to a k-th node on some chibling.

•

  Automaton for the query //*[ancestor::σ] -revised σ

Fig. 6 .

 6 Fig. 6. trdag t,tree-equivalent t, and corresponding rlag Dt

Example 2 .

 2 α.X) = L r1 u (α.X) ∪ L r2 u (α.X) L OR u (α.X) = L r1 u (α.X) ∩ L r2 u (α.X)We evaluate the query Q =//*[ancestor::b [parent::c]] on the trdag t presented to the left of Figure 6. The standard form of this query is Q =//*[ancestor::*[self::b and parent::c]]

(Fig. 8 .

 8 Fig. 8. Evaluation of Q on t using the revised automata

Fig. 9 .

 9 Fig. 9. Evaluation of Q on t using non-revised automaton

above (note that if the axis is different from parent and ancestor we have L r u = P os t (u) and L r u = ∅). Next, using function AN D, we find the answer for conjunction, and we associate to every node u the corresponding sets L AN D u and L AN D u . Then, to every node with label s we associate two labels: s with set L AN D u , and η with set L AN D u . This way we have obtained a relabeled rlag lab AN D (D t ), and on this rlag we evaluate the outer query //*[ancestor::s]. The final answer consists of the set L r u , containing the nodes u such that r(u) = s. Using the revised automata, we thus obtain the answer for Q on t restricted to a set of positions; this corresponds exactly to the answer set for Q on the tree-equivalent t of t. Example 3. We evaluate here the query Q =//*[parent::a] on the fully compressed trdag t presented to the left of Figure 9. The aim here is to clarify the meaning of transitions restore. As before, the Figure 9 shows that the runs of the non-revised automaton do not give the same answers for Q on trdag t and on its tree-equivalent.

Figure 10 presents the evaluation of Q on this t by using the revised automaton. This time the maximal priority run has associated to the node a (having parent a), the selecting state ( , 1) and the sets L = {11} and L = {21}. This means that only position 11 is selected; indeed, the position 21 cannot be selected because its parent node at the position 2 doesn't have the symbol a. At the next step, the run has followed the restore transition from ( , 1) to (s, 1). (Note: the run of the automaton for // * [parent::a] can associate the states ( , 1) and ( , 1) only to the nodes with symbol a, so every child position of such nodes has to be selected. For this reason, every outgoing transition from ( , 1) and ( , 1) is of the type restore.) Using this transition, we select all the positions at the leaf c. Remark 3. The algorithm given in [START_REF] Frick | Query Evaluation of Compressed Trees[END_REF], for the evaluation of (Core) XPath queries on a compressed dag t, actually takes a given position on t as a parameter;

Appendix I: From Canonical Forms to Standard Forms

We stick to the notations of Section 3.1. Given any canonical XPath expression Q can , we compute, inductively, an equivalent standard XPath expression denoted as Std(Q can ); as earlier, conn stands for either of the boolean connectives and, or.

To start with, we define: We also define, for every basic axis relation, an inverse relation, as follows: Case of length n>1:

This translation procedure is of complexity linear with respect to the total number of location steps (i.e. of the form axis::σ) that appear in Q.

Appendix II: Constructing the Maximal Priority Run

Given a trdag t, and a basic non-sibling query Q we give here the algorithm constructing the maximal priority run of the automaton A Q on D t . (It is trivial for the sibling queries.) Let D t be the dependency rlag of L t and n the number of its nodes. We construct then a directed acyclic graph G = (V, E), representing the maximal priority run of A Q on D t . The vertices of G will be of the form

where A i is a node on D t (i.e., a non-terminal of L t ), and α is an ll-pair, that will eventually satisfy r(A i ) = α under the maximal priority run r (on D t ) of the automaton A Q . The algorithm can be divided into four steps as described below, where we denote by llab(A i ) the first component of the label of the A i -named node on D t . The overall cost of the algorithm is O(m), where m is the number of edges of the rlag D t . In particular, if t is a tree D t is isomorphic to t, so our algorithm will then be linear on the number of nodes of the tree t; thus, the complexity of our approach compares well with that of other query evaluation approaches.

For uniformity of presentation, we shall add a 'fictive root' node A 0 to D t , and an edge (A 0 , A 1 ) joining it to the real root node A 1 on D t . By state, we shall mean any ll-pair corresponding to a state of the automaton A Q ; the greek letters α, β, γ, . . . will designate such ll-pairs.

Step 1): The initial form of the graph G:

i) The set of "potential" edges: Add an edge (A i,α , A j,β ) in G iff there is an edge (A i , A j ) on D t ; initialize, by marking all the edges as incorrect, with the boolean label 0.

ii) The set of "A Q -compatible" edges: Mark an edge (A i,α , A j,β ) with boolean label 1 iff the automaton A Q has a transition rule (α, llab(A j )) → β.

Step 2): Mark (a first list of) edges as incorrect with 0, under a top-down traversal of the graph G:

For any vertex A j,β : -if there is an i ∈ {1, . . . , n}, i < j, such that the 3 potential edges (A i,α , A j,β ) are all marked with 0 (for the three possible α ∈ States determined by llab(A i )), then mark all the edges incoming and outgoing at A j,β , with 0.

-if there is a k ∈ {1, . . . , n}, k > j, such that the 3 potential edges (A j,β , A k,γ ) are all marked with 0 (for the three possible γ ∈ States determined by llab(A k )), then mark all the edges incoming and outgoing at A j,β , with 0.

Step 3): Complete the marking of incorrect edges with 0, by repeating the operation of Step 2) by back-propagation (when necessary), under a bottom-up traversal of the graph G.

Step 4): Deduce the maximal priority run r:

The maximal priority run r is constructed inductively, as follows. We first set r(A 0 ) = init; for any j, 1 ≤ j ≤ n, assume having defined r(A i ) for all 0 ≤ i < j; then define r(A j ) = β where β is the >-maximal priority state determined by llab(A j ) such that:

-for every 0 ≤ i < j for which D t has an edge (A i , A j ), there is a 1-marked edge (A i,r(Ai) , A j,β ) on G.

The algorithm works with the following INPUT:

/** Here (-, A j,β ) and (A j,β , -) respectively stand for any incoming and outgoing edge at A j,β **/ } /* 3: Bottom-Up pruning */ For j from n downto 0 do For all β ∈ States(llab

That the complexity of this algorithm is O(m) is due to the following facts. The construction of Step 1 is obviously O(m); as for the other steps, it suffices to note that:

A 5 η ( ,1) Figure 13 shows, to the left, the rlag obtained by re-labeling D t with the run of the automaton for the query //*[descendant::s]; and to the right, the (minimal) sub-rlag of D t formed of nodes marked now by ll-pairs with boolean component 1, and the corresponding answer for the query Q on the document t. This final sub-rlag of D t is obtained by cutting out the nodes where the ll-pairs attached have boolean component 0.

s,1 The two rlags D t , D t of Figure 15 are then obtained by applying the relabeling functions respectively lab r and λ r (of subsection 4.2) for these respective runs. The rlag D t to the right is obtained by the run of automaton for // * [self::s] on D t . The Figure 16 presents the final answer for our query obtained by applying the function OR from section 6.