Abstract:
Disclosed is a method, apparatus and computer program for producing input to a transformation engine. A request is received to transform some data. It is determined whether the data is stored in a form permitting said data to be lazily constructed into a graph structure upon request by a client. If the data is stored is such a form, then it is determined whether to convert the stored data into a graph structure from which structure input to the transformation engine can be produced. In the affirmative the data is converted and input to the transformation engine is produced from this graph structure. Otherwise input to the transformation engine can be produced directly from the stored data.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to data transformation.  
       BACKGROUND OF THE INVENTION  
       [0002]     In order for a client process to be able to access and manipulate data, a client may request that a program (henceforth called a Data Access Service or DAS) convert the data into a hierarchical (or other graph) structure. WO0221291 discusses conversion of certain HTML files into tree structures such that the information contained within the tree structures may be used by other application programs. WO2004068320 discusses the conversion of HTML source into a tree structure such that that tree structure can be manipulated and transformed into a simplified HTML document.  
         [0003]     The conversion of other data formats (such as XML) into hierarchical format for the purpose of data manipulation is also known. U.S. Pat. No. 6,785,685 for example describes the parsing of XML data in order to build a DOM tree from which a dynamic data object (DDO) or extended data object (XDO) can be constructed. US2003041077 is another example of a patent that discuses the conversion of a source document into hierarchical form in order that the data contained within can be referenced. Other graph structures are known such as SDO and Microsoft&#39;s ADO (Microsoft is a registered trademark of Microsoft Corporation in the United States, other countries, or both).  
         [0004]     A simplified overview of the processing required to construct and access a graph is illustrated by  FIG. 1   a . Client  10  requests DAS  20  make a graph  30  out of data “data”. In the case of XML data, this may be achieved by a “Simple API for XML” (SAX) parser parsing the XML data to create events which DAS  20  can then use to build the graph  30 .  
         [0005]     As shown in  FIG. 1   b , when client  10  wishes to access a node within the graph  30 , client  10  makes such a request (via an operation) to the graph itself. The operation traverses the existing graph according to the supplied path until the requested node is identified and sends this back to client  10  for manipulation. US2004193575 discusses modelling of an XML document as a tree of nodes and navigating the tree of nodes to address parts of the XML document, where a destination node is as a result of a path expression. The reader is also referred to the discussion of XPath at http://www.w3.org/TR/xpath.  
         [0006]      FIGS. 1   a  and  1   b  address the situation where the complete graph is built immediately or “eagerly” when requested by the client. (For more detail, the reader should refer to ftp://www6.software.ibm.com/software/developer/library/j-commonj-sdowmt/ComSDO monj-SDO-Specification-v1.0.pdf.) This can however be processor intensive, especially when the client may never access every node in the graph.  
         [0007]      FIGS. 2   a  and  2   b  show a “lazy” solution. As before, client  50  requests that a DAS  60  converts some data “data” into a hierarchical format. A parser within the DAS parses the data to create an event pertaining to the root of the graph  70 . The graph then builds the root node from this event and creates and instance of a store  80  containing a buffer  90 . The graph&#39;s root node points to this store. The graph then adds the “data” into buffer  90 .  
         [0008]     Nodes are only built when a client specifically requests them. For example,  FIG. 2   b  shows that client  50  issues a request for node “b/c”. This request is received by graph  70  which points to store  80  containing buffer  90 . Store  80  parses the buffer to produce the events required by the graph in order to build the nodes in the path to the requested node. In the present case this produces graph  70 ′. Once the requested node has been created by the graph, this is then sent back to the client  50 .  
         [0009]     Thus a better performance can be achieved by building the graph on demand rather than by expending processing power up front.  
         [0010]     Use of a store to build a graph on demand is described in the EMF javadoc found at http://eclipse.org/emf/. The base technology is also described at: http://xml.apache.org/xerces2-j/xni-config.html  
         [0011]     In certain circumstances, a client may require the data to be in a different format to that in which it is currently stored. Numerous patents/patent applications discuss the concept of data transformation. See for example US2002073119, WO0073941 and US2004025117.  
         [0012]     Transformation of data can be achieved by a transformation engine. There are two logical operations a transformation engine might be performing, “transcription” (i.e. transcoding) in which the same logical information is expressed in a different “wire format”. In general a client would do this when it intends to forward the message to another agent. An example would be translating from English to French or XML to a legacy (or “cherished”) application format. The second which is a logical transformation, changes the logical meaning of the graph, for instance it might involve changing routing information in a message.  
         [0013]     The present invention is particularly concerned with the process for achieving data transformation when the data to be transformed is constructed lazily.  
       SUMMARY  
       [0014]     According to a first aspect, the invention provides a method for producing input to a transformation engine, the method comprising: receiving a request to transform some data; determining whether the data is stored in a form permitting said data to be lazily constructed into a graph structure upon request by a client and, if the data is stored in such a form, determining whether to convert the data into a graph structure from which structure input to the transformation engine can be produced and, in the affirmative, converting the data into a graph structure and producing input to the transformation engine from this graph structure and, otherwise, producing input to the transformation engine directly from the stored data.  
         [0015]     In other words the graph structure creation phase can be bypassed in certain circumstances.  
         [0016]     The data could, for example, be stored in a buffer.  
         [0017]     Preferably in order to determine whether to convert the stored data into a graph structure, it is determined whether there is a relationship between the type of data stored and the type of input to the transformation engine which is produceable from the graph structure.  
         [0018]     If it is determined that the data should be converted into a graph structure, this is preferably done by parsing the stored data to create a first generalised form of the data (e.g. events) and the graph structure is then preferably built from the first generalised form.  
         [0019]     In order to produce input to the transformation from this graph structure, the graph structure is preferably traversed in order to create a second generalised form of the data (e.g. events).  
         [0020]     In some circumstances it is possible to produce input to the transformation engine directly from the stored data. In such circumstances, the stored data is preferably parsed to create a generalised form (e.g. events) which can then be input into the transformation engine.  
         [0021]     Irrespective of whether the graph construction phase is bypassed, the input to the transformation engine will preferably be the same (assuming the original data is the same).  
         [0022]     According to another aspect, the invention provides an apparatus for producing input to a transformation engine, the apparatus comprising: means for receiving a request to transform some data; means for determining whether the data is stored in a form permitting said data to be lazily constructed into a graph structure upon request by a client; means, responsive to the data being stored in such a form, for determining whether to convert the data into a graph structure from which structure input to the transformation engine can be produced; means, responsive to a positive determination, for converting the data into a graph structure and for producing input to the transformation engine from this graph structure; and means, responsive to a negative determination, for producing input to the transformation engine directly from the stored data.  
         [0023]     It will be appreciated that the invention may be implemented in computer software. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0024]     A preferred embodiment of the present invention will now be described, by way of example only, and with reference to the following drawings:  
         [0025]      FIG. 1   a  illustrates the construction of a graph from data in accordance with the prior art;  
         [0026]      FIG. 1   b  shows, according to the prior art, how a client requests information from the graph constructed in  FIG. 1 ;  
         [0027]      FIGS. 2   a  and  2   b  illustrate a “lazy” solution to the construction of a graph and the provision of access to portions of that graph;  
         [0028]      FIG. 3  shows the components involved in data transformation in accordance with one embodiment of the present invention;  
         [0029]      FIG. 4  shows one way of achieving a data transformation; and  
         [0030]      FIGS. 5, 6   a ,  6   c  and  6   c  illustrated the componentry and processing of the present invention, in accordance with a preferred embodiment. 
     
    
     DETAILED DESCRIPTION  
       [0031]     As described above, a client uses a Data Access Service (DAS) to convert data into a form such that it is accessible to the client. This form is a hierarchical (or other graph) structure. (The hierarchical form used in accordance with a preferred embodiment of the present invention is SDO (Service Data Objects)).  
         [0032]     Creating a complete graph of a client&#39;s data can be processor intensive and this is wasteful if the client is unlikely to visit every node in that graph. Thus the solution is to use a lazily constructed graph where nodes in the graph are only created when a client requests access to those specific nodes.  
         [0033]     Whilst performance is gained in some respects, this solution can however cause performance problems when a client (either the same one or another client) requests transformation of the data into a different format.  
         [0034]     One possible (but less preferred) way of transforming lazily constructed data is explained with reference to  FIGS. 3 and 4 .  
         [0035]      FIG. 3  shows the components involved. For explanatory purposes only, the rest of the discussion will be in terms of XML.  
         [0036]     The function/purpose of components/data such as client  100 , DAS  130 , store  110 , buffer  130  and SAX Events  140  have all been discussed previously and so will not be discussed in any more detail. In addition to these components/data, an XSLT Transformation Engine  180  is provided. (XSLT is described at http://www.w3.org/TR/xslt.) This takes as input a “Transformation API for XML” (TrAX) Source  190  which is created by TrAX DAS  170  from graph  70 . When a TrAX Source is input to Engine  180 , the output (i.e. the transformed data) is placed into TrAX Result  195 . This result can then be returned to client  100  as a tree of data (or more loosely a graph of data which represents a tree structure).  
         [0037]     Note, TRAX is described at: http://java.sun.com/j2se/1.4.2/docs/api/javax/xml/transform/package-summary.html and http://xml.apache.org/xalan-j/trax.html  
         [0038]      FIG. 4  illustrates the processing that can take place (using the components described above) when a client requests that certain data is transformed into another format.  
         [0039]     The client (or another client) has already provided the XML DAS  130  with some XML data upfront (step  200 ). The XML DAS produces a lazily constructed graph from this data at step  210 . In other words, the DAS constructs a graph shell containing some functionality (allowing the graph to build itself) and in terms of nodes, only the root of the graph. The root is then set to point towards store  110 . Buffer  120  is then filled with the XML data.  
         [0040]     At some point, the client indicates that it requires the data to be transformed into another format. The client does this by asking the TrAX DAS for TrAX Source which can then be input into the XSLT Transformation Engine  180  (step  220 ). The TrAX DAS wraps the graph shell with an instance of a TrAX Source class (step  230 ). The client then asks the TrAX DAS for an empty TrAX Result (step  240 ). The client subsequently requests that the XSLT Transformation Engine fill in the empty TrAX Result using the TrAX Source (step  250 ). In other words, the client requests that output from the Transformation Engine is entered into the empty TrAX Result.  
         [0041]     At step  255  the transformation engine asks the TrAX source for a sequence of events to perform the transformation on. It should be observed that this is a generic step which would be applied whatever the nature of the graph, whether it be a truly disconnected graph or a graph which is underpinned by a store supplied by some other form of DAS, or as in this case an XML based store. At step  260  the TrAX Source asks the graph for its nodes. Because the data is constructed lazily, the graph references the store  110  to request these nodes (step  270 ). The store then parses the buffer  120  to generate events pertaining to the requested nodes (step  280 ) and returns the events to the graph (step  290 ). The graph uses the events to build itself (step  300 ). Having constructed itself, the graph can then return the nodes to the TrAX Source (step  310 ) and the TrAX source builds events from the nodes returned to it (step  320 ). These events can then be input as TrAX Source to the XSLT Transformation Engine (step  330 ). The output of the Transformation Engine (i.e. the transformed data) is used to complete a TrAX Result for return to the client (step  340 ).  
         [0042]     Thus it can be seen that the transformation of data, based upon a lazily constructed hierarchy and using the processing described above, makes for a a processor intensive task.  
         [0043]     The inventors of the present solution have realised that in certain circumstances it is possible to short-circuit the unwieldy process described with reference to  FIGS. 3 and 4 .  
         [0044]     The components and processing involved in a preferred embodiment of the present invention will now be discussed with reference to  FIGS. 5, 6   a ,  6   b  and  6   c.    
         [0045]     The first three steps are the same as those described with reference to  FIG. 4 . A client provides an XML DAS with some XML data (step  400 ). The XML DAS creates a graph shell (comprising some functionality enabling it to traverse and build itself and a root node) and also an XML store (step  410 ). The Client then asks TrAX DAS  300  for TrAX Source  370  (step  420 ). This is where the processing of the present invention, in accordance with a preferred embodiment, differs from that described with reference to  FIG. 4 .  
         [0046]     At step  430 , the TrAX DAS asks graph  320  whether it points to a store (graph querier  320 ). If the answer is yes, then the TrAX DAS determines from the graph whether this is an XML store (step  440 , graph querier  320 ) and whether the store has an up-to-date buffer (step  450 , graph querier  320 ). Note, history information is preferably stored by the graph regarding changes made to it by the client (note changes may be made by different clients, but one is referred to here for ease). If there have been no changes, then the buffer will be up-to-date.  
         [0047]     The above functionality is provided by the following components owned by graph  320 . A store determiner  340  determines whether graph  330  has a store. Store determiner  340  contains a store type determiner  350  which is used to determine whether any store contains an XML buffer. A store validity determiner  360  is used to determine whether any buffer is up-to-date.  
         [0048]     If the answer to any of the questions posed by steps  430 ,  440 ,  450  is no, then the short-cut of the preferred embodiment is not possible. Instead the processing discussed with reference to  FIG. 4  must be used, starting at step  230 .  
         [0049]     On the other hand, if the answers to steps  430 ,  440 ,  450  were all yes then at step  460  the client asks the TrAX DAS for an empty TrAX Result. The client then asks the XSLT Transformation Engine to fill the TrAX Result using TrAX Source (step  470 ). TrAX Source  370  asks (store querier  380 ) the store parser (not shown) to parse the buffer in order to create events (step  480 ) and these are the events that are then input directly to the XSLT Transformation Engine (step  490 ). As before output from the Transformation Engine is used to fill the TrAX Result (step  500 ).  
         [0050]     In this way, it is possible in certain circumstances to circumvent much of the processing described with reference to  FIG. 4 .  
         [0051]     In the particular embodiment described, there is a special relationship between the TrAX DAS and the XML DAS that means that the events generated by parsing the buffer are suitable for direct input into the transformation engine and there is no need to create events from a hierarchical form of the data for input to the transformation engine.  
         [0052]     It should be appreciated that whilst preferred embodiment has been described in terms of XML, the invention is not limited to such. The invention can apply to any environment in which data is normally lazily constructed into a graph structure on request by a client where the events produced by a store parser when parsing stored data are suitable for direct input to a particular transformation engine. In such situations these events can be provided to the transformation engine instead of creating a graph structure first and then using this form to generate appropriate events for input to the transformation engine.