Compact Representation
for Answer Setsof n-ary Regular Queries

byKazuhiro Inaba (National Institute of Informatics, Japan)and Hauro Hosoya (The University of Tokyo)

CIAA 2009, Sydney

BACKGROUND

N-ary Query over Trees• … is a function that
– Takes a tree t as an input, and– Returns some set of n-tuples of nodes of t
• Examples:– 1-ary: “select the leftmost leaf node”– 2-ary: “select all pairs (x,y) s.t. x is takenfrom the left subtree of the root,and y is from the right”– 0-ary: “is the number of leaves odd?”

BACKGROUND

N-ary Regular Queries over Trees• Query definable by a tree automaton• Regular– iff definable by Monadic 2nd-Order Logic– iff definable by Modal μ-Calculus– iff definable by Monadic Datalog– iff definable by Boolean Attribute Grammar–…

BACKGROUND

Efficiency of Regular Queries• Given a query q (represnted by anautomaton A), and an input tree t,
we can compute q(t) in…

• O(|A|・(|t|+|q(t)|)) time
[Flum & Frick & Grohe 2002]– (In some sense) optimal

“Optimal”, but…
• O( |A |・( |t| +Still Big|q(t)| ) )– ～|t|n for n-ary queries in the worst case

• In some applications, we do not need

the concrete list of all the answers– At least, don’t need to list up them all at
the same timeInputTree

size: INheight: H

Set ofOutput Tuples
Run Query

O( IN + OUT)

size: OUT∈O(INn)Today’s Topic“SRED”
Data structuresize: O(min(IN,OUT))

isMember: O(H)
Get-Size: O(min(I,O))“Projection”: O(H・α)“Selection”: O(H)Outline① Introduction– N-ary Regular Queries & Their Complexity② Application– When Do We Need Compact Representation?
③ Algorithm– Query Algorithm (Suitable for “SRED” Repr.)– “SRED” Data Structure④ Conclusion

APPLICATION(IN XML TRANSLATION)

“Relative” Queries in XML<list>{foreach x s.t. φ(x):<item>{x}</item><sublist>{foreach y s.t. ψ(x,y):<item>{y}</item>}</sublist>}</list>• Select y relative to x
– In many cases, # of y for each x is constant. E.g.,• “select the child labeled <name>”, “select next <h2>”

Two Evaluation Stategies<list>{foreach x s.t. φ(x):<item>{x}</item><sublist>{foreach y s.t. ψ(x,y):<item>{y}</item>}</sublist>}</list>A := the answer set of
1-ary query {x | Φ(x)}for each x in A:
B := the answer set of
1-ary query {y | Ψ(x,y)}for each y in B:
print <item>y</item>

A := the answer set of
1-ary query {x | Φ(x)}C := the answer set of
2-ary query {(x,y) |Φ(x)&Ψ(x,y)}for each x in A:
B := {y | (x,y)∈C} = C[1:x]for each y in B:
print <item>y</item>;O(|t|2) timein “common” cases(= many x, constant y)O(|t|) timein “common” cases

Two Evaluation Stategies

A := the answer set of
1-ary query {x | Φ(x)}for each x in A:
B := the answer set of
1-ary query {y | Ψ(x,y)}for each y in B:
print <item>y</item>

A := the answer set of
1-ary query {x | Φ(x)}C := the answer set of
2-ary query {(x,y) |Φ(x)&Ψ(x,y)}for each x in A:
B := {y | (x,y)∈C} = C[1:x]for each y in B:
print <item>y</item>;O(|t|2) timein “common” cases(= many x, constant y)O(|t|) timein “common” cases

Two Evaluation Stategies
O(|t|2) timeO(|t|) spacein “worst” cases(= many x, many y)

A := the answer set of
1-ary query {x | Φ(x)}for each x in A:
B := the answer set of
1-ary query {y | Ψ(x,y)}for each y in B:
print <item>y</item>

O(|t|2) timeO(|t|2) spacein “worst” cases

