Method and system for storing and querying of markup based documents in a relational database

[0002] 1. Field of the Invention

[0003] This invention relates in general to database management systems performed by computers, and in particular to an optimized method and system for decomposing and storing of markup based documents, such as XML documents, in a relational database. This allows easy and fast subsequent retrieval of data from the database in the XML format and reconstruction of the XML document.

[0004] 2. Description of Related Art

[0005] Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. RDBMS software using a Structured Query Language (SQL) interface is well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Organization (ANSI) and the International Standards Organization (ISO).

[0006] Extensible Markup language (XML) is a standard used for representing data on the Internet in a hierarchical data format and for information exchange on the World Wide Web. Presently, there is a need for a an optimized method and system for serializing and storing of XML documents in a relational database, which preserves the structure of the XML document for subsequent querying of XML document components.

[0007] An XML document consists of nested element structures, starting with a root element. An XML document is tree-structured, with each node in the tree representing an element being described by a name. Data describing an element can be in the form of attributes or sub-elements. An “id” attribute uniquely identifies an element within an XML document and can be used to reference the element from another element. An XML document uses tags to describe the type of data following the tag. Thus, an XML document is self-describing because the data can be interpreted by a remote user without an input from the creator of the document.

[0008] There are numerous conventional software products used for transferring data contained in an XML document into a database. They consist of modules capable of decomposing the XML document and storing it in a database. For querying the database to obtain the XML data, conventional products usually use an XML query to search the contents of the XML document for elements or attributes. Moreover, most such products store data in an object-relational database. Some conventional products use structural serialization which is performed on the basis of the hierarchical structure of XML documents. In the structural serialization of XML documents the tree structure of an XML document is mapped to a set of relational tables. However, this often leads to a large number of tables for even a simple XML document. Moreover, when the serialization is carried out using the structural serialization method, the queries usually need to have some kind of mapping information in order to obtain valid results, since there is a need to perform a mapping between an XML schema and a relational database schema.

[0009] While there have been various techniques developed for decomposing and storing of markup based documents, such as XML documents, in a database, there is a need for a simple, optimized and generic method for serializing and storing of markup based documents in a relational database, which allows easy and fast subsequent retrieval of data from the database in the original format and reconstruction of the document. Moreover, such method has to be independent of the hierarchical structure and structural complexity of the stored document.

[0010] The foregoing and other objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments, which makes reference to several drawing figures.

[0011] One preferred embodiment of the present invention is a computer-based markup serialization method for transferring data contained in a markup based document, such as an Extensible Markup Language (XML) document, into a relational database stored in an electronic storage device having a database management system. It is used for easy subsequent retrieval of data from the database in the XML format and reconstruction of the XML document. The method decomposes the document according to basic markup types of the documents' data components and stores the decomposed document in a set of markup tables created in the database, one markup table for each basic markup type, thereby preserving the hierarchical tree structure, parent-child order, and components of the document. The basic markup types of an XML document are ATTRIBUTE, CDATA_SECTION, COMMENT, DOCUMENT_FRAGMENT, DOCUMENT, DOCUMENT_TYPE, ELEMENT, ENTITY, ENTITY_REFERENCE, NOTATION, PROCESSING_INSTRUCTION and TEXT. For querying the database markup tables the method uses SQL queries to retrieve the XML document components in the XML format.

[0012] Another preferred embodiment of the present invention is a system implementing the above-mentioned method embodiment of the present invention.

[0013] Yet another preferred embodiment of the present invention includes a computer usable medium tangibly embodying a program of instructions executable by the computer to perform method steps of the above-mentioned method embodiment of the present invention.

[0014] Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

[0015] FIG. 1 illustrates a computer hardware and software environment enabling markup serialization, according to the preferred embodiments of the present invention;

[0016] FIG. 2 illustrates a flowchart of the markup serialization software, according to the preferred embodiments of the present invention;

[0017] FIG. 3 illustrates a flowchart of the module used for the markup based document decomposition, according to the preferred embodiments of the present invention; and

[0018] FIG. 4 illustrates a flowchart used for querying the database markup tables, according to the preferred embodiments of the present invention.

[0019] In the following description of the preferred embodiments reference is made to the accompanying drawings, which form the part thereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural and functional changes may be made without departing from the scope of the present invention.

[0020] The present invention discloses a system, method and program storage device embodying a program of instructions executable by a computer to perform the method of the present invention for serializing, storing and querying of a markup based documents, such as Extensible Markup Language (XML) documents, in a relational database. The method and system may be used in a distributed computing environment in which two or more computer systems are connected by a network such as World Wide Web, including environments in which the networked computers are of different type.

