A C/C++ XSLT Processor Architecture Optimized for Application Development.

1. XML: A Key Technology for Object Relational Databases

The Oracle9i database has XML capabilities which are built right in to the database engine and integrated with Java and SQL-PL/SQL. During the development of Oracle9i and Oracle's XML development solution named XDK, we have evolved a unique architecture for the C/C++ based XSLT engine. This facilitates the XSLT engine to be integrated with any performance critical C/C++ application irrespective of its platform and DOM implementation. We achieved this by defining a C/C++ based DOM API and a set of additional callbacks to ensure the platform independence. The XSLT processor accesses the DOM API through a set of callbacks. Thus the XSLT processor becomes fully independent of any specific DOM implementation. By making use of this architecture we successfully integrated the same engine into the database as well as in a standalone XSLT processor

2. Need for a C/C++ Based DOM API

Integration of an XSLT processor right into the core of a database engine presents a unique challenge. The performance constraints and the existing code base necessitates that the processor must be C based. In turn, to implement such a processor we must first define a C based DOM API. The DOM specification as recommended by W3C is for object-oriented languages like Java and C++. C is a procedural language. In defining a parallel API for C we must ensure that it is functionally equivalent to the W3C recommendation and retains as close a structure as possible. Unlike Java, which is completely platform independent, C has platform specific idiosyncracies. A common C based XSLT processor must steer clear of all the platform specific assumptions to ensure its wide application. Once we have developed the C based processor it is trivial to wrap it in a set of C++ classes for use in C++ applications. Similarly if a C++ application has its own DOM implementation, it would need to write C based wrapper to use it in the C based XSLT processor.

2.1. A Callback Based DOM API

There are many possible ways to implement a predefined DOM API. Some applications may need to implement DOM in a very memory efficient way. Others may emphasize dynamic generation of the the DOM content or some other application specific need. A standalone XSLT processor may read the whole input XML document to populate an in-memory DOM. However, a database can not read its terabytes of data to populate an in-memory instance of DOM. There must be a different DOM implementation optimized specifically for this scenario. The standalone version can tune for fast reads while the database version would selectively populate only sections of an otherwise huge DOM. A common XSLT processor should be able to work with any implementation. Infact the XSLT processor may actually need to determine at runtime that which DOM implementation it needs to use. For example, the database engine may want to populate some of its stylesheets in a different DOM implementation than the XML document given to the processor. Depending on the choice, the XSLT processor needs to invoke a different implementation of the same DOM API. This is the reason why our XSLT processor accesses the DOM implementation through a set of callbacks. These callbacks can be substituted at runtime depending on the DOM implementation that needs to be used.

While defining a callback based DOM API, we realized that there are too many callbacks. To facilitate, we subdivided them into two groups. The first group consisted only of calls from the DOM 1.0 specification. The second set consisted of core portion of the DOM 2.0 specification. Together this set is sufficient for XSLT. After dividing the callbacks in two groups we wrapped each of these groups in independent structures. Finally we wrapped both the structures into a single structure. Following is an abbreviated listing of the DOM 1.0 callback structure to provide an idea that how it looks like.

 
    /* This is only a partial listing. For complete listings please 
    download XDK from Oracle Technology network at 
    http://otn.oracle.com */
    typedef struct xdkdomcb
    {
           /************************* Miscellaneous ******************/
        xdkdomimp* (*createDOMImpl)(void *ctx);
           /******************** Interface Document ******************/
        xdkdomdtdnode* (*getDTD)(const xdkdomdocnode *doc);
        xdkdomimp* (*getImpl)(const xdkdomdocnode *doc);
        xdkdomelementnode* (*getDocumentElem)(const xdkdomdocnode*doc);
        xdkdomelementnode* (createElem)func(const xdkdomdocnode *doc, 
                const oratext *tagname);
        xdkdomattrnode* (*createAttr)(const xdkdomdocnode *doc, 
                const oratext *name, const oratext *value);
           /*********************** Interface Node ******************/
        const oratext* (*getNodeName)(const xdkdomnode *node);
        xdkdomnodetype (*getNodeType)(const xdkdomnode *node);
        const oratext* (*getNodeValue)(const xdkdomnode *node);
        void (*setNodeValue)(xdkdomnode *node, const oratext *data);
        xdkdomnode* (*getParentNode)(const xdkdomnode *node);
        xdkdomnodelist* (*getChildNodes)(const xdkdomnode *node);
        xdkdomnode* (*insertBefore)(xdkdomnode *parent, 
                xdkdomnode *newChild, xdkdomnode *refChild);
        xdkdomnamedmap* (*getAttr)(const xdkdomnode *node);
        xdkdomdocnode* (*getOwnerDocument)(const xdkdomnode *node);
           /*********************** Interface NodeList ***************/
        xdkdomnode* (*getNodeListItem)(const xdkdomnodelist *list, 
                ub4 index);
        ub4 (*getNodeListLength)(const xdkdomnodelist *list);
           /******************** Interface NamedNodeMap **************/
        xdkdomnode* (*getNamedItem)(const xdkdomnamedmap *map, 
                const oratext *name);
        xdkdomnode* (*setNamedItem)(xdkdomnamedmap *map, 
      xdkdomnode *newNode);
    } xdkdomcb;

