System and method for synchronizing and/or updating an existing relational database with supplemental XML data7031956Abstract A system and a method for synchronizing and updating a relational database with supplemental data in which the relational database has a set of tables defined by a relational schema. The supplemental data preferably comprises data in a tagged format having a document-type definition representative of the relational schema and is represented in a document object. The system and method preferably ensure record-by-record updating and synchronization of the relational database with the at least one proposed data update by receiving at least one proposed data update from a source external to the relational database; and propagating the received at least one proposed data update into the relational database. In this matter, the compliance with both the relational database relational schema and the tagged data document type definition is ensured without requiring reloading existing data in the relational database. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
The task of developing a relational schema for XML documents requires understanding the components of, and relationships within, such documents. A DTD defines a structure for XML documents that can be seen as an ordered graph composed of element type declarations. A DTD has the following properties (also referred to herein as data and/or content particles): Grouping: Within an element type definition, elements that are associated within parentheses participate in a grouping relationship, and are defined as a group. This relationship can be further classified as sequence grouping (wherein the elements are separated by a comma ',') or choice grouping (wherein the elements are separated by a vertical bar '|') according to the operator used as a delimiter in the grouping. Nesting: An element type definition provides the mechanism for modeling relationships that can be represented structurally as a hierarchy of elements. These relationships are referred to as a nesting relationship (a structural view can be chosen to avoid having to choose particular semantics for all such relationships). Schema Ordering: The logical ordering among element types specified in a DTD. For example, line one of the DTD in Example 1 specifies that in a book, a booktitle precedes a list of authors (or an editor). Existence: In a DTD, an element type with no content declares the existence of an element with no structure or value for that element type. This kind of virtual element is declared so that attributes can be defined for unique properties of the element or for element referencing relationships. Occurrence: Occurrence indicators (i.e., "?", "*", and "+") indicate optional occurrence or repetition of a content particle in an element definition. For example, in Example 1, the grouping (book|monograph) can appear zero or more times in an editor element which is indicated by the "*" following this grouping in line eight of the DTD in Example 1. Element Referencing: Elements reference one another using attributes of type ID and IDREF(s). For example, in Example 1, contactauthors has an element reference relationship with author. These properties and relationships illustrate that a DTD not only defines element types for conforming XML documents, but also provides valuable information about the structure of an XML document and relationships between its elements. Besides that, while the DTD specifies a schema ordering between element types thereof, XML documents also have a physical ordering, or data ordering, of data elements. The challenges of mapping a DTD to a relational database model arise from a mismatch between (1) types of properties and relationships embedded in DTDs and (2) those modeled by relational database models. Turning to the task of loading XML data (as validated by a DTD) into a relational database, the prior art in database systems must be considered. Database systems are traditional, well-known tools for managing data. After many years of development, database technology has matured and contributed significantly to the rapid growth of business and industry. Relational database systems are a proven technology for managing business data and are used everywhere by various sizes of companies for their critical business tasks. Commercial relational database products embody years of research and development in modeling, storage, retrieval, update, indexing, transaction processing, and concurrency control, and continue to add capabilities to address new kinds of data, such as multimedia. With more and more data flowing in XML formats, there have been attempts to extend prior art relational database systems to accommodate XML data. Such an approach has avoided re-inventing database technology to suit XML data but, more importantly, takes best advantage of the power of relational database technology and the wealth of experience in optimizing and using the technology. There have been several problems to overcome in bringing XML data into a relational database for management, including defining a relational schema for the XML data, loading the XML data into a relational database, and transforming XML queries (whether formulated in extensible stylesheet language [XSL], XML Query Language [XML-QL] or other XML query standards) into meaningful structured query language [SQL] queries. Prior attempts to solve these problems have fallen short of an efficient and, preferably automatic, way to import XML data into a relational database schema. Current industry enterprise database management system (DBMS) vendors, such as DB2 and Oracle 8i, provide XML extensions for bringing XML data into a relational database. However, these methods are far from automatic. These vendors require users to manually design the relational schema for a given DTD and to define the mapping between the DTD and the user-designed schema for the loading of XML documents. While this manual approach can be straightforward, and these vendors provide tools to assist the user, users must be very familiar with the XML data, the DTD therefor and the particular database system used. In addition, the prior art approach only works well for generating a relatively simple relational schema, and is not effective or efficient when the data contains complex relationships between tables. It is most appropriate for a small number of short or familiar DTDs. The known approach also requires experts on both XML and relational techniques. For more complex DTDs and a more robust relational schema, the manual approach becomes more difficult and requires specialized expertise. The common existence of non-straightforward relational database schema cases requires a more advanced approach to generating the relational schema and defining the load mapping definition. Other attempts to conceive a method that automatically loads XML data into a relational database have also proven to be of limited success. In accordance with these failed attempts, the user is required to either mine XML documents or to simplify the DTD. In either case, semantics captured by the DTD or XML documents are lost, e.g., how elements may be grouped within the data or as defined by the DTD, and how to distinguish between DTD specific symbols, such as * and +, etc. Other prior art attempts to load XML data into a relational database schema include one method by which a large amount of data is placed into relational databases by creating a relational data schema and applying data mining over a large number of the same type of XML documents, and then abstracting a relational data schema out of them. Then, the data is loaded into the relational tables. For parts that cannot fit into the relational table schema, an overflow graph is generated. Others have done benchmark testing on a relational schema generated out of XML data by four variations of a basic mapping approach—but this work does not consider or does not require a DTD. However, one known form of benchmark testing that does consider a DTD was performed by Shanmugasundaram et. al. who investigated schema conversion techniques for mapping a DTD to a relational schema by giving (and comparing) three alternative methods based on traversal of a DTD tree and creation of element trees. This process simplified the DTDs and then mapped those into a relational schema. While this approach also works with simple XML data structures, portions of the structure, properties and embedded relationships among elements in XML documents are often lost. Instead of bringing the semi-structured data into the relational model, there are other approaches to bring the XML data into semi-structured, object-oriented, or object-relational database management systems (DBMS). Some commercial relational DBMSs, e.g., IBM's DB2 and Oracle, have begun to incorporate XML techniques into their databases, e.g., IBM Alphaworks visual XML tools, IBM DB2 XML Extender, and Oracle 8i. Recently IBM's Alphaworks proposed a new set of visual XML tools that can visually create and view DTDs and XML documents. In its tools, IBM has proposed the idea of breaking DTDs into elements, notations, and entities that use components grouped with properties sequential, choice, attribute, and relationship and with repetition properties to construct DTDs. Tools to do XML translation and XML generation from SQL queries are provided. However, a method by which to load the XML data into relational tables was not addressed in this prior art. The DB2 XML Extender can store, compose and search XML documents. Document storing is accomplished in two ways. First, the XML document is stored as a whole for indexing, referred to as way of storing the XML document as an XML column. Second, pieces of XML data are stored into table(s), referred to as XML collections. Oracle 8i is an XML-enabled database server that can do XML document reading and writing in the document's native format. An XML document is stored as data and distributed across nested-relational tables. This XML SQL utility provides a method to load the XML documents in a canonical form into a preexisting schema that users manually (and previously) designed. Other problems have arisen with the prior art regarding propagation of updates to an XML database and/or a relational database. In many cases, the relational database has been required to be completely rebuilt from all of the previous updates or, alternatively, a single update to the data requires the relational database to be rebuilt. Much of the prior efforts focused on the implementation issues of using database triggers and assignment of identifications for each element, as well as other sets of updates using XQuery. These prior attempts have been unable to solve several issues. First, these previous attempts at XML updates can include XML data changes that could violate constraints inherent in or defined in the DTD. Second, the issue of how such violations would be addressed in the relational correspondence with the RDBMS have not been perfected. Third, the previous attempts at implementation of XML updates does not support the order properties in the DTD. Fourth, the previous attempts at updates cannot move an element into different places in the XML database. SUMMARY OF THE INVENTION Mapping and Loading Overview According to the invention, a relational schema definition is examined for XML data, a relational schema is created out of a DTD, and XML data is loaded into the generated relational schema that adheres to the DTD. In this manner, the data semantics implied by the XML are maintained so that more accurate and efficient management of the data can be performed. Starting with a DTD for an XML document containing data (rather than analyzing the relationships between the actual elements of the XML data), all of the information in the DTD is captured into metadata tables, and then the metadata tables are queried to generate the relational schema. Then, the data contained in the XML document can be loaded into the generated relational schema. This method can be described by three broad steps: First, the DTD is stored as metadata (i.e., a transformation and/or recasting of the data contained in the DTD) in tables—i.e., the metadata is used to describe the information of the DTD associated with the XML documents. This approach provides flexibility to manipulate the DTD by standard SQL queries. Second, a relational schema is generated from the metadata stored in the metadata tables. This step provides additional flexibility in that, although the relational schema can be directly mapped from the metadata tables according to the invention, the metadata tables can also be queried to do optimizing or restructuring on the metadata tables representative of the XML data structure stored in the DTD. Third, data contained in the XML document is loaded into the tables as defined by the relational schema (which is generated in the previous step), by using the associated metadata tables. According to the invention, the inventive metadata-driven approach includes the following beneficial characteristics: For Storing: All of the information contained in the DTD is captured in the metadata tables. It is anticipated that the XML document and the DTD can be reconstructed from the relational data and metadata as needed. For Mapping: The generated relational schema is rich in relationships that are useful in processing queries. For Loading: Mappings between the XML document and the final relational schema are captured in the metadata tables. It is contemplated that the relational data can be synchronized with XML data, which means whenever there is a data update in the relational data, the effect is also reflected in the XML data, and vice versa. Metadata Extraction and Storage In one aspect, the invention relates to a method for generating a schema for a relational database corresponding to a document having a document-type definition and data complying with the document-type definition. The document-type definition has content particles representative of the structure of the document data including one or more of the following content particles: elements, attributes of elements, nesting relationships between elements, grouping relationships between elements, schema ordering indicators, existence indicators, occurrence indicators and element ID referencing indicators. The method also contemplates loading the data into the relational database in a manner consistent with the relational schema. The method comprises the steps of: extracting metadata from the document-type definition representative of the document-type definition; generating the schema for the relational database from the metadata, wherein at least one table is thereby defined in the relational database corresponding to at least one content particle of the document-type definition via the metadata, and at least one column is defined in each of the at least one table corresponding to another of at least one content particle of the document-type definition; and loading the document data into the at least one table of the relational database according to the relational schema. Metadata Extraction The extracting step of the inventive method can further comprise the steps of: generating an item metadata table corresponding to element type content particles in the document-type definition; creating at least one default item in the item metadata table; generating a row in the item metadata table corresponding to each of the element type content particles of the document-type definition; generating an attribute metadata table corresponding to attribute type content particles in the document-type definition; creating a default attribute value in the attribute metadata table corresponding to any default items in the item metadata table; generating a row in the attribute metadata table corresponding to each of the attribute type content particles of each element type stored in the item metadata table; generating a nesting metadata table corresponding to nesting relationship content particles in the document-type definition; and generating a row in the nesting metadata table corresponding to each relationship between items identified in the item metadata table. In some embodiments of the invention, the generated nesting table row can indicate the cardinality between a pair of items. The cardinality can be one of one-to-one and one-to-many. The generated nesting table row can indicate a relationship between a parent item and a child item. The generated nesting table row can indicate the position of the child item in a definition of the parent item. Metadata Table Schema Generation In other embodiments of the invention, the generating step can further comprise the steps of: creating a table in the schema of the relational database corresponding to each row of the metadata item table; generating at least one default field in the table of the schema; altering the schema of the relational database to add a column to each table in the schema corresponding to each row of the metadata attribute table related to the particular metadata item table row; altering the tables in the schema of the relational database to add links between tables in the schema corresponding to a relationship identified in each row of the metadata nesting table; altering the tables in the schema of the relational database by adding a foreign key to a parent table if the identified relationship is a one-to-one relationship; and altering the tables in the schema of the relational database by adding a foreign key to a child table if the identified relationship is a one-to-many relationship. Metadata Loading In additional embodiments of this invention, the loading step can further comprise the steps of: initializing a link table; determining whether each item in the metadata nesting table contains a group type; initializing a pattern-mapping table; directly mapping a link into the link table for each item in the metadata nesting table that does not contain a group type; creating an additional link table containing a mapping of a link pattern for each group type identified in the metadata item table; retrieving a preselected set of rows corresponding to each item in the metadata item table; mapping a create tuple loading action in the pattern mapping table corresponding to each item in the item metadata table; mapping an update tuple loading action in the pattern mapping table corresponding to each attribute in the attribute metadata table; mapping a create tuple loading action in the pattern mapping table corresponding to each group in a link; mapping an assign action tuple loading action in the pattern mapping table corresponding to each pair in the same link corresponding to each link in the link pattern table; and forming a tree structure with the document data; and traversing the formed tree and updating the at least one relational database table according to the rows of the pattern mapping table. Metadata Table Clean Up and Optimization In yet further embodiments of this invention, the method can also comprise the step of optimizing the metadata. This optimizing step can further comprise the steps of: eliminating duplicate particle references in the metadata; and simplifying references to corresponding elements, links and attributes in the metadata. Implementation of Metadata Extraction and Storage In other aspects of the invention, a system is provided for generating a schema for a relational database corresponding to a document having a document-type definition and data complying with the document-type definition and loading the data into the relational database in a manner consistent with the relational schema. The key inventive features of the system include an extractor adapted to read a document-type definition that extracts metadata from the document-type definition representative of the document-type definition; a generator operably interconnected to the extractor for generating the schema for the relational database from the metadata, wherein at least one table is thereby defined in the relational database corresponding to at least one content particle of the document-type definition via the metadata, and at least one column is defined in each of the tables corresponding to another content particle of the document-type definition; and a loader operably interconnected to the generator for loading the document data into the table(s) of the relational database according to the relational schema. Extractor Implementation In various embodiments of the extractor for the system, the extractor can generate an item metadata table corresponding to element type content particles in the document-type definition. The extractor can create at least one default item in the item metadata table. The extractor can generate a row in the item metadata table corresponding to each of the element type content particles of the document-type definition. The extractor can generate an attribute metadata table corresponding to attribute type content particles in the document-type definition. The extractor can generate a row in the attribute metadata table corresponding to each of the attribute type content particles of each element type stored in the item metadata table. The extractor can generate a nesting metadata table corresponding to nesting relationship content particles in the document-type definition. The extractor can generate a row in the nesting metadata table corresponding to each relationship between items identified in the item metadata table. Generator Implementation In various embodiments of the generator for the system described herein, the generator can create a table in the schema of the relational database corresponding to each row of the metadata item table. The generator can alter the schema of the relational database to add a column to each table in the schema corresponding to each row of the metadata attribute table related to the particular metadata item table row. The generator can alter the tables in the schema of the relational database to add links between tables in the schema corresponding to a relationship identified in each row of the metadata nesting table. The generator can alter the tables in the schema of the relational database by adding a foreign key to a parent table if a relationship identified between a pair of tables is a one-to-one relationship. The generator can alter the tables in the schema of the relational database by adding a foreign key to a child table if a relationship identified between a pair of tables is a one-to-many relationship. Loader Implementation In various aspects of the loader of this system, the loader can initialize a link table and/or a pattern-mapping table. The loader can determine whether each item in the metadata nesting table contains a group type content particle. The loader can directly map a link into the link table for each item in the metadata nesting table that does not contain a group type. The loader can create an additional link table containing a mapping of a link pattern for each group type identified in the metadata item table. The loader can retrieve a preselected set of rows corresponding to each item in the metadata item table. The loader can map a create tuple loading action in the pattern mapping table corresponding to each item in the item metadata table. The loader can map an update tuple loading action in the pattern mapping table corresponding to each attribute in the attribute metadata table. The loader can map a create tuple loading action in the pattern mapping table corresponding to each group in a link; and map an assign action tuple loading action in the pattern mapping table corresponding to each pair in the same link corresponding to each link in the link pattern table. The loader can form a tree structure with the document data. The loader can traverse the formed tree and update the relational database table(s) according to the rows of the pattern mapping table. Optimizer Implementation In other embodiments of the system, the system can also be provided with an optimizer for refining the metadata. The optimizer can eliminate duplicate particle references in the metadata. The optimizer can simplify references to corresponding elements, links and attributes in the metadata. Terms In other embodiments of the invention, the document can be an XML document. The document-type definition can be a DTD. The data can be tagged data. Updating XML Storage in a Relational Database In a further aspect, the invention relates to a method for synchronizing and updating a relational database containing existing data with supplemental data, the relational database having a set of tables defined by a relational schema, the supplemental data comprising formatted data having a document type definition representative of the relational schema and represented in a document object, the method comprising the steps of receiving at least one proposed data update representative of the supplemental data from a source external to the relational database; and propagating the received at least one proposed data update into the relational database in a manner which ensures compliance with both the relational database relational schema and the document type definition without requiring reloading the existing data in the relational database. Update Primitives In various embodiments, the invention relates to providing at least one update primitive for accomplishing the step of propagating the received at least one proposed data update. The formatted data can be tagged-format data. The method can also further comprise the step of selectively calling the at least one update primitive and validating an output of the at least one update primitive against the document type definition. The at least one update primitive can further comprise at least one of a create root element primitive, a modify element primitive, a delete leaf element primitive and a move element primitive. The create root element primitive can create a new unattached root element in the document object representative of the at least one proposed data update. The modify element primitive can modify a specified attribute of an identified element of the document object representative of the at least one proposed data update. The delete leaf element primitive can remove an identified element of the document object representative of the at least one proposed data update. The move element primitive can change the document object location of an identified element of the document object representative of the at least one proposed data update. In various other embodiments, the method can also further comprise the step of calling both the create element primitive and the move element primitive to create a new element in the document object and to attach the newly-created element within the document object at a desired location within the document object when the at least one proposed data update calls for the creation of a new element. A location of a particular element in the document object can be identified by a path. The path can be formed in an XPath syntax. The method can also further comprise the step of converting an object identifier of a particular document object into a path. The method can also further comprise the step of traversing the document object in a child-to-parent direction to build the path. The path can comprise at least one node indicator comprising a label value and a position value corresponding to the document object. Successive node indicators can be separated by a preselected delimiter. The position value can correspond to a lateral sibling location in the document object. The label value can be selected based upon a node type of a predetermined node. Updating XML Relational Database System In another aspect, the invention relates to a system for synchronizing and updating a relational database containing existing data with supplemental data, the relational database having a set of tables defined by a relational schema, the supplemental data comprising formatted data having a document type definition representative of the relational schema and represented in a document object. A translator is provided for receiving at least one proposed data update representative of the supplemental data from a source external to the relational database and an execution device is operably connected to the translator for propagating the received at least one proposed data update into the relational database in a manner which ensures compliance with both the relational database relational schema and the document type definition without requiring reloading the existing data in the relational database. Validation/Attribute Constraints In further embodiments of the invention, the method can also further comprise the step of validating the at least one proposed data update to ensure the at least one proposed data update is compliant with the document type definition. The method can also further comprise the step of determining whether at least one of a type constraint and an attribute constraint remain valid when at least one of a new value of a document object attribute value is set and a new document object is created. The method can also further comprise the step of determining whether a cross-reference index is unique within the document object during the step of validating the at least one proposed data update. The method can also further comprise the step of determining whether a default value is required during the creation of a new element in accordance with the at least one proposed data update during the step of validating the at least one proposed data update. Quantifier Constraint The method can also further comprise the step of determining whether an enumerated value is required by the at least one proposed data update and determining whether a proposed value therefore is contained in a specified enumeration during the step of validating the at least one proposed data update. The method can also further comprise the step of checking a nesting relationship between a former and a new location of an element when an element is moved in accordance with the at least one proposed data update during the step of validating the at least one proposed data update. The method can also further comprise the step of determining a quantitative relationship between the at least one proposed data update and the relational database and determining whether the at least one proposed data update complies with such quantitative relationship as determined by the document type definition. The method can also further comprise the step of checking a quantifier constraint of a nesting relationship between elements implicated by the at least one proposed data update and determining whether the at least one proposed data update violates that quantifier constraint. The method can also further comprise the step of preventing the propagation step from occurring if the at least one proposed data update fails the validation step. In another aspect, the invention relates to a method for both generating a relational schema for a relational database corresponding to a document having a document-type definition and data complying with the document-type definition, the document-type definition having content particles representative of the structure of the data and loading the data into the relational database in a manner consistent with the relational schema, the method comprising the steps of: extracting metadata representative of the document-type definition from the document-type definition; generating the relational schema from the metadata, thereby defining via the metadata at least one table in the relational database corresponding to at least one of the content particles of the document-type definition; and loading the data into the at least one table according to the relational schema and in a manner driven by the metadata. In other aspects, the invention relates to a system for both generating a relational schema for a relational database corresponding to a document having a document-type definition and data complying with the document-type definition, the document-type definition having content particles representative of the structure of the data and loading the data into the relational database in a manner consistent with the relational schema. An extractor is provided for creating metadata representative of the document-type definition from the document-type definition. A generator is provided for forming the relational schema from the metadata, thereby defining via the metadata at least one table in the relational database corresponding to at least one of the content particles of the document-type definition. A loader is provided for loading the data into the at least one table according to the relational schema and in a manner driven by the metadata. In various embodiments, the invention also relates to the step of loading data from the document into the relational schema of the relational database. The method can also further comprise the step of updating the relational database with at least one proposed update from a second document containing related data without requiring the reloading of the data already in the relational database. The method can also further comprise the step of validating the at least one proposed update with respect to the document-type definition. The method can also further comprise the step of preventing the at least one proposed update from being loaded into the relational database if the validating step fails. The method can also further comprise the step of validating the at least one proposed update further comprises the step of comparing at least one of a data type constraint, an attribute constraint, a link reference constraint, a nesting relationship constraint and a quantifier constraint of the at least one proposed update against that required by the document-type definition prior to the step of loading the data from the at least one proposed update into the relational database. Other objects, features, and advantages of the invention will be apparent from the ensuing description in conjunction with the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS In the drawings: FIG. 1 is a schematic view detailing a system for generating a relational schema from a document type definition, forming a relational database from the relational schema and loading the contents of an extensible document into the relational database according to the relational schema. FIG. 1A is a diagrammatic representation of the system of FIG. 1 showing the extraction of a document-type definition from an extensible document, the generation of a relational schema therefrom and the loading of data contained in the extensible document into the relational database. FIG. 1B is a schematic representation of interaction between tables created in the system and method shown in FIGS. 1 and 1A. FIG. 2 is a flowchart detailing three broad method steps according to the invention schematically shown in FIGS. 1, 1A and 1B, namely, storing the document-type definition into metadata tables, creating a relational database table schema from the metadata of the metadata tables, and loading data contained in an extensible document into tables contained in the formed relational schema. FIG. 3 is a flowchart detailing the step for storing the document-type definition into metadata tables shown in FIG. 2 in which a metadata item table is created and filled with element-types declared in the document-type definition. FIG. 4 is a flowchart detailing another step of the method shown in FIG. 2 of storing the document-type definition information into metadata tables in which a metadata attribute table is created and filled with attributes defined in the document-type definition. FIG. 5 is a flowchart showing another step of the method shown in FIG. 2 of storing the document-type definition table into metadata tables including the step of building groups and forming a metadata nesting table from the metadata item table formed in FIG. 3. FIG. 5A is a flow chart detailing a portion of the flow chart of FIG. 5 corresponding to the steps to be performed when an element type is encountered during generation of the metadata nesting table. FIG. 6 is a flowchart detailing the step of the method of FIG. 2 in which a relational database schema is generated from the metadata tables including the step of forming tables for each element type in the metadata item table formed in FIG. 3 with default fields provided therein. FIG. 7 is a flowchart detailing another method step from the method shown in FIG. 2 in which tables are created to form a relational table schema from the metadata tables in which columns are added to the tables formed in the method shown in FIG. 6 for each of the attributes defined in the metadata attribute tables formed in FIG. 4. FIG. 8 is a flowchart detailing a method step corresponding additionally to the method step in FIG. 2 in which a relational schema is created from the metadata tables in which nesting relationships are determined between the attributes of the various tables and index columns are added to the various tables in the schema corresponding to those nesting relationships identified in the method step in FIG. 2 in which the metadata nesting table is constructed. FIG. 9 is a flowchart corresponding to the initialization of the pattern mapping table as described in FIGS. 1, 1A, 1B and 2. FIG. 10 is a flowchart corresponding to the method step of FIG. 9 in which at least one link table is initialized. FIG. 11 is a flowchart corresponding to a method step in FIG. 9 in which the pattern mapping table is initialized from the data contained in the metadata tables formed according to the method steps of FIG. 2. FIG. 12 is a flowchart corresponding to the method step of FIG. 2 corresponding to loading data contained in an extensible document into the relational tables formed in the method steps of FIG. 2. FIG. 13 is a flowchart corresponding to the traversal of a node tree defined in the flowchart shown in FIG. 12 for traversing the node tree and inserting data into the relational table schema formed in the method steps of FIG. 2. FIG. 14 is an example of a node free discussed with respect to FIGS. 12-13 having data and complying with a document-type definition corresponding to Example 1 described in the Background section herein. FIG. 15 is a tree representative of another example of XML data compliant to a DTD document in the form of a document object model (DOM) tree. FIG. 16 is a schematic view of a RDBMS loader and data synchronizer according to the invention comprising a DTD Loader, an XML Importer and Dumper and an XML Update Synchronizer for receiving XML data from an external source and updating a relational database formed earlier from an XML document compliant to a DTD. FIG. 17 is a set of relational tables generated from Examples 3-4 set forth below relating to a telephone billing system, wherein the relational tables can be imported from XML compliant to a DTD in the manner set forth according to the invention described in FIGS. 1-14. FIG. 18 is a schematic view of a process for propagating updates to a RDBMS according to the system and method set forth in FIG. 16 according to the invention. FIG. 19 is a before-and-after schematic view of a process for moving an element of one parent node in a DOM tree to another parent node in the DOM tree (shown by example in FIG. 15) for use in the system and method for updating a relational database with the system of FIGS. 16-18. FIG. 20 is a schematic view of a pair of XML documents in the form of DOM trees which are compliant to the same DTD that indicates the transformation of one XML document into another XML document if the documents are compliant with the same DTD, wherein this schematic is useful in understanding how the update primitives in the system and method of FIGS. 16-19 are completed. FIG. 21 is a flow chart detailing the steps of converting a DOM tree object identifier into an XPath expression for use in updating an RDBMS in accordance with the invention of FIGS. 16-20. FIG. 22 is a flow chart detailing the steps of determining the position of a selected DOM node in an XPath expression for use in updating an RDBMS in accordance with the invention of FIGS. 16-21. FIG. 23 is a flow chart detailing the steps for determining the position of a selected label of a particular node in an XPath expression for use in updating an RDBMS in accordance with the invention of FIGS. 16-22. FIG. 24 is a modified version of the DOM tree shown in FIG. 15 and the relational tables shown in FIG. 17 after a new element (itemized_call) is created therein according to the invention of FIGS. 16-23. FIG. 25 is a modified version of the DOM tree shown in FIG. 15 and the relational tables shown in FIG. 17 after an existing element (itemized_call) is modified according to the invention of FIGS. 16-24. FIG. 26 is a modified version of the DOM tree shown in FIG. 15 and the relational tables shown in FIG. 17 after an existing element (itemized_call) is deleted according to the invention of FIGS. 16-25. FIG. 27 is a modified version of the DOM tree shown in FIG. 15 and the relational tables shown in FIG. 17 after an existing element (itemized_call) is moved according to the invention of FIGS. 16-26. FIG. 28 is a flow chart detailing the steps of checking attributes for validating updates to an RDBMS when a root element is created and/or an existing element is modified according to the invention of FIGS. 16-27. FIG. 29 is a flow chart detailing the steps of checking the internal table cross-references for validating updates to an RDBMS when a root element is created and/or an existing element is modified or deleted according to the invention of FIGS. 16-28. FIG. 30 is a flow chart detailing the steps of checking quantifiers for validating updates to an RDBMS when a root element is created and/or an existing element is modified according to the invention of FIGS. 16-29. DESCRIPTION OF THE PREFERRED EMBODIMENT According to the invention, a relational schema is created out of a DTD, metadata is extracted from the DTD that describes the DTD and that illustrates how the DTD maps to the schema, and XML data is loaded into the generated relational schema that adheres to the DTD according to the metadata. In this manner, and as a direct result of the metadata analysis and storage, the data semantics implied by the XML are maintained so that more accurate and efficient management of the data can be performed. Starting with a DTD for XML documents containing data (rather than analyzing the relationships between the actual elements of the XML data), all of the information in the DTD is captured into metadata tables, and then the metadata tables are queried to generate the relational schema. Then, the data contained in the XML document can be loaded into the generated relational schema. This method can be described by three broad steps: First, the DTD is stored as metadata in tables—i.e., the metadata is used to describe the information of the DTD associated with the XML documents. This approach provides flexibility to manipulate the DTD by standard SQL queries. Second, a relational schema is generated from the metadata stored in the metadata tables. This step provides additional flexibility in that, although the relational schema can be directly mapped from the metadata tables according to the invention, the metadata tables can also be queried to do optimizing or restructuring on the metadata tables representative of the XML data structure stored in the DTD. Third, the data contained in the XML document is extracted from the document and stored into the tables defined by the relational schema, which is generated in the previous step, by using the associated metadata tables. According to the invention, the inventive metadata-driven approach includes the following beneficial characteristics: For Storing: All of the information contained in the DTD is captured in the metadata tables. It is anticipated that the XML document and the DTD can be reconstructed from the relational data and metadata as needed. For Mapping: The generated relational schema is rich in relationships that are useful in processing queries. For Loading: Mappings between the XML document and the final relational schema are captured in the metadata tables. It is contemplated that the relational data can be synchronized with XML data, which means whenever there is a data update in the relational data, the effect is also reflected in the XML data, and vice versa. It will be understood that it has been assumed that there exists only one external DTD file for compliant XML documents and that the file has no nested DTDs, and that there is no internal DTD in the XML files. Of course, to the extent that XML documents are encountered that include these items, this requirement can be achieved by pre-processing XML documents with nested or internal DTDs as needed. FIG. 1 Turning now to the drawings and to FIG. 1 in particular, a system 10 is shown for automatically loading a document 12 into a relational database 14. As can be clearly seen from FIG. 1, the document 12 comprises a first data portion 16 and a second document definition portion 18. It will be understood that the document 12 is preferably an XML document, the first data portion 16 is preferably a compliant set of tagged data normally found in a document formatted in the XML language, and the tags are compliant with the second document definition portion 18 that comprises a document-type definition (DTD) as is well known in the art (the document 12 is shown surrounded by a broken line in FIG. 1 indicating a possible separated of the DTD 18 and the data 16 since the DTD 18 can be provided separately from the XML data 16 as is also well known). As can also be clearly seen from FIG. 1, the relational database 14 comprises a first data storage portion 20 and a second data definition portion 22. It will be understood that the relational database 14 can be any of the well-known relational databases. The first data storage portion 20 is typically, and preferably, a set of tables in the relational database 14. The second data definition portion 22 preferably comprises a relational schema as is typically used to model, outline or diagram the interrelationship between tables in a relational database. It is an important feature of this invention that the DTD 18 (i.e., the second document definition portion 18) is loaded by the system 10 and used in metadata format to generate the relational schema of the second data definition portion 22. Then, the XML data stored in the first data portion 16 of the XML document 12 is loaded by the system 10 into the tables making up the first data storage portion 20. In order to accomplish these functions, the system 10 comprises an extractor 24, an optimizer 26, a generator 28 and a loader 30 all of which are interconnected to a storage unit 32. As contemplated by this invention, the storage unit 32 comprises at least a metadata table storage portion 34 and a pattern mapping table storage portion 36. According to the method of this invention, which will be hereinafter described in greater detail, the system 10 reads the DTD 18 with the extractor 24 and stores data representative of the DTD 18 in metadata tables in the metadata tables storage portion 34. From the data stored in metadata tables, the generator 28 generates the relational schema 22 in the relational database 14. In an optional loop, the optimizer 26 can massage the data stored in the metadata tables 34 to create a more efficient set of inputs for the generator 28 which, in turn, results in the generation of a more efficient relational schema 22. Next, once the relational schema 22 has been generated by the generator 28, a pattern-mapping table 36 is generated from the metadata tables and fed as an input to the loader 30 (in addition to the input of the XML data 16 from the document 12) which, in turn, provides an input to load the tables 20 and the relational database 14 with the XML data 16 stored in the document 12. FIG. 1A The automatic loading of an XML document 12 into a relational database 14 according to a document-type definition 18 contained in the XML document 12 is shown in greater detail in FIG. 1A. One feature of this invention is the importation of the information contained in the document-type definition 18 to the extractor 24 to create the metadata tables 34 (referred to herein as DTDM, short for document-type definition metadata). As can be seen from FIG. 1A, the metadata tables 34 comprise a DTDM-Item table 90 generally made up of elements and groups defined in the DTD 18, a DTDM-Attribute table 92 generally made up of Attribute of elements and groups contained in the DTD 18, and a DTDM-Nesting table 94 generally made up of nesting relationships contained in the DTD 18 as identified by the extractor 24. The metadata tables 34 are then fed to the generator 28 and, optionally, the optimizer 26, to create the link pattern and pattern mapping tables 36. It should be understood that the optimizer 26 is entirely optional and can be omitted without departing from the scope of this invention. When used, the optimizer 26 provides the additional benefits discussed herein. The tables 36 comprise an IM-Item table 96 which contains mapping information relating to the DTDM-Item table 90, an IM-Attribute table 98 that contains mapping information relating to the DTDM-Attribute table 92, an IM-Nesting table 100 that contains mapping information relating to the DTDM-Nesting table 94, and a TS-JC table 102 for containing table schema and join constraint information for assisting in the generation of the table schema 22 for the relational database 14. It will be understood that the metadata tables 34 are preferably necessary for generation of the table schema 22. However, it has been found that the generation of the link pattern and pattern mapping tables 36 can result in the generation of a more efficient table schema 22 for the relational database 14. Then, either the metadata tables 34 or, if the optimizer 26 is employed, the pattern and pattern mapping tables 36 are fed to the loader 30 to create and fill the tables 20 and the relational database 14 according to the generated table schema 22 therein. FIG. 1B A schematic representation of the tabular interaction according to this invention is shown in FIG. 1B wherein the tables shown in FIG. 1B refer to the components of the invention shown in FIGS. 1 and 1A with like reference numerals. Dashed lines interconnecting the illustrated tables indicate a relationship between a field of one table with a field in the connected table. Turning now to FIGS. 2-13, the method of automatically loading XML data into a relational database according to a relational schema defined by a document-type definition will now be described. FIG. 2 FIG. 2 describes broad method steps of the invention, shown mainly by the steps surrounded by a double-line frame, wherein step 40 indicates that data representative of the DTD 18 is stored (via the extractor 24) into the metadata tables storage portion as metadata representative of the DTD 18 which is referred to as the DTDM tables 34. Step 42 indicates the second broad method step of this invention wherein the relational schema 22 is generated (via the generator 28) from the DTDM tables. Step 44 indicates the final broad method step of this invention wherein the XML data 16 from the document 12 is loaded (via the loader 30) into the tables 20 of the relational database 14 according to the relational schema 22 generated in step 42. FIG. 2 also describes more detailed method steps for each of the broad method steps 40, 42 and 44. Namely, step 40 of storing the DTD 18 into the DTDM tables 90, 92 and 94 preferably comprises steps of creating and filling the DTDM-Item table 90 in the metadata tables 34 (shown by reference number 46 and described in greater detail in FIG. 3), creating and filling a DTDM-Attribute table 92 in the metadata tables 34 (shown by reference number 48 and described in greater detail in FIG. 4), creating and storing a DTDM-Nesting table 94 in the metadata tables 34 (shown by reference number 50 and described in greater detail in FIG. 5), and initializing a pattern mapping table (shown by reference number 58 and described in greater detail in FIGS. 9-11). Step 42 of creating the relational table schema 22 from the metadata tables 34 preferably comprises the steps of creating tables in the relational database 14 (shown by reference number 52 and described in greater detail in FIG. 6), adding columns to the tables created in step 52 to correspond to attributes from the metadata tables 34 created in step 48 (shown by reference number 54 and described in greater detail in FIG. 7), and adding nesting relationships indicated by the DTDM-Nesting table 94 stored in the metadata tables 34 in step 50 (shown by reference number 56 and described in greater detail in FIG. 8). Step 44 of loading the XML data 16 of the document 12 into the tables 20 of the relational database 14 according to the relational schema 22 generated in step 42 preferably comprises the step of loading the XML data 16 contained in the document 12 into the tables 20 of the relational database 14 according to the relational schema 22 generated herein (shown by reference number 60 and described in greater detail in FIGS. 12-13). It will be understood that the focus of the metadata extraction steps begins with three empty DTDM tables 34—the DTDM-Item table 90, the DTDM-Attribute table 92, and the DTDM-Nesting table 94, the function and features of which will be explained in detail below. The DTD 18 is first stored into the metadata tables 34 so that it can be optionally restructured, and then the relational schema 22 can be generated from the metadata tables 34. The storing stage identifies the characteristics of the DTD 18, and stores it as the metadata tables 34. The (optional) restructuring stage can identify the multi-valued attributes of the DTD 18, and can also identify items that could be represented as attributes. Mapping the DTD 18 into the relational schema 22 is achieved by applying mapping rules defining transformations over the metadata tables 34 storing the DTD 18. One initial step is identifying the types of the objects that will be found in these types of data-containing XML documents 12. Three kinds of metadata have been identified as being relevant for storing these properties: items, attributes, and relationships. The three metadata tables 34 for storing the items, attributes and relationships defined in the DTD 18 and the properties of the DTD 18 captured by each table 90, 92 and 94 are defined as will be hereinafter described. Every item, attribute and nesting relationship in the tables 90, 92 and 94 is preferably assigned a unique ID as will be described in greater detail below. An item represents an object in the DTD 18 that contains, or is contained by, other objects. An attribute is a property of an item. An item can have multiple unique attributes. The attributes of an element in a DTD are all the attributes of the corresponding item in the metadata generated by the invention described herein. A nesting relationship is used to show the hierarchical relationships between two items. It denotes that a child item is directly nested in a parent item. FIG. 3 The step of creating and filling the DTDM-Item table 90 identified by reference number 46 in FIG. 2 will now be described in greater detail with respect to FIG. 3. As illustrated in FIG. 3, processing moves to step 62 in which, initially, a pair of default items are created in the DTDM-Item table 90 referred to as "PCDATA" and "GROUP" (also referred to as ANY_GROUP in the figures). Proposed SQL statements that could accomplish this task are shown in the note associated with step 62 referred to by reference number 64. Once these initial default items are created in step 62, processing moves to step 66 which initiates a loop for each Element type declaration in the DTD 18. For each of the Element type declarations, a row is created in the DTDM-Item table 90 as shown by the proposed SQL statement in note 68. Processing then moves to decision block 70 in which it is determined whether any additional Element type declarations exist in the DTD 18. If so, processing returns to step 66. If not, processing ends. The DTDM-Item table 90 preferably stores element types and groups. The table 90 captures the existence property of an element as the Type of the item. It also captures a grouping property by creating a new group item for each group.
The Type field defines the type of an item, i.e., type of the element content in an element type declaration. ELEMENT.ELEMENT means an element content. ELEMENT.MIX means a mix content. ELEMENT.EMPTY means an EMPTY content. ELEMENT.ANY means an ANY content. There are two new item types, i.e., PCDATA and GROUP. PCDATA, means a PCDATA definition, and GROUP means a group definition. FIG. 4 The step of creating and filling the DTDM-Attribute table 92 identified by reference number 48 in FIG. 2 will now be described in greater detail with respect to FIG. 4. As shown in FIG. 4, processing moves to step 72 in which the Item_ID of PCDATA is retrieved from the DTDM-Item table 90. Processing then moves to step 74 in which default attribute values for PCDATA are created in the DTDM-Attribute table 92. A proposed SQL statement for accomplishing this task is provided in note 76 associated with step 74. Processing then moves to step 78, which initiates a loop for each element type declaration in the DTD 18. Processing then moves to step 80 in which the Item_ID for each of the element type declarations in the DTDM-Item table 90 is retrieved. Processing then moves to step 82, which initiates a loop for each attribute of this particular element type. For each attribute of this element type declaration, a row is inserted into the DTDM-Attribute table 92 providing attribute information corresponding to the elements of the DTDM-Item table 90. A proposed SQL statement for accomplishing this task is provided in note 84 associated with step 82. After each row insertion into the DTDM-Attribute table 92, processing moves to decision block 86 to determine whether additional attributes exist for this element type. If so, processing returns to step 82 to process additional attributes. If not, processing moves to decision block 88 to determine whether additional elements exist in the DTD 18 (i.e., as stored in the DTDM-Item table 90). If so, processing returns to step 78. If not processing ends. The DTDM-Attribute table 92 stores attributes of elements or groups.
Note that, for now, the ID/IDREF(s) attributes that represent the element reference properties are stored simply as attributes. Later, during a mapping stage, the element reference property will be captured and stored in an additional metadata table, denoted as the TC-JS table 102 in FIG. 1A (and JoinConstraint 102 in FIG. 1B). FIG. 5 The step of creating and storing the DTDM-Nesting table 94 identified by reference number 50 in FIG. 2 will now be described in greater detail with respect to FIG. 5. Processing moves to step 402 in which the DTDM-Nesting table 94 is initialized. Pseudopodia indicative of the steps performed in step 402 are given in note 404 associated with step 402. Processing then moves to step 406, which initiates a loop for every element type declaration found in the DTD 18. Processing then moves to step 408, which retrieves the type, i.e., MIXED, PCDATA, ANY, ELEMENT, and EMPTY of the particular element type being examined in the loop initiated at step 406. Processing then moves to step 410 in which the DTDM-Item table 90 is queried to return the identification (ID) of the element type identified in step 408. Processing then moves to decision block 412 which determines whether the current element type is of type MIXED. If so, processing moves to step 414 in which a new group is created in the DTDM-Item table 90 with type CHOICE, wherein a proposed SQL statement to accomplish this task is shown in note 416 associated with step 414. Processing then moves to step 418 in which a nesting relationship is created from the current element type to the newly-created group as shown by the proposed SQL statement in note 420 associated with step 418. Processing then moves to step 422 in which a nesting relationship is created from this group to element type PCDATA. Processing then moves to step 424 in which all of the nesting relationships from this group to its children are created by function fill_DTDM-Nesting_Item shown in detail in FIG. 5A (via indicator 5A referred to by numeral 444). Processing then moves to decision block 426 in which it is determined whether there are additional element types in the DTD 18 to be processed for the loop initiated at step 406. If so, processing returns to step 406. If the test performed at decision block 412 fails, processing moves to decision block 428 which determines whether the current element type is of type ANY. If so, processing moves to step 430 in which one relationship from the current element is created to the item titled ANY_GROUP. A proposed SQL statement to accomplish this task is identified in note 432 associated with step 430 in FIG. 5. Processing then moves to decision block 426, which has been previously described. If the test performed at decision block 428 fails, processing moves to decision block 434 which determines whether the current element type is of type PCDATA. If so, processing moves to step 436 in which a relationship to the previously-created PCDATA item is created in accordance with the proposed SQL statement shown in note 438 associated with step 436 in FIG. 5. Processing then moves to decision block 426, which has been previously described. If the test performed at decision block 434 fails, processing moves to decision block 440 which determines whether the current element type is of type ELEMENT. If so, processing moves to step 442 which calls a function titled fill_DTDM-Nesting_Item (element_type,-1), the details of which are described in FIG. 5A (by the connector identified with 5A and indicated by numeral 444). After this function has completed, processing moves to decision block 426, which has been previously described. If the test performed at decision block 440 fails, processing moves to step 446 which notes that the current element type is EMPTY. Processing then moves to decision block 426, which has been previously described. Once all of the elements have been processed, i.e., all of the element type declarations as identified in the loop initiated at step 406 have been processed, processing ends. FIG. 5A The contents of the function (i.e., fill_DTDM-Nesting_Item) identified by the "5A" connectors 444 of FIG. 5 are described in greater detail with respect to FIG. 5A. Once this function is called, processing moves to decision block 446 in which it is determined whether the nesting relationships of the parent item are to be copied into the group. If so, processing moves directly to step 448 in which the group_ID is treated as an element_ID. If not, processing moves to step 450 in which the DTDM-Item table 90 is queried to determine the ID of the parent item (i.e., element type or group) as element_ID. A proposed SQL statement to accomplish this task is shown in note 452 associated with step 450 in FIG. 5A. In either case, processing then moves to step 454, which initiates a loop for the group or element identified in step 448 as element_ID. Processing then moves to step 456, which retrieves the object reference to the current element type or group being processed. Processing then moves to decision block 458, which determines whether the element type or group corresponding to the object reference identified in step 456 is of type GROUP. If so, processing moves to step 460, which retrieves the group ID and stores this ID in variable ref_ID. If not, processing moves to step 462 in which the type is determined to be an element type declaration. Following either step 460 or step 462, processing then moves to step 464 in which the previously-determined object reference is stored into the DTDM-Nesting table 92 in a manner consistent with note 466 which shows a proposed SQL statement for accomplishing this task. Processing then moves to decision block 466 in which it is determined whether any additional references need to be processed. If so, processing returns to step 454. If not, processing terminates and returns to continue processing at the point FIG. 5 was left via connector 444. The DTDM-Nesting table 94 captures relationships between different items, i.e., nesting, schema ordering, and occurrence properties.
Fields FromID and ToID reference a parent item and a child item that participate in a nesting relationship. The Index field captures the schema ordering property; it denotes the position of this child item in the parent item's definition. In a sequence group, each child item will have a different value for indices (i.e., 1, 2, . . . ); for all children in a choice group, the index fields will all be the same (i.e., 0). The occurrence property for a child element is captured by a combination of the Ratio and Optional fields. The Ratio field shows cardinality between the instances of the parent item and of the child item. Note that, since the nesting relationships are always from one element type to its sub-elements in the DTD 18, there are only one-to-one or one-to-many nesting relationships in the Ratio column. The many-to-one and many-to-many relationships are not captured by the Ratio field but rather are captured by ID/IDREF(S) attributes in the DTD. The Optional field has value of true or false depending on whether this relationship is defined as optional in the DTD. The following table shows how the Ratio and Optional fields combine to represent the occurrence properties:
The steps for extracting the metadata tables 90, 92 and 94 can be summarized as follows: Create one PCDATA Item. This one item will represent all occurrences of #PCDATA in the DTD. The PCDATA item will be used to convert all element-to-PCDATA relationships, such as found in a mixed content definition, to element-to-element relationships, thus unifying these two types of nesting relationships. A PCDATA item has one attribute called value that is used to capture the text value of this PCDATA item. Create an item for each element type declaration. Tuples in the DTDM-Item table 90 are the elements directly defined by the DTD 18. Create an item for each grouping relationship in each element type declaration. For each element type declaration in a DTD 18, a group item is created for each group in the item, and the group in the element type declaration is replaced with the corresponding group item. In Example 1, items 14 to 16 represent the groups (author*|editor), (author, affiliation?), and (book|monograph) respectively. Defining each group as an item is used to convert nested groups into nesting relationships between items. For example, the definition of element book shows that book is composed of booktitle, and a group of authors or an editor. A new item G1 would thereby be defined for the group (author*|editor), the element definition of book would be changed to <!ELEMENT book (booktitle, G1)>. Store nesting relationships. After defining the PCDATA item and all group items, the hierarchical definitions of elements can be described as nesting relationships between two items. An element definition is a sequence (or choice) of n sub-elements stored as n nesting relationships with index fields in the DTDM-Nesting table 94. For example, the element definition <!ELEMENT book (booktitle, G1)> has two nesting relationships, i.e., between items book and booktitle, and between items book and G1. These nesting relationships are shown in the DTDM-Nesting table 94 constructed in accordance with the DTD 18 of Example 1 (with IDS 1 and 2). Store attributes. For items with attributes defined, those attributes are stored in the DTDM-Attribute table 92. For example, the attribute AuthorIDs of item Contactauthors is stored in DTDM-Attribute table 92 (with ID 1) constructed in accordance with Example 1. Store the ANY element type definitions. An ANY-typed element can contain a mix of PCDATA and any defined element types, and thus can have relationships with all other element types. To capture that relationship, a choice group item is created called ANY GROUP (AG). Every element type definition with content ANY expresses its relationships with all other element types with a one-to-many nesting relationship with the AG item. Using Example 1, row 17 in the DTDM-Item table 90 is the AG group, and nesting relationships with ID 24 through 36 are between this AG group and each of the other element items and the PCDATA item, i.e., between this AG group and items 1 through 13, respectively, in the example described herein conforming to the DTD 18 of Example 1. The Affiliation item, which is an ANY element type declaration, has a one-to-many nesting relationship to the AG group (see line 23 in the DTDM-Nesting table 94 below). Once the metadata has been extracted and mapped from the DTD 18 shown in Example 1 in the Background section, the metadata tables 34 have the following structure: The DTDM-Item table 90:
The DTDM-Attribute table 92:
The DTDM-Nesting table 94:
Any discussion based on examples (and, specifically, Example 1) refer to the above metadata table examples. The rules used for mapping the DTD 18 are described (as stored as described above), into the relational schema 22 are described in the following. The basic idea behind these rules is that each item is to be mapped into a relational table 20 in the database 14 according to generated schema 22. As discussed previously, the elements in XML documents are ordered. This order is retained in the newly-generated relational table schema. Groups are not directly shown in the XML document, so they do not have an order property. FIG. 6 The step of creating tables 20 in the relational database 14 (identified by reference number 52 in FIG. 2) will now be described in greater detail with respect to FIG. 6. Turning to FIG. 6, processing moves to step 120 in which a query of the DTDM-Item table 90 is performed to return all of the item types stored in the DTDM-Item 90 table. A proposed SQL statement to accomplish this task is shown in note 122 associated with step 120 in FIG. 6. Processing then moves to step 124, which initiates a loop for every item returned in the recordset selected in step 120. Processing within the loop then moves to step 126 wherein a table 20 is created in the relational database 14 with some key-type default fields, wherein the table name created in the database 14 corresponds to the Name field in the DTDM-Item table 90 as returned in the recordset in step 120. A proposed SQL statement to accomplish this task is shown in note 128 associated with step 126 in FIG. 6. Processing then moves to decision block 130, which determines whether additional items exist for processing. If so, processing returns to step 124. If not, processing ends. These steps perform a first mapping on the DTDM-Item table 90. That is, for each ELEMENT.* and PCDATA-typed item defined in the DTDM-Item table 90, a table is created with two default columns: "iid" and "order". For each Group-typed item, a table is created with only an "iid" column. The metadata tables 34 are queried to get all non-group items by: SELECT name, type FROM DTDM-Item WHERE type LIKE "ELEMENT.%" OR type="PCDATA" After the name and type of the item are retrieved, the following queries are performed to create the tables from the query recordset returned. So, for the type of "ELEMENT.*" and "PCDATA" item in the query recordset result, the following query is issued to create a table for each of them, (e.g., an item called ItemTable with a default primary key "iid" and a column called "order" in an INTEGER format): For items of other types, a table will be created in the form such as: After identifying the basic tables and their required columns, any other columns that are appropriate for those tables must be determined. First, columns are added, which represent the attributes of its parent item, to each table corresponding to that item. Second, the columns of the various tables are interconnected according to the detected nesting relationships therebetween. FIG. 7 The step of adding columns in the tables created in step 52 for attributes in the DTDM-Attribute table 92 (as identified by reference number 54 in FIG. 2) will now be described in greater detail with respect to FIG. 7. As shown in FIG. 7, processing moves to step 132 in which a join query of the DTDM-Attribute table 92 with the DTDM-Item table 90 is performed to return all of the attributes of an item from data contained in the DTDM-Attribute table 92 and the DTDM-Item tables 90. A proposed SQL statement to accomplish this task is shown in note 134 associated with step 132 in FIG. 7. Processing then moves to step 136, which initiates a loop for every Attribute returned in the recordset selected in step 132. Processing then moves to step 138 in which, based upon the attribute type of the particular row in the recordset returned in step 132, a column-type variable is determined. A list of applicable column types is shown in note 140 associated with step 138 in FIG. 7. Processing then moves to step 142 in which the relational database schema 22 is altered to add this attribute and its type to its parent table. A proposed SQL statement to accomplish this task is shown in note 144 associated with step 142 in FIG. 7. Processing then moves to decision block 146 to determine whether additional attributes need to be processed. If so, processing returns to step 136. If not, processing ends. In this part of the inventive method herein, these steps perform a second mapping on the DTDM-Attribute table 92. For each tuple in the DTDM-Attribute table 92, a column is created, named with the "Name" property of the tuple in the relational table that is identified by the pid index of the tuple. All of the column domains are preferably strings, since the DTD 18 preferably only has one data type, i.e., CDATA, PCDATA. In this invention, it is not necessary to perform additional parsing on the data values to determine their data types, although doing so would not depart from the scope of this invention. More generally and by way of summary, the above described steps illustrate that the metadata tables 34 are queried to get all attributes for a given item name X (see step 132 and its associated note 134): SELECT A.name, A.type FROM DTDM-Item I, DTDM-Attribute A WHERE I.name=X AND I.id=A.pid Then, those attributes returned in the above recordset are placed in the definition of the tables created in the first mapping by issuing the following queries (see step 142 and its associated note 144): Here, the A1, A2, etc. names and types are the tuples selected from the query issued in connection with step 132 (as described in note 134). FIG. 8 The step of determining and adding nesting relationships to the relational schema 22 (identified by reference number 56 in FIG. 2) will now be described in greater detail with respect to FIG. 8. Turning to FIG. 8, processing moves to step 148 in which a query of the DTDM-Nesting table 94 is performed to return all of the nesting relationships of an item from the data contained in the DTDM-Nesting table 94 and the DTDM-Item table 90 (i.e., to extract all of the item IDs involved in each nesting relationship). A proposed SQL statement to accomplish this task is shown in note 150 associated with step 148 in FIG. 8. Processing then moves to step 152 which initiates a loop for every nesting relationship returned in the recordset selected in step 148. Processing then moves to decision block 154 which determines whether the ratio of elements in the particular nesting relationship is a 1-to-1 or a 1-to-n relationship. If the decision block 154 determines that the ratio is 1-to-1, processing moves to step 156 in which a foreign key is inserted in the parent table of the relationship. A proposed SQL statement to accomplish this task is shown in note 158 associated with step 156 in FIG. 8. If the decision block 154 determines that the ratio is 1-to-n, processing moves to step 160 in which a foreign key is inserted into the child table in the relationship. A proposed SQL statement to accomplish this task is shown in note 162 associated with step 160 in FIG. 8. In either case, processing then moves to re-connector 164 and then to decision block 166 which determines whether additional nesting relationships need to be processed. If so, processing returns to step 152. If not, processing ends. Again, in a general summary, a third mapping is thereby performed on the metadata tables 34 in connection with the process shown in FIG. 8. For each tuple R in the DTDM-Nesting table 94, the table corresponding to the from item is labeled as S and the table corresponding to the to item as T participating in R. Then if R is a one-to-one nesting relationship, the iid of T is stored as a foreign key in S (i.e., store T_iid as a column in S); if R is a one-to-many nesting relationship, the iid of the item S is stored as a foreign key, named P_T_iid (P means parent, so it can be thought of as a reverse link), in T. If the Optional field of this relationship R in the DTDM-Nesting table 94 is false, then a NOT NULL constraint is added on the definition of the table. If there is more than one relationship between the two items S and T, then indices are placed after each column name, e.g., _T_iid—1. The metadata tables 34 are queried to get pairs of items of all of the nesting relationships (see, e.g., note 150 associated with step 148 in FIG. 8): SELECT F.name, T.name FROM DTDM-Item F, DTDM-Item T, DTDM-Nesting WHERE F.id=N.fromid AND T.id=N.toid. In accordance with the invention, this relationship mapping depends upon the ratio inherent to the nesting relationship, so that the corresponding table is updated in the following manner: If a one-to-one relationship is detected at decision block 154: If a one-to-many relationship is detected at decision block 154: In this approach, many-to-many relationships between different elements are captured by joins on attributes of type ID and IDREF(S). Different combinations of the ID/IDREF(s) attribute represent different cardinalities between two elements. The following table represents the possible relationships between two elements depending upon their ID/IDREF(S) attributes (e.g., of note, the contactauthors and author elements in Example 1 listed in the Background section have a many-to-many relationship):
A fourth mapping is performed on the metadata tables 34 for the ID type of attributes. For the ID type of attributes, those attributes are designated as a key of their parent tables. A fifth mapping is performed on the metadata tables 34 for the IDREF(S) type of attributes. For the IDREF(S) type of attributes, join constraints will be added to show meaningful joins between those tables. Each combination of attributes with type ID and type IDREF(S) is stored as one tuple in a TS-JC table 102 (short for Table Schema/Join Constraints). The FromColumn and ToColumn store the ID of the attribute of type IDREF(s) and of type ID, respectively. The TS-JC table 102 stores these equi-join conditions representing the element reference properties:
The metadata tables 34 are queried to retrieve all of the attributes having type ID by the query: SELECT I.name, A.name FROM DTDM-Item I, DTDM-Attribute A WHERE I.id=A.pid AND A.type="ID" All of the attributes having type IDREF (S) are retrieved by the query: SELECT I.name, A.name FROM DTDM-Item I, DTDM-Attribute A WHERE I.id=A.pid AND (A.type="IDREF" OR A.type="IDREFS") Then, those retrieved recordset items are placed into the TS-JC table 102. The result after performing these mappings on the metadata tables 34 (specifically as updated per Example 1), is shown in the following tables which show essentially a data dictionary of the relational schema 22 for the relational database 14 and also the TS-JC table 102. The data dictionary lists the table names and the columns in each table. The relational database data dictionary would look as follows if the metadata for Example 1 is employed:
The TS-JC table 102 would appear as follows:
From the examples shown above, it can be seen that there are several relationships between different tables and also, the IDREFS type attribute of the DTD 18, e.g., authorIDs, is not fully represented by the schema 22 proposed above. Two restructuring techniques (i.e., as part of the optional optimizer 26) can be employed according to the invention on the metadata tables 34 to address these shortcomings. First, multiple-value attributes can be identified. Second, elements that should be attributes of other elements can be identified. In the DTD 18 (and, of course, any DTD), some attribute types can contain multiple values, e.g. IDREFS, NMTOKENS, ENTITIES. Such attributes can be analogized to a set rather than an attribute, and it is desired to represent their values as sets. In stead of treating the whole attribute as a unitary string of some undetermined length, the values of that attribute are accessed individually. Hence, it is desired to identify these multiple-value types of attributes and convert them into separate tables to access those values. Of course, the transformation of attribute types other than IDREFS would be handled in a similar manner. By way of example, assuming that a DTDM-Item E has a multiple-value attribute A. For each A, another item named E:A is created. There is only one attribute in this item named value. A one-to-many relationship is then created between the item E and the item E:A. The attribute A is then removed from the attribute list of the item E. The following paragraphs describe this type of mapping in detail. It can be seen from the above metadata expression of Example 1 that the attribute authorIDs of item contactauthors is of type IDREFS. So, a new item contactauthors_authorIDs is created and the attribute authorIDs with type IDREFS is changed into the attribute value of item contactauthors_authorIDs with type IDREF. This allows the expression of multiple values of attribute authorIDs by a new table. In a DTD, there are one-to-one relationships between different elements. If an element of type A contains only an EMPTY content element, then a later element of type B can be considered to act as a complex attribute of an earlier one. Hence, a technique is proposed to convert these kinds of "complex attribute"-elements into a real attribute which is referred to herein as an inline attribute process. Inlining an attribute means, if item A to item B has a 1:1 nesting relationship and item B has no child item, then all of the attributes of item B can be inlined into item A. Then, the attribute X of item B is inlined into A as B_X. This inline technique cannot be applied to one-to-many relationships, because multiple occurrences of the attributes could exist. After inlining the attributes by the process discussed above, the number of nesting relationships is consequently reduced, hence the table schema 22 is simpler. It can be appreciated that a group item could also contain other items, so, after inlining attributes, the group item could have attributes which are converted from its children items. The inlining process includes multiple iterations, until no additional items can be inlined. In terms of operations on the metadata tables 34, starting from the PCDATA element (leaves), items in the DTDM-Nesting table 94 are searched for that have never appeared in the "FromID" field, and only appeared in "ToID" field with "Ratio" as "1:1". In order to apply the inline operation, the item B has to have no child items, and the relationship between item A and item B must be one-to-one, as follows:
For example, using the metadata tables generated in response to Example 1, there are two proposed iterations. During the first iteration, only item 1 (PCDATA) is returned. During the second iteration, item 3 (booktitle), 5 (title), 11 (firstname) and 12 (lastname) are returned. Then, there no more items satisfy the above conditions. After inlining the attributes, the GROUP, or ATTRIBUTE typed items can be removed which, of course, have no relationship with other items, from the DTDM-Item table 90. However, the items of type ELEMENT.* or PCDATA cannot be removed, because the elements and PCDATA are required during the database data loading phase discussed hereafter in detail. After loading the data from the document 12, those tables can be removed to reduce the degree of redundancy of data. There is an additional refinement to make the schema 22 more meaningful. That is, in the table schema 22, all of the attribute names of "*.PCDATA.value" are simplified into "*" Then, a query can be performed in simpler semantic like:
The tables following this paragraph show the metadata tables 34 after being restructured as discussed above. Compared to the initial version of the metadata tables 34 above, it can be seen that, the number of nesting relationships in the DTDM-Nesting table 94) has been reduced to half, while the number of attributes has been inc | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||