[0021] FIG. 1 illustrates an exemplary computer hardware and software environment usable by the preferred embodiments of the present invention, including a console 102 having one or more conventional processors 104 executing instructions stored in an associated computer memory 105, and having a console terminal 108. The operating memory 105 can be loaded with instructions received through an optional storage drive or through an interface with a computer network.

[0022] The processor 104 is connected to one or more electronic storage devices 106, such as disk drives, that store one or more relational databases. They may comprise, for example, optical disk drives, magnetic tapes and/or semiconductor memory. Each storage device permits receipt of a program storage device, such as a magnetic media diskette, magnetic tape, optical disk, semiconductor memory and other machine-readable storage device, and allows for method program steps recorded on the program storage device to be read and transferred into the computer memory. The recorded program instructions may include the code for the method embodiment of the present invention. Alternatively, the program steps can be received into the operating memory from a computer over the network.

[0023] Operators of the console terminal 108 use a standard operator terminal interface (not shown), such as IMS/DB/DC, CICS, TSO, OS/2 or other similar interface, to transmit electrical signals to and from the console 102, that represent commands for performing various tasks, such as search and retrieval functions, termed queries, against the databases stored on the electronic storage device 106. In the present invention, these queries conform to the Structured Query Language (SQL) standard, and invoke functions performed by a DataBase Management System (DBMS) 112 located at the console 102, such as a Relational DataBase Management System (RDBMS) software. In the preferred embodiments of the present invention, the RDBMS software is the DB2 product, offered by IBM for the AS400, OS390 or OS/2 operating systems, the Microsoft Windows operating systems, or any of the UNIX-based operating systems supported by the DB2. Those skilled in the art will recognize, however, that the present invention has application to any RDBMS software that uses SQL, and may similarly be applied to non-SQL queries and probably even to non-relational databases.

[0024] FIG. 1 further illustrates a software environment enabling preferred embodiments of the present invention. In the system shown in FIG. 1 the console 102 further includes a markup serialization software 110 of the present invention. The computer-based markup serialization software 110 incorporates a method for transferring data contained in a markup based document, such as an XML document, into a relational database stored in an electronic storage device having a database management system. It is used for easy subsequent retrieval of data from the database in the original document format, such as the XML format, and reconstruction of the document. Although the description of the preferred embodiments of the present invention will be based on XML documents, the present invention is applicable to any type of markup based documents.

[0025] The preferred method embodiment of the present invention decomposes the XML document according to basic markup types of XML documents' data components and stores the decomposed XML document in a set of markup tables created in the database, one markup table for each basic markup type, thereby preserving the hierarchical tree structure, parent-child order, and components of the XML document. The basic markup types are ATTRIBUTE, CDATA_SECTION, COMMENT, DOCUMENT_FRAGMENT, DOCUMENT, DOCUMENT_TYPE, ELEMENT, ENTITY, ENTITY_REFERENCE, NOTATION, PROCESSING_INSTRUCTION and TEXT. For querying the database markup tables the method preferably uses SQL queries to retrieve the XML document components in the XML format.

[0026] The method preferably uses a hybrid approach for querying data, utilizing functions found both inside and outside of the relational database and RDBMS engine. The querying of the XML documents in the preferred embodiments of the present invention is preferably performed using SQL queries on the relational database data. The method preferably uses the RDBMS engine in order to perform fast searches. Formatting or transformation of relational data into XML data has to be carried out in a utility program created outside of the relational database system, in a middleware component.

[0027] The markup serialization technique of the present invention is not based on the hierarchical structure of XML documents, as are some conventional products. The markup serialization of the present invention is the serialization carried out on the basis of available markup types of the markup based document. Presently, there are twelve basic markup types of XML document components and all are preserved in the relational database. Thus, the preferred embodiments of the present invention preserve the hierarchical tree structure and parent-child order of a markup based document, as well as the character data and attribute values found in that document. Moreover, they preserve the document type declarations and physical structure of the document, such as entity use, CDATA sections and document encodings.

[0028] In the preferred method of the present invention the serialization and storage of an XML document is accomplished according to the twelve different basic types of markup that an XML document can have. These different types of markup are: ATTRIBUTE_NODE, CDATA_SECTION NODE, COMMENT_NODE, DOCUMENT_FRAGMENT_NODE, DOCUMENT_NODE, DOCUMENT_TYPE_NODE, ELEMENT_NODE, ENTITY_NODE, ENTITY_REFERENCE_NODE, TEXT_NODE, NOTATION_NODE and PROCESSING_INSTRUCTION_NODE. Each XML document has pre-existing markup tags describing the markup type of the data following the tag.