2.2. Techniques for Capturing Object-Oriented Features of the DOM API in C

The header file defining these callback structures, provides a set of enumeration definitions and a class hierarchy diagram. We also document what we call a containment diagram. This diagram tells which node can contain the pointers to what other types of node. Finally we define a structure which contains the pointer to the structure of callbacks and the root document node to capture what we call as the DOM instance.

2.2.1. Enum Type Definition for Node Types and the Hierarchy Diagram

The hierarchy diagram tells that what types of nodes are dependent on what base node types. A pointer to a dependent node type can be cast to a pointer to the base type by using the C typecast operator. This can be safely done if the structure corresponding to derived node always contains the structure for the base node type as the first member.

Following is the listing of the hierarchy diagram and the enumeration types:

			    /* Hierarchy Diagram -----------------------------------
         Class diagram:                   Type name:

         Node \                           xdkdomnode
               +----Entity                xdkdomentitynode
               |----DocumentFragment      xdkdomfragnode
               |----EntityReference       xdkdomentrefnode
               |----Document              xdkdomdocnode
               |----CharacterData         xdkdomchardatanode
               |     \---Text             xdkdomtextnode
               |         \--CDATASection  xdkdomcdatanode
               |          \-Comment       xdkdomcommentnode
               |----Attr                  xdkdomattrnode
               |----ProcessingInstruction xdkdompinode
               |----Element               xdkdomelementnode
               |----Notation              xdkdomnotationnode
               +----DocumentType          xdkdomdtdnode

         DOMImplementation                xdkdomimp
         NodeList                         xdkdomnodelist
         NamedNodeMap                     xdkdomnamedmap
   -------------------------------------------------*/
   /* Node type (specific values set by DOM 1.0 spec) */
   typedef enum {
       ELEM     = 1, ATTR     = 2,
       TEXT     = 3, CDATA    = 4,
       ENTREF   = 5, ENTITY   = 6,
       PI       = 7, COMMENT  = 8,
       DOC      = 9, DTD      = 10,
       FRAG     = 11,NOTATION = 12
   } xdkdomnodetype;

As you can see from this listing, the xdkdomnode is the most basic type of node. All other nodes are derived from this (i.e. the structures defining the other nodes always have this as the first member). Given a pointer to the xdkdomnode, the XSLT processor can find out the actual type by making a call to DOM callback getNodeType. Depending upon the enumeration value returned, the XSLT processor will typecast this node to the actual node type. The basic node type, namely xdknodetype, and the derived types are only referenced through pointers and hence a DOM implementation does not need to make its definition public. Internally the DOM implementation can use it any way as it wants to with the basic understanding that any derived type can be cast to the base type.

2.2.2. Containment Diagram

Please note that the above was a Hierarchy Diagram. To understand what node refers to what other nodes, there is another diagram called Containment Diagram. This diagram shows that given a pointer to a node of a specific type, what other nodes can be obtained from it. The following diagram shows that given any node we can obtain the pointer to the document node which is like the root node of the DOM tree. This is because according to the W3C specification, every node must belong to a unique DOM and hence a unique document.

			    /* Containment Diagram ---------------------------
          Doc---+-----DocType
          ^     |_____DomImp
          |     |_____docElem_____(Elem)*
          |                         |
           -------------------------
   -------------------------------------------------*/

Just like the hierarchy diagram, this diagram is also only an aid in understanding the C DOM API. There are no members which can be directly accessed as all the node definitions are opaque.

2.2.3. DOM Instance

Unlike the object-oriented languages which provide a built in compiler mechanism to associate the vtables to an object instance, in C we need to define our own association. We did this by defining a new structure named xdkdomdoc. As you have seen previously, we have already defined a callback structure containing the full DOM API. Now all that is needed is a structure definition to associate this callback structure with a specific instance of the root of the DOM document. This is is done by the following structure which is public:

 
   typedef struct xdkdomdoc {
       xdkdomdocnode *doc; /*Pointer to the Document object. */
       xdkdomcb *domcb; /* These must be set at input and it is 
           a pointer to the callback struc containing DOM callbacks */ 
   }xdkdomdoc;