A := the answer set of
1-ary query {x | Φ(x)}C := the answer set of
2-ary query {(x,y) |Φ(x)&Ψ(x,y)}for each x in A:
B := {y | (x,y)∈C} = C[1:x]for each y in B:
print <item>y</item>;O(|t|2) timein “common” cases(= many x, constant y)O(|t|) timein “common” cases

Two Evaluation Stategies
O(|t|2) timeO(|t|) spacein “worst” cases(= many x, many y)

A := the answer set ofIf query
We Use{x“SRED”
1-ary| Φ(x)}to Represent the Set C …!!

for each xO(|t|)
in A: time“common”
B :=intheanswer cases
set of1-aryquery {y | Ψ(x,y)}2O(|t|) time
spacefor eachy in O(|t|)
B:
in “worst” cases
print <item>y</item>

O(|t|2) timeO(|t|2) spacein “worst” cases

A := the answer set of
1-ary query {x | Φ(x)}C := the answer set of
2-ary query {(x,y) |Φ(x)&Ψ(x,y)}for each x in A:
B := {y | (x,y)∈C} = C[1:x]for each y in B:
print <item>y</item>;IMPLEMENTATIONOF REGULAR QUERIESUSING “SRED”

(Bottom-up Deterministic)

Tree Automaton(For simplicity, we limit our attention to binary trees)• A = (Σ0, Σ2, Q, F, δ)– Σ0 : finite set of leaf labels– Σ2 : finite set of internal-node labels– Q : finite set of states– δ : transition function(Σ0 ∪ Σ2×Q×Q)  Q– F ⊆ Q : accepting states

Example (0-ary): ODDLEAVES• Q = {q0, q1}, F={q1}q1• δ(L) = q1

• δ(B, q0, q0) = q0
• δ(B, q0, q1) = q1• δ(B, q1, q0) = q1

• δ(B, q1, q1) = q0

Bq1q0L

Bq1q1LL

Tree Automaton for Querying• For any n-ary regular query Φ on trees

over Σ0 ∪ Σ2,• There exists a BDTA AΦ on trees over
Σ0×Bn, Σ2×Bn (where B={0,1}) s.t.
– (v1,…,vn) ∈ Φ(t)–iff
– AΦ accepts the tree mark(t,v1,…,vn)• mark(t,…) = t with the i-th B component is
1 at vi and 0 at other nodes

Example (1-ary): LEFTMOSTB• Q = {q0, q1}, F={q1}L• δ(L0) = q0

L

• δ(L1) = q1q1

• δ(B0, q1, q0) = q1
• δ(otherwise) = q0

Bq0

B0

q1 L1

LB0

B0 q0

q0 L0

q0 L0

L0 q0

B0 q1

q1 L1

L0 q0

NA: Naïve n-ary Query Algorithm• For each tuple (v1,..,vn) ∈Node(t)n– Generate mark(t, v1, …, vn)– Run AΦ on it• If accepted, then (v1,…,vn) is one of the answer• Run AΦ on t O(|t|n) times = O(|t|n+1)

OA: One-Pass Algorithm• For each combination ofnode v, state q, and b1, …, bn ∈ B– Compute the set
rv (q, b1, …., bn) ⊆ (Node(t)∪{⊥})n s.t.
– (v1, …, vn) ∈ rv (q, b1, …., bn)
iff(∀i : “descendant vi of v is marked andbi=1” or “vi=⊥ and bi=0”) ⇒ “automaton
assigns q at node v”

Example (2-ary): LEFT&RIGHT• Q = {q0, q1, q2, q3, q4}, F={q3}• δ(L00) = δ(B10, q0, q0) = q0

BLBLL• δ(L10) = δ(B10, q0, q0) = q1
• δ(L01) = δ(B01, q0, q0) = q2
• δ(B00, q1, q2) = q3

• δ(B00, q0, qi) = δ(B00, qi, q0) = qi (for i=1,2)• δ(otherwise) = q4