[0029] The serialization of an XML document on the basis of document markup types (markup serialization) rather than on the basis of document structure (structural serialization) offers several key advantages. Since there are only twelve basic markup types, maximum number of relational tables required in the markup serialization is twelve, irrespective of the complexity of the XML document. However, in the structural serialization of XML documents the tree structure of an XML document is mapped to a set of relational tables which often leads to a large number of tables for even a simple XML document. Moreover, because the markup serialization does not produce a large number of tables, querying the data produced by the markup serialization is usually faster and less complex. Another advantage of the markup serialization is that querying and searching through a serialized form of an XML document obtained through the markup serialization is simpler, since there is no need to perform a mapping between an XML schema and a relational database schema. When the serialization is carried out using a structural serialization, the queries usually need to have some kind of mapping information to obtain valid results.

[0030] In the preferred embodiments of the present invention the parsing and storing of an XML document is carried out by first serializing the XML document, while preserving the parent-child relationship between elements, and then storing the data into a series of relational database markup tables. This markup serialization and storage of an XML document X can be carried out by an algorithm such as the algorithm described below.

[0031] In this algorithm of the preferred embodiments of the present invention, line 2 initializes a pointer XTREE to a root of an XML parse tree. The XML parse tree is obtained by parsing the XML document in step 3, using a conventional XML parser routine, such as IBM XML4J parser, or a user-supplied parser utility. Once an XML parse tree is available and pointed to by the variable XTREE, twelve tables, one for each type of markup, are created in step 4 by calling the function CREATE_MARKUP_TABLES( ). Step 5 carries out the serialization of the XML parse tree pointed to by the variable XTREE, and populates the relational tables, created in step 4, with serialized data. The serialization creates the serialized data by traversing the XML parse tree node by node and collecting information about each node. Variable ‘ID’ is a global variable that is common to all functions described in this algorithm. It is used to generate a unique id for each node in the XML parse tree obtained by parsing the XML document. During the serialization, the markup type of each node is identified by the preceding markup tag and each node is assigned a unique node id number, which represents the position of that node in the XML node hierarchy. Next, the information about each node is stored in a corresponding markup table, according to the node's markup type.

[0032] The function CREATE_MARKUP_TABLES creates twelve relational database tables, one table for each type of markup that can occur in an XML document. In the present invention the tables created by the function CREATE_MARKUP_TABLES are named as: ATTRIBUTE, CDATA_SECTION, COMMENT, DOCUMENT_FRAGMENT, DOCUMENT, DOCUMENT_TYPE, ELEMENT, ENTITY, ENTITY_REFERENCE, NOTATION, PROCESSING_INSTRUCTION, and TEXT. They correspond to the nodes of each markup type that the XML document parse tree can have: ATTRIBUTE_NODE, CDATA_SECTION_NODE, COMMENT_NODE, DOCUMENT_FRAGMENT_NODE, DOCUMENT_NODE, DOCUMENT_TYPE_NODE, ELEMENT_NODE, ENTITY_NODE, ENTITY_REFERENCE_NODE, TEXT_NODE, NOTATION_NODE, PROCESSING_INSTRUCTION_NODE.

[0033] In the preferred embodiments of the present invention each record in the twelve markup tables contains information about a node in the XML parse tree of the XML document. Each node will appear only once in any one of the tables used to store the XML document, because they are stored in the tables according to the markup type. Each record of the twelve markup tables contains the following columns that describe a node: PID representing id of the parent node, ID representing id of this node, NAME of the node or element, and VALUE represented by this node. There is no need for the markup type column in any table rows, because the markup type of each node corresponds to the markup of the table, and is the same for all the rows in a given table, since any of the twelve markup tables is used to store information about nodes of only one type.

[0034] The root element of the XML document is stored in the ELEMENT table and always has an id=0. The children elements of the root element are also stored in the ELEMENTS table. An element node may have its attributes, which are defined as attribute nodes and stored in the ATTRIBUTE table. The pid of each ATTRIBUTE record points to the id of the element stored in the ELEMENT table record which contains that element record. Similarly, information about data with other types of markup are set up in other markup tables. Thus, the entire XML document is stored in its serialized format along with additional information (id and pid) necessary to recreate the original XML document or its part.

