Contemporary XQuery processing and optimization
techniques are usually focused on querying and, in most cases,
ignore the existence of user-defined functions. In the era
of XSLT 1.0, the implementation techniques had to
recognize user-defined functions (templates) well (see for
instance [
There were several attempts to apply Datalog or
Datalog-like models to XPath or XQuery. There are also
topdown approaches using structural recursion, i.e. strongly
syntactically limited form of Horn clauses with function
symbols [
In this paper, we (informally) define the language BTLog as an extension of Datalog. In the Section 3, an abstraction of an XQuery program as a forest is defined. In the fourth section, the principles of the transformation to BTLog is defined and shown on an example. In the Section 5, ⋆ Project of the program “Information society” of the Thematic program II of the National research program of the Czech Republic, No. 1ET100300419 – Termination – using the T-operator, any number of values may be generated. Therefore, termination is not generally guaranteed and any BTLog evaluation algorithm shall cope with termination problems. – Minimal model semantics – without negation, minimal model semantics works well with BTLog, just as it works with Datalog without negation. – Stratification – In Datalog¬, stratification is used to extend the notion of minimal model. Similar definition may be used in BTLog, resulting in the language BTLog¬,strat. – Non-stratifiable program semantics – stable model semantics is used for non-stratified BTLog¬ programs.
Definition of the abovementioned terms and detailed
discussion of theoretical properties of such a language may
be found for instance in [
g function toc($P) $P h for $X
$X in
return i $P j <section> k , m n $X/section a main b <toc> c
toc() d for $S
$S in
return e doc("D") f $S/book l $X/title toc()
Principles of the transformation
The model is based on the following principles:
– Nodes within a tree are identified by node identifiers
using Dewey ID labeling scheme. (See, for instance
[
Our model assigns a set of predicates to each AST node, i.e. to each address E: – Invocation invE (i,f ) enumerates the contexts in which the expression E is evaluated. Argument i represents the call stack that brought the execution to the examined expression E. f is the stack of sequence identifiers selected by the for-clauses throughout the descent along i to E. The two stacks together form the identification of the dynamic context in which an expression is evaluated. While the XQuery standard defines dynamic context as the set of variable assignments (with some negligible additions), our notion of dynamic context is based on the stack pair that determines the descent through the code to the examined expression, combining both the code path stored in i and the for-control variables in f . The key to the sufficiency of this model is the observation that the variable assignment is a function of the stack pair. – Atomic list alstE (i, f, s, v) represents the atomic value portion of the assignment of the result value of the expression E to the contexts enumerate by invE (i, f ). s is a sequence identifier, v is a value of an atomic type as defined by the XQuery standard. The predicate alstE (i, f, s, v) is true if the value of the expression E in the context (i, f ) contains the atomic value v at position s. – Node list nlstE (i, f, s, t, n) represents the node portion of the result value of the expression E. The meaning of i, f , and s is the same as in alstE . t is a tree identifier – for external documents, it is a literal value, for temporal trees, it is the expression T(i1, f1) corresponding to the environment identification at the moment of tree creation. n is a node identifier in the form of a Dewey ID. – Environment envE (i, t, n, a) represents the tree environment associated to the result value of the expression E. i determines the call context (note that the environment is independent of the control variable stack). t is a tree identifier, n is a node identifier, a is a tuple of properties assigned to a node by the XML Data Model, containing node kind, name, typed and string values, etc. Particular properties are accessed using predicates name(a, v), string(a, v), etc. – valstE,$x(i, f, s, v), vnlstE,$x(i, f, s, t, n), and venvE,$x(i,t,n,a) represent the assignment of the values of the variable $x ∈ vars[E] to the contexts satifying invE (i, f ). The meaning of the arguments is the same as in alstE , nlstE , and envE . 4.2
The following example shows the Query 1 transformed to a BTLog program. The subscripts in the predicate names correspond to the adresses shown in Fig. 2; unused and identity rules were removed. The main expression of the Query 1 transforms to the following BTLog rules:
-- variable $S inva(1, 1). -- program start enve(i, D, n, a) :– inve(i, f ), doc(”D”, n, a).
-- doc(”D”) tree environment vnlstf,$S(i, T(s, f ), 1, t, n) :– nlsta(i, f, s, t, n). nlstf (i, f, T(t, n), t, n) :– vnlstf,$S(i, f, s, t, m), enve(i, t, n, T(element, book)), child(m, n).
-- $S/book node nlstd(i, f, T(s, r), t, n) :– nlstf (i, T(s, f ), r, t, n). vnlstg,$P(T(c, i), f, s, t, n) :– nlstd(i, f, s, t, n).
-- argument $P in toc venvg,$P(T(c, i), t, n, a) :– enve(i, t, n, a).
-- environment of $P in toc nlstc(i, f, s, t, n) :– nlstg(T(c, i), f, s, t, n).
-- the return value of toc envc(i, t, n, a) :– envg(T(c, i), t, n, a).
-- the return value environment nlstb(i, f, 1, T(i, f ), 1) :– inva(i, f ).
-- the <toc> node envb(i, T(i, f ), 1, T(element, toc)) :– inva(i, f ). envb(i, T(i, f ), T(s, p), a) :– nlstc(i, f, s, t, m), envc(i, t, n, a), cat(n, m, p).
-- the <toc> node environment out(i, t, n, a) :– envb(i, t, n, a).
-- the output tree The following rules correspond to the function toc: invj(i, T(s, f )) :– vnlstg,$P(i, f, s, t, n).
-- the invocation of the return clause vnlstj,$X(i, T(s, f ), 1, t, n) :– vnlstg,$P(i, f, s, t, n).
-- variable $X nlstl(i, f, T(t, n), t, n) :– vnlstj,$X(i, f, s, t, m), venvg,$P(i, t, n, T(element, title)), child(m, n).
-- $X/title expression nlstn(i, f, T(t, n), t, n) :– vnlstj,$X(i, f, s, t, m), venvg,$P(i, t, n, T(element, section)), child(m, n).
-- $X/section expression vnlstg,$P(T(m, i), f, s, t, n) :– nlstn(i, f, s, t, n).
-- argument $P in toc venvg,$P(T(m, i), t, n, a) :– venvg,$P(i, t, n, a).
-- environment of $P in toc nlstm(i, f, s, t, n) :– nlstg(T(m, i), f, s, t, n).
-- the return value of toc envm(i, t, n, a) :– envg(T(m, i), t, n, a).
-- the return value environment nlstk(i, f, T(1, s), t, n) :– nlstl(i, f, s, t, n). nlstk(i, f, T(2, s), t, n) :– nlstm(i, f, s, t, n).
-- the concatenated value envk(i, t, n, a) :– venvg,$P(i, t, n, a). envk(i, t, n, a) :– envm(i, t, n, a).
-- the environment of the concatenation nlstj(i, f, 1, T(i, f ), 1) :– invj(i, f ).
-- the <section> node envj(i, T(i, f ), 1, T(element, toc)) :– invj(i, f ). envj(i, T(i, f ), T(s, p), a) :– nlstk(i, f, s, t, m), envk(i, t, n, a), cat(n, m, p).
-- the <section> node environment nlsth(i, f, T(s, r), t, n) :– nlstj(i, T(s, f ), r, t, n). nlstg(i, f, s, t, n) :– nlsth(i, f, s, t, n). envg(i, t, n, a) :– envj(i, t, n, a).
-- the result of the function -- the result environment
Figure 3 show the dependence graph for the predicates of Query 1. There are three strongly connected components (shown in bold) – the first one carries the environment of argument $P (i.e. the input document) down through the recursion of the function toc. The second component corresponds to the recursive descent of the variable $P through the document. The third component collects the constructed nodes back, unwinding the call stack.
For Expression – E0 = for $y in Ein return Eret
The for-expression generates a new dynamic context for each member of the sequence Ein; in our model, it is represented by pushing the sequence identifier s onto the control stack f :
invEret (i, T(s, f )) :– nlstEin (i, f, s, t, m).
At the same time, the variable $y is added to the dynamic context, defined as follows: vnlstEret,$y(i, T(s, f ), one, t, n) :–
nlstEin (i, f, s, t, n).
venvEret,$y(i, t, m, a) :– envEin (i, t, m, a).
For older variables, the following rules are defined for each $x ∈ vars[E0] \ {$y}: vnlstEret,$x(i, T(s, f ), r, u, m) :– nlstEin (i, f, s, t, n),
vnlstE0,$x(i, f, r, u, m). venvEret,$x(i, u, m, a) :– venvE0,$x(i, u, m, a).
Finally, the value of the for-expression is created by the concatenation of the return clause values: nlstE0 (i, f, T(s, r), t, n) :– nlstEret (i, T(s, f ), r, t, n). envE0 (i, t, n, a) :– envEret (i, t, n, a). 5
Representation of Core XQuery Operators
Let Expression – E0 = let $y := Edef return Eret
The let-expression adds the variable $y to the dynamic
context. Nevertheless, the identification of the context is
There are several variants of core subsets of XQuery, in- not changed and the other variables are also preserved.
cluding the core grammar defined in the W3C standard
[
XSLT and XQuery are related languages and the transla- vnlstEret,$y(i, f, s, t, n) :– nlstEdef (i, f, s, t, n).
tion from XSLT to XQuery is known (see [
Note: Most XQuery operators do not change the assignment of variable values; therefore, we will omit the $y in Ein where propagation rules in the subsequent description. We will also omit the rules for alstE and valstE,$x whenever they are similar to nlstE and vnlstE,$x.
Where Clause – E0 = for Ewh return Eret
Adding where clause to a for-expression affects the set of contexts generated for the return clause; similarly, variable models are affected: Function call – E0 = f( E1 )
Assume that Ef is the root of the function and $x is the name of the formal argument. The rules implement pushing the call address E0 onto the call stack and popping it back upon return.
invEf (T(E0, i), f ) :– invE0 (i, f ). vnlstEf ,$x(T(E0, i), f, s, t, n) :– nlstE1 (i, f, s, t, n). venvEf ,$x(T(E0, i), t, n, a) :– envE1 (i, t, n, a). nlstE0 (i, f, s, t, n) :– nlstEf (T(E0, i), f, s, t, n). envE0 (i, t, n, a) :– envEf (T(E0, i), t, n, a).
alstEwh (i, f, s, true). invEret (i, T(s, f )) :– alstEwh (i, f, s, true). vnlstEret,$y(i, T(s, f ), one, t, n) :– nlstEin (i, f, s, t, n), vnlstEret,$x(i, T(s, f ), r, u, m) :– nlstEin (i, f, s, t, n),
alstEwh (i, f, s, true), vnlstE0,$x(i, f, r, u, m).
Equality Test – E0 = E1 eq E2 eqE0 (i, f ) :– alstE1 (i, f, s, v), alstE2 (i, f, r, v). alstE0 (i, f, 1, true) :– eqE0 (i, f ). alstE0 (i, f, 1, false) :– ¬eqE0 (i, f ). inv[a] env[e] doc
nlst[e] vnlst[f,$S] nlst[f] nlst[d]
nlst[l] venv[g,$P] nlst[n]
vnlst[j,$X] vnlst[g,$P] nlst[k] nlst[m] nlst[g] nlst[h] nlst[j] inv[j] env[b]
out nlst[c] env[c]
env[g] env[j]
env[m] env[k] tree information is merged by the envE0 rules. Since the tree identifier exactly determines the context in which the tree was created, trees having the same identifier must be identical; therefore, merging the tree environments do not alter them anyway. 6
We have presented a model of XQuery evaluation based on Horn clauses under the BTLog¬ syntax. From the syntactic point of view, this model comprehends the following XQuery structures: Declare function, function call, forclause, let-clause, where-clause, stable-order-by-clause, quantified expressions, equality operator on atomic values, Boolean operators including negation, union, intersection, except operators, concatenation (,) operator, statically named document references (fn:doc), forward/reverse axis navigation, name tests, fn:root, and element constructors.
There are two important omissions from the core XQuery that are not covered by this model: Positional variables and aggregate functions. There are also some flaws in error handling, namely the fact that the model may silently process some situations that shall be signalled as an error. These issues will be addressed by our future research.
The universal quantified expression (every), the
equality operator, and the node-set subtraction operator
(except) involve negation in their BTLog rules. Some
XQuery programs are not stratifiable after conversion to
BTLog¬. This is not necessarily a weakness of the
approach – since the XQuery language is Turing-complete,
we shall not expect general stratifiability. This way, the
stratifiability of its BTLog¬ equivalent may be used
as a borderline between “easy” and “difficult” cases.
Fortunately, it shows that most of the real-life XQuery programs
fall in the “easy” stratifiable category – for instance, all the
XML Query Use Cases [
Since termination in XQuery is not guaranteed, it may be expected that it is not generally guaranteed also in BTLog. Our future research will focus on static analysis methods trying to discover a termination guarantee in a BTLog program (of course, due to the Turing-completeness, no method can decide on the existence of a termination guarantee).