By representing an XML document in-memory as an object tree, DOM parsers preserve and allow dynamic access to the XML document structure and content. However, this object-based XML processing does not perform or scale well when processing large XML documents because of its high memory costs.

Additionally, DOM-based XML data retrieval has redundant DOM tree traversals when processing multiple XPath expressions. For example, suppose you have two XPaths: /A/B/C and /A/B/C/D, from which you wish to retrieve data in an XML document DOM as shown in Figure-1.

Figure 1. DOM XPath Data Retrieval

When evaluating /A/B/C, the DOM parser will select the A element, then iterate its children selecting all the B elements under A. After all the B elements are selected, then all the C elements under B are selected and evaluated. Next to evaluate /A/B/C/D, the same process is performed learning nothing from the previous XPath. From Figure-1, you can find that A, B and C elements are processed twice. This is not efficient especially when you have hundreds of XPath expressions as in a large XML document and can result in scalability issues once the application gets deployed under real-world document loads.

Because of their limited memory use, the stream-based SAX and StAX XML parsers are ideal options for effectively retrieving data from large XML documents. SAX is even better than StAX for multiple XPath evaluations, because you can easily leverage the broadcasted SAX events to multitask within the XML parsing process. However, both of them do not maintain the hierarchical structure of XML documents and thus lack the XPath support.

As more and more real world applications require efficient data retrieval from large XML documents, we have to find a solution that provides a lightweight and efficient strategy to:

The Extractor initialization requires registerations of XPath expressions and their respective content handlers to receive the extracted XML. As an XML schema or DTD describes the structure of input XML documents, the Extractor also provides a provision to accept them within this initialization, as it will be able to use the information to optimize retrieval paths.

("my", "http://www.foo.com/xml")

/my:PO/Shipping_Address

/PO/LineItems/Item[../../Billing_Address/To/text()="John Smith"] 

The XPath compilation process needs to translate and build indexes for all the registered XPaths. This processwill first split an XPath into its location path and predicate component parts, as these will be processed differently. The location paths will be further compiled to reflect the fact that SAX events will occur in document order and normalized to eliminate redundant matching of common path steps. Each XPath predicate will be compiled into a predicate dependency table that will then be linked to its associated compiled location path as seen in Figure-4.

Figure 4. Compilation of XPaths

The predicate dependency table contains its own set of location XPath expressions related with a value or reference to another location XPath. These paths may contain either forward (children) or backward (parent) references. For backward references, all the data will be preserved in hash table for later reference. For forward references, depending on the isAll option, the Extractor will have to hold the data in memory until the XPath expression can be evaluated and the SAX events send out. In this case, the status of the dependency will be set as yet-to-be-matched so that when later all precidates value are available, the action for re-evaluating the location XPath will be triggered. We will discuss this further in the next XPath Tracking section.

Secondly, an overall index tree will be built based on the location XPath expressions including those in the predicate dependency tables. There are two types of index trees for Extractor:

Figure 5. XPath Dependency Tree

In order to track XPath, an automaton is built to maintain the hierarchical relationships between XML elements and attributes. Each state in this automaton reflects the current XPath context with the SAX events triggering the state transitions. Due to the nature of XPath semantics, the state machine can be implemented as a stack, which keeps the following information:

Based on the information in the stack, a set of XPath expressions are treated as the current XPath. All the current XPaths will be matched against the XPath index built during the XPath compilation. Any predicates evaluated to be false will result in removing the XPath from the tracking list.

Without DTD or XML schema, the XPath dependency tree is traversed synchronously to when parsing the XML document as shown in Figure-6. It can provide list of possible node matches and the match of the registered XPaths.

Figure 6. Synchronous XPath Dependency Tree Traversal

With DTD or XML schema, matching of the XPath is then primarily based on the synchronous data model traversal when parsing the XML document as shown in Figure-7. During this traversal, the annotations on the data model are retrieved and evaluated to determine XPath match. This annotation look-up process is much more efficient than the string-match approach taken when DTDs or XML schemas are not available.

Figure 7. Synchronous Data Model Traversal

By using the existing XML schema validation engine, the implementation of such look-up process for the Extractor also take less time and effort.