2.3. A Callback based Memory and I/O Management

When it comes to memory management and I/O, each platform and application has its idiosyncracies. The architecture provides a set of callback routines which the application can implement according to a paradigm specific to the platform or application. The XSLT processor will ultimately invoke only these callbacks for its memory management and I/O needs. There are only two memory management callbacks that the application needs to implement

 
         /* Application-defined memory callbacks.  Both functions must be provided! */
         typedef struct xmlmemcb
         {
            void *(*alloc)(void *ctx, ub4 size);
            void  (*free)(void *ctx, void *ptr);
         }xmlmemcb;

In order to keep the performance as high as possible, the XSLT processor makes only a few calls to these routines. This is ensured by allocating big chunks of memory and maintaining internal heaps within them.

Analogous to the callback based memory scheme, the architecture provides for a callback based stream API. The XSLT processor reads and writes text based input or output XML documents through these callbacks. This I/O API is listed as follows:

 
   typedef struct xmlstream {
      uword open(xmlstream * stream);
      uword write(xmlstream * stream, size_t len, oratext * buf, 
        size_t *written);
      uword read(xmlstream * stream, size_t maxlen, oratext * buf, 
        size_t *read);
      uword close(xmlstream * stream);
      void *userdata; /* user data to be accessible in callbacks */
   }xmlstream;

3. The API for the XSLT Processor

The API for the XSLT processor is simple. It accepts the pointer to two xdkdomdoc structures. The first pointer is used for a DOM instance of the stylesheet and the second is for a DOM instance of input XML document. If the XSLT processor is required to generate results as another DOM a third xdkdomdoc structure is needed to hold the result DOM instance. These three xdkdomdoc structures may share the same callbacks or may refer to different ones. XSLT processor interfaces with the DOM instances only through these callbacks.

Following is the listing of the XSLT API:

 
    xslctx *xdkxslinit(xdkdomdoc *stylesheet, xmlmemcb * memcb);
    uword xdkxslterminate(xslctx *xslSSctx);

    uword xdkxslsetoutputdomctx(xslctx *xslSSctx, xdkdomdoc *resctx);
    uword xdkxslsetoutputstream(xslctx *xslSSctx, xmlstream *stream);

    uword xdkxslprocessxml(xslctx *xslSSctx, xdkdomdoc *xmlctx);

3.1. Initializing and Terminating the XSLT Context

Some applications may be need to use the same stylesheet again and again. Our architecture provides an advantage to them. These applications can create and initialize an XSLT processor context for a given instance of the stylesheet DOM. Once created this context can be used over and over to process any number of input XML DOM instances. Terminating the context will free all the storage and the intermediate data which was generated for speeding up the transformation. A typical invocation by an application will look as follows:

 
    sctx = xdkxslinit(....); /* initialize the context */
    ...
    ... /* carry out all the transformations using this context */
    ..
    xdkxslterminate(sctx); /* terminate the context */

3.2. Selecting an Output Method

The application can set the XSLT processing context to generate the output as a text based stream or as another DOM instance. For generating the result as a DOM instance, another xdkdomdoc needs to be passed to the XSLT processor by xdkxslsetoutputdomctx. For generating the result as a stream, the stream callbacks are passed to the processor by xdkxslsetoutputstream.

Specifying the output method to be DOM based, provides the facility to transform the output DOM without the need to parse any thing inbetween. If the final output is only for storage in form of text, it is more efficient to select the stream based method.

3.3. Carrying Out the Processing

After initializing and selecting the output method an input XML document is transformed by the call to xdkxslprocessxml. This call takes the xdkdomdoc specifying the input XML to be transformed. During the execution of xdkxslprocessxml, the XSLT processor populates the result or streams the output by making calls to the callbacks. By the time this call returns back to the application, the output is already generated through these callbacks.

4. The Built-in, Default DOM Implementation

The C based XSLT processor is shipped as a part of the overall XML development solution by Oracle, namely XDK. The XDK has a whole range of Java, C and C++ based solutions for XML parsing, DTD validation, XSLT processing and XML Schema validation. The C specific part of the solution available as a set of headers and libraries which applications can use for development. As part of the XDK, a C DOM implementation is provided for applications which do not want or need to develop their own DOM implementations.

5. Using the XSLT Processor Inside the Database

We have discussed how this unique architecture makes the XSLT processor DOM implementation and platform independent. Now we will discuss how the Oracle database uses this architecture for an XML Schema aware DOM implementation.

5.1. A Brief Overview of XML Support in Oracle

