We introduce a new compact model of XML Schema framework for streaming XML transformations introduced called a schema tree. Given an XSLT transformation xsl and an in [3]. The framework is capable to process automatically a XML schema xsd, we present a method which statically analyzes class of top-down XSLT transformations which captures a the schema tree constructed according to xsd and determines significant number of practically needed XML transformawhether xsl can be processed in a streaming manner on a set tions. The processing is done using a stack of the size proof XML documents defined by xsd. We consider streaming pro- portional to the depth of the input XML document - such tcheessiinnpgutthdaotcuusmeesnat -sttahcisk porfotcheesssiinzge ipsrohpigohrltyioenfafilciteontthien dperapcthticoef processing is highly efficient in practice since real XML since real-world XML documents are shallow. The schema anal- documents are shallow [9]. ysis is performed via stepwise application of templates of xsl on We focus especially on the schema-based analyzer the schema tree. We present the implementation of a schema tree which represents a powerful tool used within the Xord frameand the static XSLT analyzer on .NET platform. work to determine the most efficient way of processing the given XSLT transformation. For a given XSLT stylesheet xsl and an XML schema xsd1, it automatically analyzes 1 Introduction the memory usage of the streaming processing of xsl on a set of documents defined by xsd. The existing models for XML schemas (DOM, .NET XmlSchema) appeared inconvenient for the purpose of the streamability analysis, we therefore introduce the Xord Schema Model - a new compact model for schema representation. The model is abstract, and thus not bounded to a particular schema language. However, in the prototype implementation we employ W3C XSD notation [11, 12] for XML schemas.
Many applications need to employ streaming approach when processing huge data in XML format. Most typically, the languages XSLT [10] and XQuery [13] are used to specify XML transformations. Both of them enable the user to write a high-level specification based on tree manipulation. Common processors of these languages (e.g., Saxon, Xalan, AltovaXML) are tree-based, i.e., read the whole input document into memory and then perform the transformation itself. Related work. Several streaming processors for XSLT and
The XSLT and XQuery tree-based processors are ap- XQuery have been implemented. However, their efficiency
parently not suitable when transforming XML streams or was demonstrated only by experiments on a small number
huge XML data. In this case, the transformation can be ei- of XML transformations and input XML documents. It is
ther written by hand using an event-base parser (e.g., SAX, thus not known how much memory is consumed on clearly
StAX) or using some streaming transformation language characterized transformation classes.
(STX [
In this paper we focus on the problem how to enable the documents of various sizes against a simple query. Using user to write a tree manipulation specification in the XSLT XSM the processing time grows linearly with the document language, and at the same time to process it in a streaming size, while in the case of standard XQuery processors the manner automatically. Such automatic streaming processor time grows superlinearly. More complex queries have not is supposed to apply the tree-manipulation functions over been tested. a continuous stream of data while the buffering is treated BEA/XQRL [4] is a streaming processor that implements automatically. An important issue is to design the processor full XQuery. The processor was compared with Xalan-J in such a way that the size of memory buffers is minimized XSLT processor on the set of 25 transformations and anfor the given transformation and the input document. other test was carried on XMark Benchmarks. BEA pro
We describe the implementation of the Xord framework which represents a prototype XSLT automatic stream- 1 We use the term XML schema for a general schema for XML ing processor. The Xord framework is based on the formal documents.
XfAnalyzer
XfAlgorithm XfXsdSsxtAnalyzer
XfTemplateAnalyzer
XfSsxt sch
XfSchema (SchemaModel) xslt
xslt xslt
XfXslt (TemplateModel) SchemaModel Fig. 1. The Xord framework.
TemplateModel
Ssxt adopted to model any XML schema language based on structure definition.
Furthermore, the framework is complemented by a set of auxiliary helper classes. The algorithmic part of the API supports: SsxtAlgorithm algorithm derived from the abstract Al
gorithm model, and XsdSsxtAnalyzer algorithm derived from the abstract Analyzer model, and using the Schema Model and the
Template Model.
The implementation of the above mentioned models are described in more detail in following sections. cessor was fast on small input documents, however, the processing of large documents was slower since the opti- 3 XSLT representation mizations specially designed for XML streams are limited The Xord framework is currently restricted to process simin this engine. ple XSLT transformations on XML documents without data
FluXQuery [7] is a streaming XQuery processor based values. on a new internal query language FluX which extends XQuery with constructs for streaming processing. XQuery Simple XSLT stylesheets. Simple XSLT stylesheet conquery is converted into FluX and the memory size is opti- sists of an initializing template and several transforming mized by examining the query as well as the input DTD. templates. The initializing template sets the current mode FluXQuery supports a subset of XQuery. The engine was to the initial mode m0 and calls processing of the root elebenchmarked against XQuery processors Galax and AnonX ment of the input document. It is of the form: on selected queries of the XMark benchmark. The results <xsl:template match="/"> <xsl:apply-templates mode="m0"/> show that FluXQuery consumes less memory and runtime. </xsl:template>
SPM (Streaming Processing Model) [6] is a one-pass streaming XSLT processor without an additional memory. The transforming templates are of the form: Authors present a procedure that tries to converts a given <xsl:.t.e.mptleamtpelamtaetcbho=d"yna.m.e." mode="m"> XSLT stylesheet into SPM. No algorithm for testing the </xsl:template> streamability of XSLT is introduced, and therefore the class of XSLT transformations captured by SPM is not clearly characterized.
The template body contains output elements (possibly nested) and apply-templates calls. Output elements are of the form: 2
Xord Fra1 m1ework / The Xord framework for analyzing and transforming XML data is implemented on .NET platform. Its application interface is formed by a set of interface classes for traversing analyzed data structures. The core of the framework consists of these abstract models (see Fig. 1): 1. Template Model for transforming templates implemen
ted by the XfXslt classes, 2. Schema Model for XML schemas implemented by the
XfSchema classes, 3. Algorithm Model for streaming algorithms implemen
ted by the XfSsxt classes, 4. Analyzer Model for static analyzers implemented by the
XfXsdSsxtAnalyzer and XfTemplateAnalyzer classes.
Xord Template Model. In the Xord framework, XSLT stylesheets are represented by a set of classes, an Xord Template Model. Its simplified object structure is depicted in Fig. 2.
Each template from the XSLT contains a sequence of template calls. A template call consists of the parsed XPath expression and the template called by the apply-templates Since the models are abstract, the Template Model may be mechanism. The input template file is parsed into these adopted to model templates of any template-based XML structures before the analysis. Then the analysis algorithm transformation language and the Schema Model may be directly traverses the DAG, evaluates the expressions etc. where name refers to an element name. <name> . . . element content . . . </name> The apply-templates construct has a select attribute that contains selecting expression, and a mode attribute. <xsl:apply-templates select="selexp" mode="m’"/> A subset of XPath expression is allowed in templates they contain child and descendant axis, and select nodes by name: XPath := Step j Step/XPath
Step := child::name j descendant::name We represent an XML schema hierarchically as a schema programmatically, but its application interface is not very tree. The representation does not depend on a particular useful for parsing and analyzing existing schemas. schema notation (DTD, XSD). The schema tree consists of Since the schema analysis using standard XML schema two kinds of nodes: DOM model would be very complicated and tangled, we have designed an Xord Schema Model which is targeted to – element nodes: correspond to an element type defined effective representation and analysis of existing schemas.
within schema A simplified object structure of that model is depicted in – constructor nodes: correspond to constructors used in Fig. 3.
the schema (sequence, choice, *, +, ?) The whole schema is represented as an associative array of simple or complex type nodes. 1E/ a1ch complex node The relationships among element types and constructors contains a list of references to its child nodes with their are represented by the structure of the tree. cardinality. Using this recursive structure that form a DAG
Some subtrees of schema tree may be identical - this (or a tree with one particular node selected as a root), the situation occurs if we derive the1s/ c1hema tree from DTD or parsed schema could be easily traversed and processed. XSD containing shared element types. When designing the analyzer, the tree representation is more convenient. However in the implementation of schema-based analyzer each 5 Schema-based analyzer type is represented as a single node and the whole schema is represented as a DAG (see Schema Object Model be- The schema-based analyzer applies the given XSLT stylelow). sheet xsl to the schema tree xsd, starting at the root node.
In the schema-based analysis, we consider XML sche- First, let us remind the principles of the XSLT application mas without the choice constructor and recursive defini- to the XML document tree. Let tmp be the current temtions. Such schema can be represented as a single regular plate of the XSLT stylesheet (at the beginning of the transexpression. This representation is useful in the extraction formation, it is the template matching the root element in part of the analyzer algorithm (see Section 5). the initial mode m0) Xord Schema Model. Although there are well established and widely used XML parsers, we have found no suitable parser for XSD. To perform schema manipulation, the .NET Framework provides a set of classes called the Schema Object Model, or SOM for short. The SOM is for schemas what DOM is for XML documents: the SOM classes represent various parts of a schema, for example XmlSchemaSimpleType, XmlSchemaElement, there are many other classes that represent attributes, facets, groups, complex types, and so on. This model is especially useful for creating schemas 1. The node sequence selected by the XPath expressions
in the rule calls of the current template are found. 2. The templates called by the rule calls are applied to the
selected nodes.
However, in case of the schema tree, a modification of the first step of this simple algorithm is needed: 1. All possible node sequences selected by the XPath expressions in the rule calls of the current template are found. 2. The templates called by the rule calls are applied to the selected nodes.
bool AnalyzeNode(XfTemplate t,XfSchema.Node n) f if(t.Empty)
return true; XfLastNames li = t.GetLastNames(); XfRegexp re = sch.ExtractFragment(n, t); if(re.Empty())
return true; if(! sch.Compare(re, li))
return false; foreach(XfCall call in t.calls) f
List<XfSchema.Node> ln =
new List<XfSchema.Node>(); ln = sch.EvalExp(n, call.select); foreach(XfSchema.Node ni in ln) f
AnalyzeNode(call.template, ni); Since the set of all possible node sequences selected by XPath expressions in the first step may be infinite, we represent it in the form of regular expression regexp. Such regular expression is basically a fragment of the schema tree, i.e., a set of its nodes (not necessarily connected) which is a fragment of the regular expression representing the whole schema tree.
The regular expression regexp may contain both ele- g ment nodes and constructor nodes. It is extracted as fol- greturn true; lows: First, the node sequence selected by the XPath ex- g pressions are found in the same way as in the XML docu- Fig. 4. The code of the AnalyzeNode function. ment tree (constructor nodes are skipped). Second, all constructors appearing in the branch of the schema tree from the root to the selected nodes are added to the sequence. 6 Stack-based streaming algorithm The hierarchy of the nodes is preserved by delimiting the nodes appearing at the same level of the schema tree by The stack-based algorithm is based on a formal model called parentheses. simple streaming XML transducer (SSXT), therefore we call
We say that regexp represents possible reading orders it the SSXT algorithm. The transducer has a single input of the element names selected by the expressions in tmp, head that reads the input document sequentially, and a sini.e., the order in which the elements are accessed when a gle output head that generates the output document sequendocument defined by the schema xsd is read sequentially. tially. The SSXT is equipped with a stack to store tempoNow let names be a sequence of element names in the or- rary data. der they are called in tmp - clearly, the sequence can be The SSXT takes an input document din and a top-down constructed statically by examining the last steps of the XSLT stylesheet xsl as the input. It reads din sequentially XPath expressions in tmp. The names sequence repre- in one pass and apply the stylesheet xsl stepwise. First, sents the processing order of the elements. In case one of the template matching the root element of din in the initial the reading orders does not conform to the processing or- mode m0 is set to be the currently processed template (curder, the order-preservation of the xsl is violated and the rent template). The processing proceeds in cycles. During SSXT algorithm is not applicable2. It is thus only neces- a single cycle, a single template call of the current template sary to compare regexp to the names sequence in order to is processed. check applicability ot the stack-based algorithm. Processing cycle. All XPath expression within a template are evaluating concurrently. The evaluation is realized by deterministic finite automata (DFA)3. A single DFA is constructed for each expression. When the processing of a template starts, the sequence of the initial states of DFAs is pushed on the stack. The input head of SSXT reads the elements of din in document order. When a start-tag is encountered, new sequence of DFAs is computed. Three situations may occur: Implementation. The core of the schema-based analyzer is the AnalyzeNode function which takes two arguments - a template of xsl and a node of the schema tree xsd.
It performs the application of the template to the schema tree node as described above. Using the Template Model and the Schema Models allows the analyzer algorithm to be simple and straightforward - see Fig. 4.
The comparison of the regexp to the names sequence is accomplished by the Compare function. Its implementation is based on inherent properties of its arguments. Instead of an expensive checking of swapping for each pair of names, the predicate is a compound of two simple steps.
First, regexp is checked for existence of two distinct names within any ’+’ or ’*’ sequence. Second, the last names in names are stripped to those contained in the schema being used, adjacent duplicities are reduced to a single name, and the resulting list is linearly compared to names contained in regexp. Since each name appearing regexp must be contained in names, any difference cause a fail. 2 See [3] for further details. a) new sequence contains no final state - the input head
continues in evaluation, b) new sequence contains a single final state which belongs to the DFA evaluating the lastly-matched expression or an expression located after the lastly-matched expression - the corresponding template call is processed, c) new sequence contains a final state which belongs to the DFA evaluating expression located before the lastlymatched expression, or it contains two or more final states - error. 3 We refer the reader to [2] for a more detailed description of this evaluating method.
In case b), the current cycle configuration (template id, matched expression id) is pushed on the stack and new cycle for processing the called template starts. The cycle configuration is popped after the whole called template has been processed and the control moves back to the current template. In case a), the evaluation continues. Here if an end-tag is encountered, the sequence of the DFA states located at the top of the stack is popped. Hence, the XPath expression of the current template are evaluated on “branches” of din.
Implementation. The implementation of the SSXT algorithm uses both Template Model and Algorithm Model classes.
Since the algorithm is stack-based, the main data structure used is a polymorphic stack stk of sequences of DFA states (SIDfaSequence) and cycle configurations (SICycleConfig), see Fig. 8.
Until the transformation is finished the top of stack is checked and the stack item is processed, see the function RunSsxt in Fig. 5. In case of an empty stack and nonempty remaining input new DFA sequence is pushed on the stack. void ProcessDfaSequence(XfXml xml) f
SIDfaSequence ds = stk.GetDfaSequence(); switch(xml.currType) f case XmlNodeType.Element: SIDfaSequence new ds = ds.Transition(xml.currName); if(!new ds.HasFinalStates()) f stk.Push(new ds); xml.Advance(); g else f XfCall myCall = new ds.GetCallWithFinalState(); currTemplate.Generate(currCall, myCall); XfTemplate calledTemplate =
xslt.SelectTemplate(xml.currName, myCall.mode); if(calledTemplate.Empty) f calledTemplate.Generate(null, null); currCall = myCall; if(xml.laType == XmlNodeType.Element) stk.Push(new ds); xml.Advance(); g else f stk.Push(new SICycleConfig(currTemplate, myCall)); currTemplate = calledTemplate; currCall = null; g g break; case XmlNodeType.EndElement: if(xml.laType == XmlNodeType.EndElement) stk.Pop(); xml.Advance(); break; default: stk.Pop(); break; void RunSsxt(XfXml xml) f
XfTemplate currTemplate = xslt.Start(); XfCall currCall = null; bool transformed = false; while(!transformed) f if(!stk.Empty()) f switch(stk.Type()) f case XfStack.ItemType.DfaSequence: ProcessDfaSequence(); break; case XfStack.ItemType.CycleConfig: ProcessCycleConfig(); break; g g else f switch(xml.currType) f case XmlNodeType.Element: stk.Push(new SIDfaSequence(currTemplate)); xml.Advance(); break; case XmlNodeType.EndElement: currTemplate.Generate(currCall, null); transformed = true; break; g g g g current DFA sequence contains no final states. Otherwise 7 Evaluation the output is generated and a new cycle configuration is placed on the stack. In case of a template without calls, its The evaluation and measurements of the SSXT algorithm output is generated immediately.
implementation confirmed our expectation that it requires
XfCall (TemplateModel) + template : XfTemplate + node : XmlNode + select : XfXpath + mode : string
call
SICycleConfig + template : XfTemplate + call : XfCall call
DfaItem + call : XfCall items
SIDfaSequence + template : XfTemplate + items : List<DfaItem>
XfTemplate (TemplateModel) + match : string + mode : string + node : XmlNode + calls : List<XfCall> template ing algorithm with such buffers and we obtain much more powerful automatic streaming XSLT processor.
Acknowledgments. This work was supported in part by the National programme of research (Information society project 1ET100300419).