We have discussed that isAll=true affects the execution behavior of the Extractor when XPath expressions contain forward (child or decedent) data references. Because the Extractor cannot decide the match of XPath when it receive the data, in order to evaluate such XPaths (when isAll=true), the Extractor has to hold the XML data in memory until it can successfully evaluate the XPath. To minimize the memory use, we create a table to record all the SAX events in order to send out the data after all the predicates are evaluated. This similar process is used to fill in the predicate table in case it includes forward references to SAX events which have not yet occurred. Once the table is complete the value can be sent out.

The Extractor needs to provide flexible outputs to make it easy-to-use. Thus with this model, its outputs can be a set of events, XML Sequence objects or XML files.

First, when the Extractor signifies the match of XPath using events, these events can easily be pipelined in stream-based XML processing applications resulting in managed memory use. The events include all the SAX events reporting the XML data with two additional events signifying the XPath match:

Thus an application can register its own handlers. In this case, it needs to implement the XContentHandler interface used by the Extractor.

Second, in order to enable the Extractor to easily integrate with XQuery 1.0 or XSLT 2.0 engine, the XMLSequenceBuilder is provided as a built-in handler, which processes the events sent out by the XPath extraction engine and represents the result set as an XML Sequence object. The XML Sequence is an object defined in XPath 2.0 data model representing the result set of XPath evaluations. In the Extractor implementation, an XMLSequence interface is defined as follows:

public interface XMLSequence {
  public boolean next();
  public XMLItem getCurrentItem();
  }

The XMLSequence object contains a list of XMLItems, which includes both the XML data and its datatype:

public interface XMLItem {
   public OXMLSequenceType getItemType();
  
   public String getLexicalValue();
   public boolean getBoolean();
   ...
   public XMLNode getNode();
  }

Another build-in handler is the XMLSAXSerializer, which simplifies the use of the Extractor by creating a set of files for the extracted XML data set.

Figure-8 shows a content management system that extracts the XML data and metadata using the Extractor and inserts them into the relational database tables in the Oracle database. The XML data extraction is based on the XPaths stored in an XPath table associated with a DTD using the DTD's system ID and public ID, or with an XML schema using the XML Schema Location URL.

Figure 8. The Extractor Content Management Use Case

When initializing the Extractor, the content management application retrieves the DTD's sysID and docID or the XML schema location URL from the XML document and uses them to query the XPath table. After it gets a list of XPaths, the application then registers the XPaths to the Extractor and specifies instances of content handlers to receive the retrieved data. The XML schema or DTD is also provided to the Extractor to optimize the XPath compilation and tracking process.

When XML document is parsed in SAX, the Extractor retrieves the XML data for each XPath and disseminates the data to the corresponding the content handlers. The content handlers then insert the extracted data into either metadata or data tables in the database.

The Extractor in this application delivers high performance XML data retrieval because all the XPath expressions are now processed within one XML document traversal and all the XML processing occurs in a SAX stream that permits memory resource management.

The Extractor can also integrate into Web service proxy servers or clients to extract data from SOAP XML messages. Figure-9 shows a Web service application using the Extractor as a data router to disseminate data to the proper users.

Figure 9. The Extractor Web Service Use Case

In this Web service application, all the client applications subscribe to the data services by registering XPath expressions to a service broker. The service broker then sets the XPath expressions to an Extractor. When the service broker invokes Web services using SOAP and gets back Web service responses in SOAP, the SOAP messages are then parsed and processed by the Extractor, where data is extracted from the SOAP messages and disseminated to each client based on their XPath-based service subscriptions.

In this case, the Extractor not only provide high-performance XML data extraction, it also allows Web service clients to share Web service responses. This can greatly reduce the round-trip traffic of Web service invocations over the Internet and thus improve the performance and scalability of the whole system.

As we have discussed, XQuery and XSLT rely heavily on the XPath queries for their execution. The current DOM-based XPath engines suffer in their ability to process large XML documents. The design of the Extractor allows it to provide the XPath services required by the XQuery or XSQL engine through registering XPaths to the Extractor and receiving results in XML Sequence objects defined in XPath 2.0 as shown in Figure-10.

Figure 10. The Extractor XSLT/XQuery Use Case