Oracle provides built-in XML support for search, storage and access of the XML data. The huge amounts of data and enterprise critical nature of the database and its demand for scalability places constraints on the DOM implementation suitable for database engine. We will discuss the XML features supported in Oracle to get a feel for the complexity of the problem. The database sees its DOM implementation as an abstraction layer for XML data above the existing physical storage designed for scalability and performance in a server environment.

5.1.1. Storage

Oracle provides a datatype called XMLTYPE. The actual storage used in an XMLTYPE row or column is specified when creating the table. The data structure for that row or column can optionally be constrained by specifying an XML Schema during CREATE TABLE as well. For example:

 
      CREATE TABLE xml_order ( info XMLTYPE )
            XMLTYPE COLUMN info STORE AS OBJECT RELATIONAL
            XMLSCHEMA 'http://www.oracle.com/xdb/orderSchema.xsd'
            ELEMENT 'PurchaseOrder';

You may note the intent that the particulars of the storage mapping, or how relational data is (de)normalized across tables, is hidden under the XML abstraction.

5.1.2. Access

The XPath standard provides the access abstraction on top of the storage model. SQL usage of XPath is via the ExtractNode, ExistsNode and UpdateVal operators for XMLTYPE rows and columns.

 
         SELECT xml_order FROM orders WHERE 
            EXISTSNODE(xml_order, '/ship_to/state') > 0
            
         SELECT xml_order FROM orders WHERE 
            EXTRACTNODE(xml_order, '/ship_to/state').getString() = 'CA'

         UPDATE orders SET xml_order = SELECT poDocument.
            updateVal('//po[pono=1001]/lineitemlist',listVal) 
            FROM source_x;

The XPath abstraction hides the storage used by XMLTYPE from the application. The XMLTYPE column could be stored as a SQL object (with each element and attribute mapped onto rows and columns) or as a LOB in its original textual form. But when Oracle executes a query against an XMLTYPE column, the underlying storage is examined to see if the query can be rewritten into object-relational SQL. For example the query predicate above:

 
EXTRACTNODE(xml_order, '/ship_to/state').getString() = 'CA'

can be rewritten by the optimizer as:

 
xml_order.ship_to.state = 'CA'

5.1.3. Search

The result of a SQL query can be combined to produce the XML. This capability in the database server is similar to the capability supported by the XSQL servlet which runs inside the JServer. Using this kind of a feature, the Web and B2B applications can generate the XML based result ready to use in the application.

5.2. Requirements From the DOM Implementation Built Inside the Oracle Database

There are many constraints for a DOM implementation suitable for integration right into the database server. It must follow the coding guidelines, exception handling and memory management specific to the database engine. It must be populated on demand, use as little memory as possible and must be easy to clean up once its usage is over.

The most important requirement is for it to work as an abstraction layer. This abstraction layer hides all the internal implementation details from XML enabled components like the XSLT processor

This abstraction is achieved without sacrificing the memory usage or performance by many complex programming techniques. An xdkdomnode (as visible to the XSLT processor through the DOM API) may not even be a pointer to some in-memory structure. It is possible to interpret it as REF or as an index into a table depending on the programming techniques used

It is this abstraction and the level of indirection provided by the callback based architecture which makes our architecture of XSLT processor useful.

All these requirements are qualitatively different from what would be required for a standalone XSLT processor. A standalone processor may just do away with a simple, lightweight DOM implementation. Infact it may not even need to access the in-memory DOM through any API. Unlike the high performance and heavy weight counterpart for the database engine it can live with the C runtime library based memory management and I/O schemes.

The multi-threaded I/O schemes for database engine is very sophisticated.

5.3. Integrating XSLT into the Database Engine

First our attempt was only to make a call to the XPath related functionality from inside the database. During this process, we realized the lack of a standard test suite to ensure that various DOM implementations implement exactly the behavior expected by the XSLT processor. After solving that problem, the rest of the integration was straightforward. It was verified during performance profiling that there is only a minimal overhead in accessing the DOM API through the callbacks.

We also found a few pitfalls of the DOM API and devised solutions to overcome those. The most significant pitfall was the difficulty of bootstrapping the DOM implementation (i.e. a call to createDomImpl) when there are multiple DOM implementations.

6. Conclusion

It has become vital to integrate XML technologies right into a database server. Performance and integration requirements necessitate adapting the XML technologies to facilitate development in C. We solved the integration problems by developing a C based DOM API. We successfully used this API through a set of callbacks and platform independent architecture to integrate our common C XSLT processor in a server environment.

This architecture has many possible applications for C/C++ based development. A high performance XSLT processor which has a DOM and platform independent architecture is a natural choice for many applications.

Design and Development by deepX Ltd.