[0035] In the preferred embodiments of the present invention the population of the twelve markup tables created for the XML document X, performed in step 5 above and defined as POPULATE_TABLES(ID, XTREE), is carried out by the algorithm described below.

[0036] The function POPULATE_TABLES (pid, node) takes the pid representing the id of the parent of a node and inserts this and all the other information about the node into one of the twelve markup tables, depending upon the markup type of the node, as shown in steps 2 to 25. In each pass, the global variable ID is incremented to create the unique id of the node. Steps 26 through 31 handle attributes of the node, if they exist, by recursively executing the same routine. Similarly, steps 32 to 34 handle the children of the node by executing the same routine recursively. This function will serialize an entire XML document given a node that points to a parse tree of an XML document. In this case, as shown in step 5 of the main function SERIALIZE_XML_DOCUMENT(X) above, the function is defined as POPULATE_TABLES(ID, XTREE), where ID=0 as set in step 1, and ‘node’ has the value XTREE.

[0037] In the preferred embodiments of the present invention function INSERT_DATA_INTO_TABLE is a function that inserts data about each node into the specified markup table. The first argument of this function is the name of the markup table into which the data is to be inserted. Other arguments are: PID, which is an id of the parent node, ID of this node, NAME, which is the name of the node, and VALUE, which is the value represented by this node.

[0038] Since an XML document may not have all twelve types of markup, some of the twelve created markup tables may remain empty. Often an XML document contains only four types of markup: elements, attributes, comment and processing instructions. In this case, only four tables will be populated and the remaining eight tables will go unused and may be deleted.

[0039] Once the XML document is stored in the database, it is possible to use other functions of the present invention, namely, querying of the database markup tables to obtain certain requested XML data, and reconstruction of the original XML document partially or in its entirety. In the preferred embodiments of the present invention the querying of the previously created markup tables to obtain XML data from the original XML document is preferably performed using the SQL SELECT syntax and is accomplished as follows. An XML result set is produced in two stages, and is made up of one or more XML elements. Since the markup tables are preferably relational tables, the first stage is the SQL Querying stage which includes querying of the twelve markup relational tables with XML data to obtain a relational result set. The second stage is the Result Set Transformation stage which transforms the relational result set, obtained in the first stage, to obtain an XML result set. The SQL Querying stage is preferably accomplished using the functionality available inside the RDBMS engine. The Result Set Transformation stage is preferably performed in a middleware component, outside of the RDBMS engine.

[0040] The first stage, SQL Querying, selects the elements defined by the user-defined markup type and firstly determines which one of the twelve types of markup a user is looking for. For example, if the user is looking for a node of the markup type ELEMENT_NODE and with node name <NAME>, the following SQL query can be used:

[0041] Similarly, if the user only wants to see the elements which have node name <NAME> and the node value ‘Albert’, the following query can be used:

[0042] The entire original XML document can be recreated using the query:

[0043] Q3) SELECT* FROM elements;

[0044] Each of these exemplary queries produces a relational result set of data that will be transformed into an XML result set in the next stage. The Result Set Transformation stage of the present invention may expect the relational result set to be in a certain format. In the present invention, as described above, the relational result set always has to contain columns pid, id, name, and value of the element, and has to be ordered by the column id. Therefore, in this implementation of the present invention the queries Q1, Q2, Q3 have to be substituted with queries Q4, Q5, and Q6 to conform to this requirement.

[0045] In the present invention the query can contain joins, relational operators and any other SQL syntax supported in a given RDBMS, provided that the result set always contains pid, id, name, and value of element of the XML result set, and is ordered by id. An example of a more complex query is given below.

[0046] The second stage, the Result Set Transformation of a relational result set to an XML result set, is carried out by using the algorithm described below.

[0047] Given a relational result set ‘R’ obtained by an SQL query, as described above, the function RELATIONAL_TO_XML_TRANSFORMATION(R) will convert the relational result set into an XML result set. Lines 2 to 4 iterate over each row Ri of the relational result set R to obtain each element (Xi) of the XML result set X. The algorithm steps through the relational result set one row at the time and moves downwards, getting that row's descendant element, attributes, text, etc. For each row or element a name and value column data are used to reconstruct the XML element. Then, a function recursively launches queries to get name and value of all descendant elements of the XML element, starting with the id of the element row of step 2. As shown below, in step 4 the SQL queries are executed to obtain and format attributes of each descendant, by querying the ATTRIBUTE table with the pid of the XML element. The function may query other tables, if needed. Thus, SQL queries may be executed to format text section of each descendant by querying the TEXT table with the pid of the XML element. It should be noted that while moving downwards on the relational result set, the function may encounter element rows which have already been processed as descendants or element-rows that came earlier. Thus, the function preferably keeps track of and ignores the rows which would create erroneous elements in the XML result set, such as duplicates or misplaced elements.