δ(L00) = δ(B10, q0, q0) = q0
δ(L10) = δ(B10, q0, q0) = q1
δ(L01) = δ(B01, q0, q0) = q2
δ(B00, q1, q2) = q3
δ(B00, q0, q2) = q2…

BL ←v2

←v1

B ←v3
L ←v4

L ←v5

δ(L00) = δ(B10, q0, q0) = q0
δ(L10) = δ(B10, q0, q0) = q1
δ(L01) = δ(B01, q0, q0) = q2
δ(B00, q1, q2) = q3
δ(B00, q0, q2) = q2…
rv2(q0, 00) = { (⊥,⊥) }rv2(q1, 10) = { (v2,⊥) }rv2(q2, 01) = { (⊥,v2) }rv2(q4, 11) = ←v
{ (v2,v2) }rv2(_, _)B= {} 1
L ←v2
rv4, rv5 :similar to rv2

B ←v3
L ←v4

L ←v5

δ(L00) = δ(B10, q0, q0) = q0
δ(L10) = δ(B10, q0, q0) = q1
δ(L01) = δ(B01, q0, q0) = q2
δ(B00, q1, q2) = q3
δ(B00, q0, q2) = q2…
rv2(q0, 00) = { (⊥,⊥) }rv2(q1, 10) = { (v2,⊥) }rv2(q2, 01) = { (⊥,v2) }rv2(q4, 11) = ←v
{ (v2,v2) }rv2(_, _)B= {} 1
L ←v2
rv4, rv5 :similar to rv2

B ←v3
L ←v4

L ←v5

rv3(q0, 00)= rv4(q0,00)*{(⊥,⊥)}*rv5(q0,00)= {(⊥,⊥)}---------------------------------------------------------------------------------------------------