[0048] The function CREATE_XML_ELEMENT_FOR_ROW is called in line 3 to create an XML element of the XML result set. Then, the function GET_DESCENDANT_XML_ELEMENTS_OF_ROW is called in line 4 to get the descendant XML elements of the element Xi obtained in line 3. The results from function calls in lines 3 and 4 are combined in step 4 to get the complete XML element of the XML result set.

[0049] Finally, when the step 2 iterating over all the rows of the relational result set R is completed, the XML result set X is returned in line 5.

[0050] The function CREATE_XML_ELEMENT_FOR_ROW(Ri.id ,Ri.name, Ri.value) is in the preferred embodiments of the present invention defined as shown below.

[0051] The function CREATE_XML_ELEMENT_FOR_ROW takes the name and value of an XML element and tags it accordingly to produce properly tagged XML data. In line 6, the function GET_ATTRIBUTES_FOR_ELEMENT is called to get all attributes of the element specified with the row ‘row’. Lines 5 through 7 combine name, data, and attributes of an XML element to produce a single complete XML element XE, which is in XML format.

[0052] The function GET_ATTRIBUTES_FOR_ELEMENT(row.id) queries the “ATTRIBUTE” markup table to get all the attributes of the element pointed to by the id ‘row.id’. These attributes are then properly formatted in line 5 and returned to the caller in line 6.

[0053] GET_DECENTDANT_XML_ELEMENTS_OF_ROW(row.id) is a recursive function similar to the CREATE_XML_ELEMENT_FOR_ROW(row.id). This function gets XML formatted data from a row that also includes descendant (child) elements.

[0054] Some preferred embodiments of the present invention, like other good XML processors, are also able to query filter element(s), based on an element path expression. The algorithm presented above reaches each element by traversing its path from the root element. Hence, when needed to query filter element(s), a modification of the algorithm presented above is used. It keeps track of a path of each element and filters out the specified element from the result node, when requested in the filtering query.

[0055] The present invention provides simple and fast decomposition and querying, independent of the structural complexity of an XML document. Number of required relational tables is small and independent of the structural complexity of an XML document. In the present invention simpler querying is obtained by using SQL queries and RDBMS, since XML schema does not have to be mapped with the corresponding relational shema, and querying is fast since there is a small number of markup tables.

[0056] The flowchart of a computer-based markup serialization method used for transferring data contained in any type of a markup based document into a relational database is illustrated in FIG. 2. Step 202 is used for decomposing the markup based document according to basic markup types of the documents' data components. Storing step 204 performs storage of the decomposed document in a set of markup tables created in the database, one markup table for each basic markup type.

[0057] The decomposing step 202 is shown in detail in FIG. 3. It includes a step 302 for parsing the document to create a nested parse tree, and a step 304 for serializing the parse tree by traversing the path of each node from the root, wherein a basic markup type of each node is identified by a markup tag in the document describing the markup type of a data component following the markup tag, and wherein each node is described by a name, attributes, and an id representing the position of the node in the parse tree. In the storing step 204 each node data is stored in a record of at least one markup table according to the node's markup type, and each record contains a node id, node name (NAME), node parent (PID), and node data value (VALUE) columns.

[0058] FIG. 4 illustrates steps used for querying the database markup tables. Step 402 creates an SQL query used to retrieve the XML document components in the XML format. The query is used in two stages, needed for reformatting a result set into the XML format. Step 404 is used in a SQL querying stage and utilizes the RDBMS for querying the markup tables to obtain a data result set. Step 406 is used in a result set transformation stage for re-formatting the data result set into an XML data result set. The querying step can be used to create a reconstructed XML document by selecting all elements from the markup tables in the query created in step 402.

[0059] The present invention may provide UNIX, Windows and other platform support. It will preferably be used for developing applications for DB2 machines. The present invention works with any of the IBM database manager products, such as DB2 for VM/VSE, DB2 for OS/390, DB2 for AS/400, DB2 Common Server, DB2 Universal Database. However, the technology may be applied to any other database manager products, such as Oracle, Informix, Sybase, SQL Anywhere, and Microsoft SQL Server, and other relational and possibly non-relational products.

[0060] The foregoing description of the preferred embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.