rv3(q3, 11)= rv4(q1,00)*{(⊥,⊥)}*rv5(q2,11)∪ rv4(q1,01)*{(⊥,⊥)}*rv5(q2,10)∪ rv4(q1,10)*{(⊥,⊥)}*rv5(q2,01)(= {(v4,⊥)}*{(⊥,⊥)}*{(⊥,v5)}∪ rv4(q1,11)*{(⊥,⊥)}*rv5(q2,01)= {(v4,v5)}---------------------------------------------------------------------------------------------------

rv3(q2, 01)= rv4(q0,00)*{(⊥,v3)}*rv5(q0,00)∪ rv4(q0,00)*{(⊥,⊥)}*rv5(q2,01)∪ rv4(q2,01)*{(⊥,⊥)}*rv5(q2,00)= {(⊥,v3), (⊥,v4), (⊥,v5)}…

Example (2-ary): LEFT&RIGHT• Q = {q0, q1, q2, q3, q4}, F={q3}• Eventually…
BL ←v2←v1

rv1(q3, 11) = {(v2,v3), (v2,v4), (v2,v5)}
…

B ←v3
L ←v4

L ←v5

Time Complexity of OA: O(|t|n+1)• One-pass traversal: |t|• For each node,– |Q|×2n entries of r are filled– Need O(|Q|2 ・3n) ∪ and * operations– Each operand set of ∪ and * may be aslarge as O( |t|n )•  each operation takes O(|t|n) time in theworst case, as long as the “set”s arerepresented by usual data structure (lists, rbtrees,…)Time Complexity of OA: O(|t|n+1)• One-pass traversal: |t|Constant wrt |t|!
• For each node,– |Q|×2n entries of r are filled– Need O(|Q|2 ・3n) ∪ and * operations– Each operand set of ∪ and * may be aslarge as O( |t|n )•  each operation takes O(|t|n) time in the
What happens
if wehaveworst
case,
as long as the “set”s area set representation
withby usual data structure (lists, rbrepresentedO(1) operations??
trees,…)

Time Complexity of OA: O(|t|n+1)• One-pass traversal: |t|Constant wrt |t|!
• For each node,– |Q|×2n entries of r are filled– Need O(|Q|2 ・3n) ∪ and * operations– Each operand set of ∪ and * may be aslarge as O( |t|n )•  each operation takes O(|t|n) time in the
What happens
if wehaveworst
case,
as long as the “set”s area set representation
withby usual data structure
O(|t|) (lists,TimerbrepresentedO(1) operations??
trees,…)
Quering!

!! Our Main Idea !!
• SRED:Set Representation by Expression Dags
– Set is Repr’d by a Symbolic Expression Producing it

Instead of{(v2,v3), (v2,v4), (v2,v5)}

B ←v1
L ←v2

∪

{(v2,⊥)}

B ←v3L ←v4*We UseL ←v5∪{(⊥,v3)}{(⊥,v4)}{(⊥,v5)}BNF for SRED (Simplified)• SET ::=– Empty– Unit– NESET-- {}-- {(⊥,…,⊥)}• NESET ::=– Singleton( ELEMENT )– DisjointUnion( NESET, NESET )– Product( NESET, NESET )Properties of SRED
Set ofOutput Tuples

Input
Tree

size: OUT∈O(INn)size: INheight: H“SRED”
Data Structure
Size:
Because, ∪and * areO(min(IN,almost triviallyin O(1)O(IN) time O(IN) spaceProperties of SRED
InputTreesize: INheight: H

Set ofOutput Tuples
Thanks toempty-setelimination“SRED”
Data Structure
Size:
Because, ∪and * areO(min(IN,OUT))
almost triviallyin O(1)Thanks toO(IN) time empty-set
O(IN) spaceelimination

size: OUT∈O(INn)Properties of SRED
Input
Treesize: INheight: H

Set ofOutput Tuples
Thanks toempty-set
elimination“SRED”
Data StructureSize:Because, ∪and * areO(min(IN,OUT))
almost triviallyin O(1)Thanks toO(IN) time empty-set
O(IN) spaceelimination

size: OUT∈O(INn)Very Easyto Derive

isMember: O(H)
Get-Size: O(min(I,O))“Projection”: O(H・α)“Selection”: O(H)O(OUT) Enumeration of SRED(or, “decompression”)• Simple Recursion is Enough!

(assumption: ∪ is O(1), * is O(out) )– eval(Empty)= {}– eval(Unit)= {(⊥,…,⊥)}– eval(Singleton(e))= {e}– eval(DisjointUnion(s1,s2)) = eval(s1) ∪ eval(s2)– eval(Product(s1,s2))= eval(s1) * eval(s2)• (NOTE: A bit more clever impl. enables
O(OUT) time & O(1) working space)

For Advanced Operations…
• Actually we add a little more

information on each SRED node
– “Type”– “Origin”

∪01 v

3

10 v2

B ←v3

L ←v4

11 v1

{(v2,⊥)}

B ←v1
L ←v2

*We UseL ←v5∪{(⊥,v3)}{(⊥,v4)}{(⊥,v5)}

01 v3

01 v4

01 v3

01 v5

“Selection” on SREDdef• S[i:v] = {(v1,…,vi-1,vi+1,…,vn) |(v1,…,vi-1, v, vi+1,…,vn) ∈S}– Again, Simple Recursion!
– (S∪T) [i:v]= S[i:v] ∪ T[i:v]– (St1,u1 * Tt2,v2)[i:v] = S[i:v] * T if i∈t1
= S * T[i:v] if i∈t2
– St,u[i:v] = {} if v is not a descendant of u

• Other operations are also easy as longas they interact well with∪ and *Comparison
H. Meuss, K. U. Schulz, and F. Bry, “Towards Aggregated Answers
for Semistructured Data”, ICDT 2001
– Limited Expressiveness < Regular• G. Bagan, “MSO Queries on Tree Decomposable Structures Are
Computable with Linear Delay”, CSL 2006
– “Enumeration” only
• B. Courcelle, “Linear Delay Enumeration and Monadic SecondOrder Logic”, to appear in Discrete Applied Mathematics, 2009
– “Enumeration” only
– His “AND-OR-DAG” is quite similar to SRED (say, “*-∪-DAG”),
but no clear set-theoretic meaning is assigned; hence it is not
at all straightforward to derive other operations like selection•