Maintenance of a markup language document in a database

[0001] This application claims priority of U.S. Provisional Patent Application Serial No. 60/332253 filed on Nov. 16, 2001, the contents of which are incorporated herein by reference.

[0002] The present invention relates generally to electronic documents and, in to particular, to the storage and maintenance of complex text-based documents.

[0003] International Publication No. WO 98/34179 (PCT/AU98/00050) in the name of Time Base Pty Ltd and published on Aug. 6, 1998 and counterpart U.S. Pat. No. 6,233,592 issued on May 15, 2001 to Schnelle et al. are incorporated herein by reference. In these documents, an electronic publishing system is disclosed that provides a sparse multidimensional matrix of data using a set of flat file records. In particular, the computer-implemented system publishes an electronic publication using text-based data. Predefined portions of the text-based data are stored and used for the publication. At least one of the predefined portions is modified, and the modified version is stored as well. The predefined portion is typically a block of text, greater in size than a single word, but less than an entire document. Thus, for example, in the case of legislation, the predefined portion may be a section of the Act. Each predefined portion and the modified portion(s) are marked up with one or more links using a markup language, preferably Standard Generalized Markup Language (SGML) or eXtensible Markup Language (XML). The system also has attributes, each being a point on an axis of a multidimnensional space for organising the predefined portions and the modified portion(s) of the text-based data. This system is simply referred to as the Multi Access Layer Technology or MALT system hereinafter.

[0004] Australian Patent Application No. 65470/00 filed on Oct. 12, 2000 in the name of TimeBase Pty Ltd, Canadian Patent Application No. 2323245 filed on Oct. 12, 2000 in the name of TimeBase Pty Ltd, New Zealand Patent Application No. 507510 filed on Oct., 12, 2000 in the name of TimeBase Pty Ltd and U.S. patent application Ser. No. 09/689927 filed on Oct. 12, 2000 in the names of Lessing et al. are incorporated herein by reference.

[0005] Large or complex text-based datasets are typically hierarchical in nature. In the storage, maintenance and publication of such data, a markup language capable of describing such hierarchies is commonly used. XML is one such markup language that is more commonly used, particularly in the print, electronic or online publishing industries, and for government or public records or technical documentation. XML data is stored typically either in flat text files encoded in ASCII, Unicode, or other standard text encoding, or in a native XML database.

[0006] The flat text files may be part of a document management system. Such a document management system may be based on a relational database. Document management systems deal with a document as a whole and are able to store relevant data is about each document. However, document management systems are typically not designed to operate on data (XML elements) within such documents. Consequently, a document management system does not typically operate on all (or even a substantial number of the) XML elements contained in flat text files on which the document managing system is operating. An XML database, in contrast, operates on all XML elements of the XML data that the XML database is storing and, consequently, XML databases must manage large amounts of data and detail. As a result, document management systems have a limited usefulness resulting from a lack of precision, and XML databases are overwhelmed by the multiplicity of XML elements that are to be managed.

[0007] Attempts have been made to transform XML data into a set of Structured Query Language (SQL) relational database tables. SQL is a database technology that provides a user with powerful query functionality and powerful data management tools. SQL possesses the stability of a mature technology, whereas XML databases are still a relatively immature technology and thus possess a degree of instability. SQL is a fast and efficient technology, and a wide choice of software and hardware manufacturers offer or support SQL databases.

[0008] Object relational mapping techniques are typically used to convert XML data into relational databases. Conventional object relational mapping techniques, however, often attempt to capture all of the document hierarchy. This is almost never necessary and can result in substantial size and performance penalties in the resulting SQL tables. Such object relational mapping techniques typically result in a far larger number of SQL tables than is necessary.

[0009] Thus, a need exists for providing an efficient method for converting a markup language document to a set of database tables, such that the conversion is reversible. The set consists of a small, fixed number of tables and may consist of a single table. A further need exists for providing a method for converting a markup language document to a set of database tables, such that the converted markup language document can be maintained without requiring a conversion back to the original markup language format of the document.

[0010] According to a first aspect of the invention, there is provided a method for converting a document encoded in a markup language into a format for mapping to a database table, the method including the steps of:

[0011] replacing the content of at least one node in the document stored in a first storage unit with a placeholder and storing the replaced content in a separate data storage unit associated with the corresponding node, the node being an instance of a node element selected from a node element set; and

[0012] modifying a formal definition of markup rules associated with the document to recognise the placeholder.

[0013] According to a second aspect of the invention there is provided an apparatus for converting a document encoded in a markup language into a format for mapping to a database table, the apparatus including:

[0014] a device for replacing the content of at least one node in the document stored in a first storage unit with a placeholder and storing the replaced content in a separate data storage unit associated with the corresponding node, the node being an instance of a node element selected from a node element set; and

[0015] a device for modifying a formal definition of markup rules associated with the document to recognise the placeholder.

[0016] According to a third aspect of the present invention there is provided a computer program product having a computer readable medium having a computer program recorded therein for converting a document encoded in a markup language into a format for mapping to a database table, the computer program product including:

[0017] a computer program code device for replacing the content of at least one node in the document stored in a first storage unit with a placeholder and storing the replaced content in a separate data storage unit associated with the corresponding node, the node being an instance of a node element selected from a node element set; and

[0018] a computer program code device for modifying a formal definition of markup rules associated with the document to recognise the placeholder.

[0019] According to a fourth aspect of the present invention there is provided a method for converting an extensible Markup Language (XML) encoded document into an equivalent Structured Query Language (SQL) table structure, the method including the steps of:

[0020] determining a node element set for the XML encoded document, wherein each node element in the node element set is a discrete level of the document;

[0021] determining one or more nodes of the XML encoded document, each node being an instance of a node element;

[0022] allocating to each node a unique node identifier; and

[0023] assembling the XML content of each node by performing the flirter steps of:

[0024] assembling XML content of the corresponding node element;

[0025] creating a separate sub-document for each node by inserting as a prefix a standard XML processing instruction, plus a DOCTYPE declaration, where the DOCTYPE element is the node element, and the public ID is the same as that of the original DTD, except that the word MALTbase is inserted as a prefix to the descriptor;

[0026] replacing any sub-node elements with equivalent empty placeholder elements in which the namespace MALTbase: has been inserted as a prefix to a element name, wherein the only non-fixed attribute is a child ID, being the ID of the sub-node relative to all other sub-nodes within the sub-node's parent; and

[0027] constructing a node table record to hold the content.

[0028] According to a fifth aspect of the present invention there is provided a method for converting an eXtensible Markup Language (XML) Document Type Definition (DTD) into a form suitable for accessing pre-processed node content, the method comprising the steps of:

[0029] declaring a new MALTbase empty placeholder element for each node element in the node element set;

[0030] modifying each content model referring to a node element to refer in addition to an equivalent MALTbase placeholder element;

[0031] inserting the word MALTbase as a prefix to a descriptor of a public identifier to produce a modified public identifier; and

[0032] allocating the modified public identifier to the new DTD.

[0033] According to a sixth aspect of the present invention there is provided a method for converting an extensible Markup Language (XML) Document Type Definition (DTD) into a form suitable for accessing pre-processed node content, the method comprising the steps of:

[0034] duplicating the XML DTD to create a new DTD;

[0035] assigning the new DTD a public identifier that is the same as the public ID of the XML DTD except that the word MALTbase is inserted as a prefix to the descriptor;

[0036] creating a new placeholder element for every element in the node element set, each the placeholder element having MALTbase: inserted as a prefix to the name, an empty content model; and an ATTLIST containing the two attributes:

[0037] child-id CDATA REQUIRED

[0038] xmlns:MALTbase CDATA FIXED http://www.malt.com/xmlns/MALTbase; and

[0039] replacing every occurrence of a node element in any content model with a group consisting of two alternatives, the original element and its MALTbase equivalent.

[0040] According to a seventh aspect of the present invention there is provided a method for reconverting a MALTbase Structured Query Language (SQL) table back into an equivalent extensible Markup Language (XML) document, the method including the steps of:

[0041] creating an XML document from root node content in which the MALTbase prefixes are removed from DTD public ID and the DOCTYPE;

[0042] replacing each placeholder element in the resulting document with the equivalent element from the corresponding sub-document;

[0043] repeating the above step until no further placeholders remain.

[0044] According to an eighth aspect of the present invention there is provided a method for maintaining an eXtensible Markup Language (XML) document in MALTbase Structured Query Language (SQL) form, without the need for reconverting the document to XML, the method comprising the steps of:

[0045] locating the node to be edited;

[0046] activating an edit function that locks the node for writing and establishes an edit session in which an editing tool manages content of a node; and

[0047] writing the updated content back into the node record, when the edit session is finished.

[0048] According to a ninth aspect of the present invention there is provided a method for saving a modified node (principal node), the method comprising the steps of:

[0049] generating a list of placeholders in the principal node;

[0050] generating a list of existing sub-nodes from a database;

[0051] pairing off placeholders and sub-nodes;

[0052] deleting from the database any sub-node and the sub-node's descendants, if that sub-node is not matched against a placeholder;

[0053] creating a duplicate node for each placeholder not currently a sub-node of the principal node;

[0054] assigning a provisional ID to each duplicate node, wherein each ID consists of the ID of the principal node, a provisional child ED within the principal node, and a trailing portion of the ID, if the new node is a descendant of the node being copied.

[0055] scanning the list of matched placeholders in document order;

[0056] assigning a provisional child ID to any placeholder that has a lower child ID than any one of the placeholder's siblings that have already been scanned;

[0057] performing a standard MALTbase XML-to-SQL conversion on each sub-node element (not being a placeholder) present;

[0058] creating new SQL records for each of the sub-node elements;

[0059] assigning a provisional ID to each new node;

[0060] assigning a provisional child ID within the principal node;

[0061] replacing the text of each sub-node element in the principal node with a new placeholder; and

[0062] assigning permanent child IDs to the placeholders to replace the provisional segment in the ID of each corresponding sub-node (or descendant).

[0063] According to another aspect of the invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for implementing any one of the methods described above.

[0064] One or more embodiments of the present invention are described hereinafter with reference to the drawings, in which:

[0065] FIG. 1 shows a sample XML document fragment;

[0066] FIG. 2 shows an original DTD fragment for the XML fragment of FIG. 1;

[0067] FIG. 3 shows a MALTbase DTD fragment corresponding to the DTD fragment of FIG. 2;

[0068] FIG. 4a shows a sample DTD;

[0069] FIG. 4b shows the DTD of FIG. 4a modified in accordance with MALTbase principles;

[0070] FIG. 5a shows the mapped content of the root node of FIG. 1;

[0071] FIG. 5b shows the mapped content of the chapter node of FIG. 1;

[0072] FIG. 5c shows the mapped content of the first part node of FIG. 1;

[0073] FIG. 6a shows a sample XML document;

[0074] FIG. 6b shows a root node corresponding to the XML document of FIG. 6a ;

[0075] FIGS. 6c-f show sub-nodes of the root node of FIG. 6b;

[0076] FIG. 7 shows a minimal SQL node table corresponding to the document fragment of FIG. 1;

[0077] FIG. 8 shows a sample nodes table corresponding to the XML document of FIG. 6a ;

[0078] FIGS. 9a-d illustrate the results of simple database operations on the node set of FIGS. 6b-f;

[0079] FIGS. 10a-f show a graphical representation of a SQL node write-back; and

[0080] FIG. 11 is a schematic block diagram representation of a general-purpose computer system on which a method for converting XML data into SQL tables may be practised.

[0081] A method, an apparatus and a computer program product for converting a markup language document into an equivalent database table are described. Preferably, the markup language is XML and the database is a SQL database. in the following description, numerous details are set forth. It will be apparent to one skilled in the art, however, that the present invention may be practised without these specific details. In other instances, well-known features are not described in detail so as not to obscure the present invention. While the following description refers to an XML document, the principles embodied therein can readily be extended to encompass arbitrary collections of XML documents.

[0082] Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

[0083] XML to SQL Conversion

[0084] A method of conversion is disclosed for producing an SQL rendition of an XML document that preserves document order, hierarchy, and all other links and relationships. Such a method of conversion preferably limits the number of tables and records and the amount of real time processing required by downstream applications to the minimum consistent with the required functionality. The method converts an XML encoded document into a minimal set of SQL tables in such a manner that the original XML document may be reconstructed in full at any time. This methodology is referred to as MALTbase hereinafter.

[0085] The MALTbase mapping operates on any arbitrary XML document with an arbitrary Document Type Definition (DTD) or schema. DTDs and XML schemas are different mechanisms that are used to specify valid elements that may occur in a document and the order in which such elements may occur. DTDs and schemas may also constrain certain aspects of the elements.

[0086] In the embodiments of the invention, the granularity of the conversion of an XML document to an SQL table is matched to the requirements of those applications that access the SQL output. Accordingly, the large scale structure of the data is mapped into a set of nodes. Structure below this level is simply broken into sub-documents which are stored as a single field or Character Large OBject (CLOB). The sub-documents in single field or CLOB format are suitable for direct use by end applications, including:

[0087] XML validating editors used to examine, modify, or both examine and modify the data; and

[0088] any other application needing to access the data on a node-by-node basis.

[0089] The fundamental underlying principle of the conversion strategy, and what sets the strategy apart from other XML to SQL conversion systems, is the concept of strictly operating at a node level, rather than operating on every single element of the document to be converted. A node is a distinguished structural unit of the document. Typically, a node is introduced by one of a set of specified XML elements (the node element set). The MALTbase mapping converts an XML document into a single table of a relational database, the table possessing a single column for storing the content associated with each node identified. The MALTbase mapping involves decomposing the original XML document into a number of sub-documents, each sub-document corresponding to a node of the original XML document. The sub-documents contain placeholders that point to other node sub-documents in the node ordering. If the sub-document corresponds to a terminal node, the sub-document contains the content of the node from the original XML document.

[0090] MALTbase maps the content of the XML document into a relational database and is capable of performing operations on the converted content. The MALTbase conversion strategy is strictly defined, and includes the following steps:

[0091] 1. Ascertain the optimal node element set for a hierarchical structure of a markup language document;

[0092] 2. Assign a unique ID to each node;

[0093] 3. Create a MALTbase DTD through which the converted nodes maybe accessed;

[0094] 4. Convert content as specified hereinafter by decomposing each node in the markup language document into an independent sub-document; and

[0095] 5. Construct a node table to hold the content.

[0096] As a result of the MALTbase conversion, content from the original XML document is contained in a single text field or a Character Large OBject (CLOB) in a single SQL nodes table. A single MALTbase implementation maps any XML document into the same number of tables every time, irrespective of the size or complexity of the document being mapped.

[0097] 1. Establish a Node Element Set

[0098] The first step of MALTbase typically involves selecting the obvious key elements of the hierarchical structure present in the XML document that is to be converted. For example, a document representing an Act of legislation might be broken into a node element set consisting of the node element names: act, chapter, part, division, section, schedule and item. Similarly, a case report might have an associated node element set consisting of the node element names: report, headnote, judgment, paragraph and order.

[0099] The choice of the smallest element in the node element set is dependent upon how the data is maintained and accessed. For optimum utility, it is prudent to include elements down to a level that is appropriate to be dealt with by a single editor. Thus, a sub-sub-paragraph may be a poor choice as this element is at a low level of a typical hierarchy for a document. An editor would likely want to deal with many sub-sub-paragraphs at a time. Similarly, choosing a chapter as the lowest element of the hierarchy in the node element set may be less than ideal as a number of editors would likely wish to make changes to the same chapter contemporaneously.

[0100] FIG. 1 shows a sample fragment of an XML document. Each XML document has exactly one root node, corresponding to content outside of the highest element of a node element set. The hierarchical structure present in the XML fragment might be represented by a node element set consisting of the node element names: chapter, part, section and note. A node is a portion of text corresponding to one of these node elements for the XML document. That is, the node is an instance of one of the node elements Accordingly, the part identified in FIG. 1 as <part shortrefCh 3, Pt A> is a node that has three sub-nodes: sections 56 and 56A and a note.

[0101] 2. Node IDs

[0102] Each identified node in the XML document in turn requires a MALTbase identifier for further processing. A MALTbase node ID is constructed of a set of segments demarcated by a /, so that the ID of a sub-node contains the ID of the sub-node's parent as a prefix. Again, every XML document has exactly one root node, the root node always has a NULL node ID, and the content of the root node is trivial if the main document element is itself a node (which is typically the case). Thus, if the parent ID is /8/50/2/4, then a sub-node's ID might be /8/50/2/4/7. The final segment, 7, is called the child ID of the sub-node.

[0103] The segments reflect the order of the sub-nodes within each parent node. These strings are ordered, so a sub-node inserted between child IDs 6 and 7 might have child ID 6.5. For example, a new intermediate child ID may be identified by a real number between the ID values of the upper and lower adjoining nodes in the node ordering. Other variations on this principle of generating intermediate node ID values may be practised without departing from the scope and spirit of the invention.

[0104] 3. DTD Transform

[0105] An XML document must be valid in relation to a DTD (or Schemathe logic is identical) for the original XML document to be maintained in a MALTbase system. In relation to the content of the original XML document, the content of each sub-node in the original XML document is transferred to an independent sub-document. Modifications to the DTD are required to handle the MALTbase nodes. Every reference to the node in the DTD is (optionally) replaced by a placeholder. In the XML document, a placeholder replaces the content of a sub-node moved into the independent sub-document with a pointer to the respective independent sub-document containing the relevant sub-node.

[0106] In further detail, the DTD transformation thus has three stages:

[0107] (i) defining placeholders;

[0108] (ii) expanding content model; and

[0109] (iii) defining a public identifier for the MALTbase DTD.

[0110] If the node element set is supplied, the transformation may be applied automatically. Where a DTD contains fragments referenced via an XML entity, either the whole DTD can be expanded into a single document by replacing the entity reference with the equivalent text in the DTD and then applying the transformation to the whole DTD, or the additional files making up the DTD can be transformed separately and the entities redefined to point to the modified entities making up the transformed DTD.

[0111] Although technical descriptions in this document relate to DTDs, the principles described can readily be applied to XML Schemas and other markup language formal to definitions for markup rules.

[0112] The MALTbase Namespace

[0113] To transform an XML document into more manageable sub-documents, unique element names must be generated for the node element set. Extra elements must be inserted in the sub-documents to replace existing element names. It is vital that the new is element names do not clash with names already in use. Fortunately, XML provides a means of doing this safely and efficiently.

[0114] The XML Namespace standard (http://www.w3.org/REC-xml-names) provides a mechanism for defining a distinct namespace in which the new elements can reside. This is achieved by inserting an identifying prefix and a colon separator before the existing element name, thus:

[0115] <MALTbase: chapter . . . />.

[0116] This element is completely distinct from the ordinary chapter element shown as a substring in the new element name, and can have different content model and/or attributes. To ensure uniqueness, the namespace must have a distinct Uniform Resource Identifier (URI). This is done by adding a fixed attribute to the element definition of each MALTbase element included in the node set:

	<ATTLIST MALTbase:chapter
	xmlns:MALTbase CDATA FIXED http://malt.com/
	xmlns/MALTbase
	...
	>

[0117] In this way, each MALTbase element name or tag cares a corresponding namespace definition at all times. The word MALTbase and the namespace MALTbase: can be replaced by any suitable word and namespace.

[0118] The namespace URI does not have to contain any particular data. In fact the namespace URI need not exist. It is merely a convenient way of assigning a label that is guaranteed to be unique across the internet. Other methods of generating unique element names may be practised without departing from the scope and spirit of the invention. For example, a long string of irregular characters may be inserted as a prefix to existing element names in the expectation that no such corresponding element names do or will exist.

[0119] Placeholder Definition

[0120] The DTD is modified by defining a placeholder element for each node element in the XML document and the DTD so that content associated with each node can be moved to an independent sub-document. A placeholder is provided in accordance with a strict protocol and acts as a pointer in the separate sub-document to the separate sub-document in which the node's content now resides. The less information that a placeholder contains, the greater the flexibility that is provided. Accordingly, the preferred embodiment of a placeholder has exactly two attributes. The first attribute is the placeholder's namespace definition, which is fixed to a predefined value. In fact, placeholders do not explicitly carry this attribute in the sub-documents, but rather rely on this fixed value. The second attribute is a child-id, which is a string that sorts lexically to define the placeholder's document order with respect to other placeholders in the same parent node.

[0121] For example, consider a chapter from an original DTD that is defined as:

	<ELEMENT chapter (intro, (part section), link)>
	<ATTLIST chapter
	id CDATA REQUIRED
	new-page (yesno) no>

[0122] A placeholder has the same element name as the original element name (chapter), except the placeholder's element name resides in the MALTbase namespace. Accordingly, MALTbase, is inserted as a prefix to the element name chapter to form MALTbase:chapter. A placeholder always has EMPTY content. An empty element is an element that does not contain further elements or data or text. A placeholder is an empty element.

[0123] Continuing the example, the following chapter placeholder needs to be defined in the modified DTD:

<ELEMENT MALTbase:chapter EMPTY>
<ATTLIST MALTbase:chapter
	xmlns:MALTbase
	CDATA FIXED http://www.malt.com/xmlns/MALTbase
	child-id
	CDATA REQUIRED>

[0124] The element name (chapter) is the only thing passed from the original element to the placeholder. All placeholder definitions are otherwise identical.

[0125] Content Model Expansion

[0126] To ensure that a placeholder can always be validly substituted for the original element that the placeholder replaced (and vice versa), the modified DTD must have the following property:

[0127] In every content model, every occurrence of an element in the node element set must be replaced with an expansion for that element and the corresponding placeholder, as alternatives (i.e., an alternation).

[0128] Continuing the above example of the chapter, wherever chapter appears in the original DTD, the modified DTD allows a chapter OR a MALTbase:chapter. For example, the act definition in the original DTD:

	<ELEMENT act (longtitle,
	(chapter part section),
	schedule*)>

[0129] is replaced in the modified DTD as follows:

	<ELEMENT act (longtitle,
	((chapterMALTbase:chapter)
	(partMALTbase:part)
	(sectionMALTbase:section)),
	(scheduleMALTbase:schedule)*)>

[0130] The node element chapter from the original DTD is replaced with (chapterMALTbase:chapter), for example, where is an OR or disjunctive logical operator for alternatives. The same principle applies for other node elements. The references to act and longtitle are unchanged. This is because longtitle was not included in the node element set, and act (in this instance) is not part of the content model. The definition of any parameter entity included in a content model must be similarly modified.

[0131] Public Identifier

[0132] The transformed DTD needs a modified public identifier to differentiate the modified DTD from the original DTD. A simple way to achieve this is to add the word MALTbase to the beginning of the descriptive part of the ID. If the original DTD has a public ID:

[0133] PUBLIC -//XYZ Pty Ltd//Sample DTD//EN

[0134] then the modified DTD has public ID.

[0135] PUBLIC -//XYZ Pty Ltd//MALTbase Sample DTD//EN

[0136] The above points are illustrated in the following example. The original DTD fragment:

	<ELEMENT chapter (label, desc, (part note))>
	<ATTLIST chapter
	shortref CDATA REQUIRED>

[0137] becomes:

<ELEMENT chapter (label, desc,
	((MALTbase:part part) (MALTbase:note note))*)>
<ATTLIST chapter
	shortref CDATA REQUIRED>
<ELEMENT MALTbaae:chapter EMPTY>
<ATTLIST MALTbase:chapter
	child-id CDATA REQUIRED
xmlns:MALTbase CDATA FIXED http://malt.com/xmlns/MALTbase
>.

[0138] The foregoing shows that not all elements (e.g., desc) need have a placeholder In this example, desc and label are elements of the DTD, but are not in the node element set.

[0139] FIG. 2 shows an original DTD fragment 200 for the XML fragment of FIG. 1. The DTD fragment 200 contains a public ID 210 and element declarations 220, 230, 240, 250 and 260 for a chapter, part, section, note and desc, respectively. FIG. 3 shows a MALTbase version 300 of the DTD fragment of FIG. 2. In FIG. 3, the public ID 310 has evidently been modified to incorporate the word MALTbase as a prefix to the descriptor. FIG. 3 also shows the inclusion of a new element with empty content for each node element in the node element set of the document being converted. Thus, the element declaration 320 for a chapter has a corresponding element declaration 325 for a MALTbase:chapter. There are also new element declarations 335, 345 and 355 for MALTbase:part, MALTbase:section and MALTbase:note, respectively.

[0140] FIG. 4a shows a simple DTD. The DTD is shown in the form as the DTD would be supplied by a user. The node element set for the original DTD shown in FIG. 4a consists of (level-1, level-2, level-3).

[0141] FIG. 4b shows a modified DTD corresponding to the original DTD of FIG. 4a . Placeholder elements 410, 420, 430 have been inserted. The public id 440 has been modified to incorporate MALTbase. The content models have been modified such that there is an alternation between the original node elements and the modified node elements, as shown by 450 and 460. Even though level-1 does not appear in any content model, level-1 requires a placeholder so that it may appear in the root node if necessary.

[0142] 4. Document Transform

[0143] After establishing a node element set and modifying the DTD, it is necessary to decompose the original XML document into individual sub-documents corresponding to the individual nodes. Each sub-document must conform to the new DTD. The content of each node takes the form of a discrete sub-document where:

[0144] the DOCTYPE element of the sub-document is the node element;

[0145] a Document Type Definition (DTD) that defines the set of rules for document construction has a public ID identical to that of the original DTD associated with the XML document being converted, except that the word MALTbase is inserted as a prefix to the description to create a new DTD with a PUBLIC identifier that is distinct, but readily derivable from the ID of the original DTD; and

[0146] the fall text of each sub-node is replaced by an empty element, which has a MALTbase: namespace prefix added to the sub-node element's name to distinguish the new MALTbase elements from their original counterparts, which can co-exist in a single document when new nodes are created.

[0147] The pre-processing of MALTbase node content is strictly defined to ensure that the conversion is reversible. The conversion must allow the node content to be accessed and/or modified by standard validating XML editing tools.

[0148] The easiest way to describe the decomposition process is by specifying a set of steps which perform the required transformations. It is important to note, however, that decomposition software need not follow these steps exactly. The software is simply required to produce the same end result as the steps below, regardless of how it is implemented internally. The steps required for this conversion are as follows:

[0149] 1. In the XML document, assemble the XML content of the nodes. This may involve expanding entity references to other original XML files, but only when such references lie directly within the node in question (i.e. not within any sub-node). Some of the content of a node may be stored in a separate file, which is represented in the main document by a file entity reference. These references must be replaced by the expanded XML markup and content that the references represent to get the complete content of a node. However, since the content of any sub-node is not part of a node, such references need not be expanded when the references lie within sub-nodes. Those references are expanded when the sub-node is being processed.

[0150] 2. Create a standalone sub-document for each node of the original XML document by inserting as a prefix the standard XML processing instruction, plus a DOCTYPE declaration, where the DOCTYPE element is the node element, and the public ID is the same as that of the original DTD, except that the word MALTbase is inserted as a prefix to the descriptor.

[0151] For example, if the original XML document begins:

[0152] <xml version1.0>

[0153] <DocTYPE document PUBLIC -//TimeBase//DTD Samrple//EN>

[0154] then the converted sub-document for a chapter node begins:

[0155] <xml version1.0>

[0156] <DOCTYPE chapter PUBLIC -//TimeBase//MALTbase DTD Sample//EN>

[0157] 3. Each node becomes a separate sub-document, while all sub-node elements are replaced by a MALTbase: placeholder.

[0158] 4. Replace any sub-node elements in the sub-documents with equivalent placeholders in which the namespace MALTbase: has been inserted as a prefix to the element name, and the only attribute explicit in the XML data is the child ID (the ID of the sub-node relative to all the other subnodes within the subnode's parent). The additional xmlns:MALTbase attribute, defined in the transformed DTD as a Fixed attribute, establishes a namespace that ensures that the new MALTbase; elements that are being inserted are unique and do not clash with any existing element. The element names must be unique to ensure that MALTbase is able to operate on any arbitrary XML document. So, if the part element also belongs to the node element set, then the internal fragment:

[0159] <part shortrefCh 3, Pt A>. . . </part>

[0160] is replaced by:

[0161] <MALTbase:part child-id80/>

[0162] This enables sub-nodes to be abstracted. Thus, generally, one editor can operate on a part, and another editor can operate on a section within that part without conflict. Accordingly, the original document can be divided into discrete chunks in such a way that if the integrity of each chunk is maintained then the integrity of the entire document is guaranteed. This is a powerful concept, since the need is removed to reverify a (potentially vast) document every time a chunk is changed.

[0163] The Root Node

[0164] Every document has exactly one root node. While every other node is associated with a single element in the node element set, the root node corresponds to the document as a whole. It is here that any XML content outside the outermost node(s) is kept. Where the DOCTYPE element is also a node element, the moot node is trivial. For example, the document:

	<xml version1.0>
	<DOCTYPE act
	PUBLIC -//XYZ Pty Ltd//Sample Document//EN>
	<-- a boring root node -->
	<act year1989 number109>
	<longtitle . . .>
	<chapter . . .>
	. . .
	</act>

[0165] has the root node:

<xml version1.0>
<DOCTYPE MALTbase:act
	PUBLIC -//XYZ Pty Ltd//MALTbase Sample Document//EN>
<-- a boring root node -->
<MALTbase:act child-id1/>

[0166] When the DOCTYPE element is itself a node, it is replaced by a MALTbase placeholder in the root node, and the DOCTYPE is altered accordingly.

[0167] However, when the DOCTYPE element is not a node, such as:

	<xml version1.0>
	<DOCTYPE act-group
	PUBLIC -//XYZ Pty Ltd//Sample Document//EN>
	<-- a non-trivial root node -->
	<act-group typeamending>
	<act year1992 number67> . . . </act>
	<note><p> . . . </p></note>
	<act year1992 number121> . . . </act>
	<act year1992 number213> . . . </act>
	. . .
	</act-group>

[0168] then the root node is not as trivial:

<xml version1.0>
<DOCTYPE act-group
	PUBLIC -//XYZ Pty Ltd//MALTbase Sample Document//EN>
<-- a non-trivial root node -->
<act-group typeamending>
	<MALTbase:act child-id1/>
	<note><p> . . . </p></note>
	<MALTbase:act child-id2/>
	<MALTbase:act child-id3/>
	. . .
</act-group>

[0169] Note that the act-group element (not being a node) does not need to change, and so neither does the DOCTYPE. It is in such a case that the advantage of having a single unique root node to hold material outside the outermost node elements becomes obvious. In particular this strategy ensures that there is a single node tree root even if there are several outermost node elements.

[0170] FIGS. 5a to 5c show the explicit conversion of the root node and two other nodes from the XML document of FIG. 1. The root node is always present, and contains the document down to the outermost node(s). The user defining the node element set decides whether to include the DOCTYPE element in that node element set. Typically, the DOCTYPE element is included in the node element set and is the outermost node corresponding to the highest level of the hierarchical structure of the document being transformed.

[0171] In FIG. 5a, the root node of FIG. 1 has been converted to a MALTbase representation. In particular, the DOCTYPE declaration has been amended such that the DOCTYPE element chapter is now MALTbase:chapter. The chapter sub-node is moved into a separate node document. For each node other than a terminal or leaf node, each MALTbase: element is effectively a sub-node placeholder that refers to a document that contains the sub-node. Terminal or leaf nodes do not contain placeholders, but instead have actual content from the original XML document. The root node of any XML document is not the principal DOCTYPE element, but a nameless node which contains all of the document outside the principal element. The principal element is the element corresponding to the highest level of the hierarchy of the XML document under consideration. The root node is typically trivial, unless the principal element is not itself a node. In the latter case, the root node may have some content from the original XML document.

[0172] Consider a document with DOCTYPE legislation, and a legislation element containing a number of acts. If an act was the highest node in the hierarchy, then the root node contains the legislation element unchanged, with MALTbase:act placeholders for each contained act. Such an example may be atypical, but importantly MALTbase must be able to handle all possibilities that might arise in arbitrary XML.

[0173] The descriptor

[0174] PUBLIC -//TimeBase Ltd //MALTbase DTD Sample Chapter//EN replaces the original descriptor

[0175] PUBLIC -//TimeBase Ltd//DTD Sample Chapter//EN to differentiate the new DTD from the original DTD. The sub-node element is indicated by the expression

[0176] <MALTbase:chapter child-id3/>

[0177] FIG. 5b shows the converted MALTbase representation of Chapter 3 from FIG. 1. The MALTbase representation indicates that the DOCTYPE is a chapter and the word MALbase has been added to the public identifier.

[0178] FIG. 1 shows that Chapter 3 consists of Part A and Part B. Accordingly, FIG. 5b shows the sub-node elements <MALTbase:part child-id1/> and <MALTbase:part child-id2/>. The MALTbase representation of Chapter 3 concludes with the link line and the delimiter </chapter>, The child IDs shown above are purely arbitrary and are always assigned by the system, never by an end user.

[0179] Similarly, FIG. 5c shows the MALTbase representation of Part A of Chapter 3 from FIG. 1. The DOCTYPE declaration line indicates that the DOCTYPE is a part, and the word MALTbase has been inserted into the public identifier.

[0180] FIG. 1 indicates that Part A has two sections and an associated note. Accordingly, three sub-node elements are provided in the MALTbase representation of Part A shown in FIG. 5c.

[0181] FIG. 6a shows a simple XML document conforming to the DTD of FIG. 4a. FIGS. 6b to 6f show the decomposition of the document shown in FIG. 6a. FIG. 6b shows a resultant root node derived from the original document of FIG. 6a Since the DOCTYPE element is a node, the resultant root node 610 is trivial, containing in effect only the initial comment. The root node 610 is the only node which may have a place holder as the DOCTYPE element.

[0182] FIG. 6c shows a classical higher level node 620 corresponding to the level-1 Papa node of FIG. 6a . As can be seen from FIG. 6c, all of the sub-node content (attributes, sub-elements, text) has been removed to an appropriate sub-document. This allows two users to edit the papa and level 2 mama nodes contemporaneously without the possibility of clashing. The content of each node is completely self-sufficient, except that a parent node refers indirectly to the parent node's children via placeholders. It may be noted that the deletion of the level-3 sub-node baby does not affect the level-1 papa node at all.

[0183] FIG. 6d shows the level-2 mama node of the document of FIG. 6a. The mama node 630 has substantive content appearing either side of the level-3 child baby node.

[0184] FIG. 6eshows the level-3 baby node 640 of the document of FIG. 6a. The baby node 640 is a typical terminal node that has no children. Accordingly, this branch of the decomposition process is complete.

[0185] FIG. 6fshows the level-2 goldilocks node 650 of the document of FIG. 6a. The goldilocks node 650 is another terminal node and is structurally identical to the baby node 640 of FIG. 6e.

[0186] The total number of nodes and hence the total number of sub-documents produced by the decomposition process is N1, where N is the total number of occurrences of elements in the node elements set. The extra node is the root node. For each node there is exactly one sub-document and vice versa. The node element of a sub-document will be its DOCTYPE element. The DOCTYPE element of the root node will be the DOCTYPE element of the whole document (if that is not itself a node element) or a placeholder (if the master DOCTYPE element is a node element).

[0187] Each node knows nothing about the node's descendants, except for the identity and placement (but not the content) of the node's immediate children. While information about the ancestors of the node is not contained within the node's XML content, the parent ID of the node does give the identity (but not the type or content) of each of the ancestors of the node.

[0188] It is now possible to construct the first record of the SQL database, where both the parent ID and child ID are NULL, and the content is the root node XML described above.

[0189] 5. Basic SQL Table Structure

[0190] In principle, any document can be mapped to a single SQL table. In practice, additional fields and/or tables may be desired to facilitate particular types of searching or other operations that are to be performed on the data. All such variants are logical extensions of the simple table defined below.

[0191] Having created a number of sub-documents corresponding to each node, a SQL table must be established to allow the nodes to be stored and retrieved as desired. This table must include the following fields:

[0192] a child₁₃ idthe child ID of the node being stored (information that corresponds to the node's relative position within the node's immediate parent);

[0193] parent_idthe ID of the current node's immediate parent in the hierarchy (NULL for the root node); and

[0194] contentthe text of the sub-document corresponding to the current node.

[0195] Other fields may exist optionally in the table to expedite searching (e.g. a node_tag field to store the node element name: chapter, part, etc; or a short_ref field to enable searching for nodes via the contents of a short_ref attribute).

[0196] The Node Hierarchy

[0197] The nodes of a document, like any other XML elements, form a strict hierarchy. At the top of the node tree is the root node, which corresponds to the document as a whole. The remaining nodes are in one-to-one correspondence with the node elements in the document. The hierarchy corresponds similarly. If element B is contained within element A, and no other node elements come between them, then node B lies directly below node A in the hierarchy. In other words, node A is the parent of node B.

[0198] The Child ID

[0199] The child ID is a value which conveys the position of a node with respect to its siblings (ie. other nodes with the same parent). Each child of the same parent must therefore have a unique child ID. A helpful analogy is to regard the child ID as a decimal number. When a document is first converted, the first child of each parent node will be assigned child ID 1, the next 2 and so on. If at some later time a new node is inserted between 1 and 2 then an ID such as 1.5 may be used. The exact values are unimportant, though it is desirable that the creation of extra decimal places be avoided where possible. The only guarantee is that: the child ID of a sibling occurring earlier in the document will always be less than the child ID of a sibling occurring later in the document. Note that child IDs may not necessarily be represented internally as decimal values, but they will always sort in the correct order.

[0200] The Node ID

[0201] The node ID is a string which uniquely identifies both the node and its position in the document. It consists of the ordered set of child IDs of each of the node's ancestors. By convention, each ID is preceded by a / character (though once again the internal representation might differ somewhat to facilitate sorting). Table 1 illustrates a possible set of node IDs.

TABLE 1
Description	parent ID	child ID	full ID
root node	NULL	NULL	/
Crimes Act	/	27	/27
Chapter 3A	/27	3.5	/27/3.5
section 67	/27/3.5	8	/27/3.5/8

[0202] As is evident from Table 1, the parent ID of any node is the full ID of that node's parent, and the full ID of a node is the concatenation of the node's parent ID and child ID. Neither the parent ID nor the child ID of a node need be present in the node content. However, the child ID of a node is present in the content of that node's parent, as the child-id attribute of the corresponding placeholder.

[0203] The Basic Nodes Table

[0204] The nodes table holds one node per record, and requires only three fields; parent_id, child_id and content. The content field is a (possibly quite large) text field or a Character Large OBject (CLOB) containing the converted node XML, or a unique pointer to that text in the sub-documents created during the document decomposition. To speed queries and updates it may be useful to include extra fields or even whole tables. Such additional extra fields and tables may include: XML context, unique and unalterable serial number, or an ancestry table.

[0205] FIG. 7 shows a minimal SQL node table 70 corresponding to the document fragment of FIG. 1. Each row in the node table 70 corresponds to a node. Each node has an associated child_id 72, a parent_id 74 and a content field 76. The content field 76 is a text string containing the MALTbase version of the relevant XML element. These strings may be quite large, but a suitable choice of the node element set will ensure that they are sized appropriately fox a particular application.

[0206] Row 77 corresponds to the mapped content of the root node of FIG. 1, as described above with reference to FIG. 5a. The root node has a NULL child_id and a NULL parent_id. The content_field 76 associated with the root node contains the text root node. Row 78 corresponds to the mapped content of the chapter node of FIG. 1, as described above with reference to FIG. 5b. The chapter node has an arbitrarily assigned child_id 72 of 3 and a parent_id 74 of NULL. Row 79 corresponds to the mapped content of the first part node of FIG. 1, as described above with reference to FIG. 5c. The first part node has a child_id 72 of 1 and a parent_id 74 of /3.

[0207] The node table 70 may in practice be augmented with extra fields to facilitate searching. Such additional fields may include XML element path or shortref. Similarly, a full ancestry table may be provided if rapid navigation through the hierarchy is a priority. Finally, the database technique of record locking can be simplified if each record is assigned a unique, unchangeable serial number (unrelated to document order). A serial number does not change when, for example, two nodes are swapped. Record locking is the database facility which enables one user to update a record, and prevents any other user from attempting to update the same record until the first user is finished.

[0208] Sub-Node Handling

[0209] Having constructed a root node, new sub-documents are constructed to hold the content of each sub-node element. These sub-documents will be valid against the modified DTD, and have the DOCTYPE set to the sub-node element. Thus for the trivial root node example above, the sole sub-node content will be:

<xml version1.0>
<DOCTYPE act
	PUBLIC -//XYZ Pty Ltd//MALTbase Sample Document//EN>
<act year1989 number109>
	<longtitle . . .>
	<chapter child-id1/>
	. . .
</act>

[0210] After root node processing, it is guaranteed that there will be exactly one outermost node per sub-document, which will always be the DOCTYPE node. The next step is to search the DOCTYPE node for sub-nodes. For each sub-node in the DOCTYPE node, insert a corresponding placeholder and construct a new sub-document. The original sub-document now looks like:

<xml version1.0>
<DOCTYPE act
	PUBLIC -//XYZ Pty Ltd//MALTbase Sample Document//EN>
<act year1989 number109>
	<longtitle . . .>
	<MALTbase:chapter child-id1/>
	. . .
</act>

[0211] It is possible to create a new database record in which the parent ID is the full ID of the parent node (/ if the parent is the root node), the child ID matches the child-ID of the placeholder which replaced this node in the parent's content, and the content is the content of the node after sub-node substitution.

[0212] This step is repeated for the new sub-document(s), and is reiterated until no sub-document contains more than one node element. At such a point, the decomposition is complete.

[0213] FIG. 8 shows a sample node table 800 arising from the decomposition shown in FIGS. 6a to 6f. Row 810 corresponds to the root node 610 of FIG. 6b. The root node has a parent id of NULL and a child id of NULL. Row 820 corresponds to the papa node 620 of FIG. 6c, having a parent id of / and a child id of 1. The child id of 1 indicates that the papa node is the first child of the root node 610. Row 830 corresponds to mama node 630 of FIG. 6d, that has a parent id of /1 and a child id of 1. Similarly, row 840 corresponds to baby node 640 of FIG. 6ethat has a parent id of /1/1/ and a child id of 1. Finally, row 850 corresponds to the terminal goldilocks node 650 of FIG. 6f that has a parent id of /1 and a child id of 2. The child id of 2 indicates that the goldilocks node is the second child of the papa node 620. The child ID field must match the child ID attribute in the parent node.

[0214] Document Reconstruction

[0215] A method, an apparatus and a computer program product for reconverting a MALTbase SQL table set back into equivalent XML is described.

[0216] The process proceeds as follows:

[0217] 1. Create an XML document from the root node (NULL parent_id) content in which the MALTbase prefixes are removed from DTD public ID and the DOCTYPE (if present).

[0218] 2. Let the current node be initially set to the root node.

[0219] 3. Establish the set of immediate children of the current node with a SQL command such as:

	SELECT *
	FROM nodes
	WHERE parent_id current_node
	ORDER BY child_id

[0220] 4. If no immediate children exist, the reconstruction of the current node is complete.

[0221] 5. Otherwise, for each child node, replace the corresponding MALTbase (empty) sub-node element with the reconstructed content of the node, which is obtained by:

[0222] isolating the sub-node element data (i.e. removing the XML instruction, DOCTYPE, and xlmns:MALTbase attribute from the content field);

[0223] setting the current node to be the sub-node;

[0224] recursively applying steps 3 to 5 until all descendant nodes have been reconverted.

[0225] The end result of this process is a monolithic XML document that contains the same content as the original document (of course, incorporating any changes made while the document was in SQL form).

[0226] If the original document was split over a number of files (for example using file entity references), a requirement of the reconversion may be that the original file structure also be recovered. This can be achieved by inserting appropriate processing instructions, such as:

[0227] <MALTbase entity&ch3-ptA; file. . . /ch3/ptA.xml >

[0228] during the initial conversion and using these embedded codes to redirect the reconstructed nodes to the appropriate output file.

[0229] SQL Document Access/Maintenance

[0230] The decomposition of a large XML document into independent smaller sub-documents is simply a means to an end. It is important to be able to access and modify the information in these sub-documents. A method, an apparatus and a computer program product for maintaining an XML document in MALTbase SQL form, without the need for reconverting the document to XML, are described.

[0231] A primary use of MALTbase is to store complex XML documents within SQL databases. In general, the node element set is chosen so that each node represents a reasonable portion of the data to retrieve or maintain. Since the converted node content is already in the form of a standalone XML document, any standard XML author/editing tool can be used to examine or modify the content.

[0232] MALTbase allows five basic node operations:

[0233] modify an existing node

[0234] insert a new node (or sub-tree)

[0235] delete an existing node (or sub-tree)

[0236] copy an existing node (or sub-tree) to a new location

[0237] relocate placeholders within a node

[0238] In particular, if this standard XML author/editing tool supports an interface with an SQL Application Programming Interface (API), an editing session consists of the following steps:

[0239] locate the node to be edited (all editing is on a per node basis);

[0240] activate an edit function which:

[0241] locks the node for writing; and

[0242] establishes an edit session in which the editing tool manages the node content; and

[0243] when the edit session is finished, the updated content is written back into the node record.

[0244] Modify an Existing Node

[0245] Simple modification involves a change to a node which does not affect.

[0246] the node's DOCTYPE element

[0247] any element in the node element set

[0248] any placeholder

[0249] This operation is the most staightforward. Simply open the node, update the content, and save. The modify operation is the only operation performed on the target node itself. All other operations are performed on the parent of the node being inserted, deleted, etc.

[0250] Insert a New Node

[0251] To insert a new node, first open the parent of the node to be created. The parent node will have to contain a placeholder for the new node. However, a placeholder cannot be created directly, as placeholder management is a MALTbase system function. Further, there is no current node to which a placeholder can point.

[0252] A solution is to enter the new material in situ, just as if editing the original document. For example, to create a new section in an act, open the act and simply key in the new section in the desired location. Use <section> elements and not <MALTbase: section/> in this procedure. Inside the section element, key the content normally. Node elements may be included in this content, where permitted by the DTD. When all the new material has been keyed, save the edited node.

[0253] At this point, the MALTbase system takes over. MALTbase routinely examines all updated nodes before saving the updated nodes. If MALTbase detects any node elements within a node, MALTbase will automatically decompose the node elements into as many new sub-nodes as are required, and replace the outermost sub-node with a placeholder In effect, this is exactly the same process as was used to convert the original document, only limited to the content of a single node. This process cannot affect the validity of the master document, as the editing application will have validated the modified node prior to saving.

[0254] Delete an Existing Node

[0255] To delete a node, edit the node's parent and delete the appropriate placeholder. The editing application will ensure that such a deletion is valid. When saving the edited parent, the MALTbase system compares the list of child IDs with a list prepared by the system when the parent node was opened. If any placeholders are missing, then the corresponding nodes (and any descendants) are deleted from the system. In this way, the validity of the whole document is maintained provided the validity of each individual node is preserved.

[0256] Copy an Existing Node

[0257] To copy a node, the node ID of the node to be copied must be known. Edit the node that will be the parent of the new copy, and insert a placeholder with an element name and child-id set to the ID of the node to be copied. If the node to be copied is not already a child of the parent, the full child ID is used, rather than just the final segment. The editing application will ensure that such an insertion is valid. When saving the edited parent, the MALTbase system will locate the nodes which have been amended in this way. A duplicate node will be created with identical content to the original, but with a parent ID set to the parent node that was edited. Any descendants will also be copied and be assigned new Ids, as appropriate, based on the parent ID and order amongst the node's existing child nodes.

[0258] Note that the child-id entered on the new placeholder must be a valid ID for an existing node somewhere in the master document.

[0259] It is not possible to create new nodes using this technique. Either an absolute or relative ID may be used. An absolute ID begins with / and gives a fall path down from the root node, whereas a relative ID begins with ./ and relates the child to the current parent. Absolute IDs are typically used except where the node to be copied is already a child of the new parent. The presence of the slash character in the child-id tells the system that an existing child node is not simply being relocated. Whatever form of child-id is used, the copy will be assigned a new regular child ID and the placeholders will be altered to reflect this.

[0260] Relocate Child Nodes within a Parent

[0261] It is possible to move existing placeholders to any valid location within a node being edited. This is a simple modification (see above) provided that the placeholders remain in the same order with respect to each other. However, if editing does affect the order of the placeholders, then a relocation operation will be triggered when saving the node.

[0262] As is the case for deletions, the system detects relocations by comparing a list of placeholders with a list of placeholders constructed before the editing session. The system assigns new child IDs to as many sub-nodes as necessary to ensure that the IDs once again correctly reflect the order of the child nodes within the parent node. These new IDs will also be applied to all descendants of affected nodes.

[0263] Database Operation Examples

[0264] FIGS. 9a to 9d illustrate the results of various database operations. FIG. 9a shows the result of a simple modifier operation, in which text is inserted into the level-2 mama node. As the modification only affects the content of the node and no placeholders are affected, the new text is simply inserted.

[0265] FIG. 9b shows the result of a delete database operation. In this particular example, the level-3 child node is deleted and the mama node is now childless. The MALTbase system will automatically remove the deleted node when this Mama node is saved.

[0266] FIG. 9c shows the result of an insertion of a new level-2 node. The new level-2 node is inserted directly into the perspective parent node, in this case the level-1 papa node shown in FIG. 9c(1).

[0267] When the level-1 papa node is saved, a new node having an id of 1/1.5 is created, as shown in FIG. 9c(2). The text inserted into the level-2 papa node is replaced by a placeholder, as shown in FIG. 9c(3).

[0268] FIG. 9d illustrates the relocation of existing placeholders. FIG. 9d(1) shows that the mama node has been moved and now appears after the goldilocks node. On being saved, the MALTbase system modifies the child ids of the sub-nodes of the level-1 papa node so that the child ids stay in ascending order. Accordingly, FIG. 9d(2) shows s that the child-id of the mama node has been modified and is now 3.

[0269] Document Integrity

[0270] The chief value of the MALTbase system is that MALTbase guarantees that the whole master document will remain valid throughout any amount of editing and updating of the node sub-documents. In practice, this guarantee rests on three fundamental principles:

[0271] 1. Each node document must at all times remain valid against the modified DTD;

[0272] 2. The integrity of the interrelationships between the nodes, embodied in the database, must be preserved; and

[0273] 3. The constraints which ensure the successful reassembly of the nodes into a master document must be honoured.

[0274] The following sections explain these principles in greater detail.

[0275] Node Validity

[0276] Clearly, if the individual node documents are compromised, there is no way that the integrity of the master document can be maintained, let alone guaranteed. Fortunately, any validating XML editor will take care of this, and the MALTbase system will immediately reject any attempt to save an invalid node document.

[0277] Database Integrity

[0278] This is a much more subtle requirement, and correspondingly harder to police. Part of the requirement is handled by the MALTbase system when it analyses the placeholders of incoming nodes. The system will reject any node which:

[0279] has a placeholder referring to a non-existent node;

[0280] has a placeholder whose element type does not match the corresponding node; or

[0281] has duplicate placeholders, except for those with child Ds beginning with / or ./ (which imply a copy operation)

[0282] It should be noted that all of the above constraints can be violated by a valid node document. Since MALTbase allows many nodes to be edited simultaneously, it must also prevent inadvertent conflicts between these operations. This is done via the database locking mechanism.

[0283] A modern database will typically support both read and write locks at the record (i.e. node) level. A read lock prevents a node from being updated for the duration of the lock, but allows any number of simultaneous read operations. A write lock prevents any access to the locked record for the duration of the lock.

[0284] Thus, whenever a first user wishes to edit a node, the system attempts to obtain a write lock on that node. If another user is accessing the node, the attempt to lock will fail and the system will advise the first user that:

[0285] The node is currently locked by another user, please try again later.

[0286] If the lock succeeds, the first user has exclusive access to the node during the editing session.

[0287] If a user aborts an editing session without saving, the system releases the lock and frees the node. However, if a user attempts to save the node, and assuming all placeholders are valid, the following actions occur:

[0288] Simple Modifythe node content field is updated and the lock is released.

[0289] Insertionnew nodes are created, and the parent node saved, in a single indivisible transaction after which all locks are released. If any part of the operation fails then the state of the database reverts back to what it was immediately prior to the edit session (a process known as rollback).

[0290] Deletionwrite locks are obtained on the node to be deleted, and all descendants of that node. The mass deletion and writeback of the original parent node form a single transaction.

[0291] Copyread locks are obtained on the node to be copied, and all descendants of that node. The mass copy, assignment of new IDs, and writeback of the target parent node form a single transaction.

[0292] Relocationwrite locks are obtained on all affected child nodes, and all descendants of that node. Assignment of new IDs, and writeback of the original parent node form a single transaction.

[0293] The important thing is that exclusive access to all the nodes being updated must be obtained before any part of the update can proceed. In this way, the linkage between placeholders and the corresponding node content is maintained and complex operations can proceed in parallel without threatening the integrity of the database.

[0294] The successful implementation of the method described above depends on two factors:

[0295] the XML validity of the whole document must be maintained; and

[0296] the integrity of the database itself must be preserved, so that the various operations (modify, delete, move etc.) must be correctly interlocked with each other by means of suitable database locks and transactions.

[0297] The XML validity of the whole document is guaranteed because of the DTD transform through which individual node documents are created. Since each occurrence of a sub-node placeholder in a content model is paired precisely with an occurrence of the original element in that model, it follows that substituting a placeholder for a sub-node (or vice versa) has no effect on the validity of the whole. Thus, provided that a node document remains always valid and every sub-node marker corresponds to a real node document before saving the text in the database, a back conversion into XML always yields a valid document.

[0298] The second criterion, preserving database integrity, is a more complex matter and must be enforced by the use of appropriate relational database management system (RDBMS) mechanisms during the implementation. The first precaution is that a write (exclusive) lock must be obtained on a node record before an edit session may commence. This prevents any other user editing the node at the same time, but may leave both descendants and ancestor nodes free for editing (except if someone tries to delete a sub-tree which includes the node of interest).

[0299] Such considerations, however, are standard RDBMS practice and familiar to persons skilled in the art. The additional processes accompanying the write-back of a node into the database are of greater interest. To avoid potential confusion, the term principal node denotes the node that was modified and is being saved, and sub-node denotes one of the new or existing sub-nodes of the principal node. A placeholder is an empty MALTbase element that marks the location of a sub-node within the text of the principal node. The main steps involved in saving a modified principal node are as follows.

[0300] Generate a list of placeholders (if any) in the principal node. If any placeholder does not correspond with an actual database node, an error arises.

[0301] Generate a list of existing sub-nodes from the database, and pair off placeholders and sub-nodes.

[0302] If any sub-node is not matched against a placeholder, that sub-node and all the descendants of that sub-node are deleted from the database;

[0303] If any placeholder is not matched against a sub-node, either an existing sub-node is being duplicated, or a node elsewhere in the database is being copied.

[0304] Create the duplicate nodes (including descendants if any) and assign a provisional ID to each duplicate node. The ID consists of: the ID of the principal node, a provisional child ID within the principal node, and the trailing portion of the ID, if the new node is a descendant of the node being copied.

[0305] Scan the list of matched placeholders in document order. If any such placeholder has a lower child ID than one or more of its siblings already processed, assign a provisional child ID.

[0306] If there are any sub-node elements (as opposed to placeholders) present, perform a standard MALTbase XML-to-SQL conversion on each such clement and create new SQL records for each. Assign a provisional ID to each new node, assigning a provisional child ID within the principal node. Replace the text of each sub-node element in the principal node with a new placeholder.

[0307] A principal node now exists in which each placeholder corresponds to a unique new or existing sub-node, and all with provisional child IDs (except for existing sub-nodes which retain the previous ordering). The final step is to assign permanent child IDs to the placeholders, replacing the provisional segment in the ID of each corresponding sub-node (or descendant). The new IDs are normally chosen to evenly fill the range between the previous existing child ID (or 0 if none) and the following existing child ID (or fff . . . ), using as few hex digits as possible.

[0308] Additional Constraints

[0309] There are a few additional constraints required by a MALTbase system that are not directly related either to database integrity or sub-document validity. These constraints are required to ensure that the reverse transform (node set to single XML document) works properly.

[0310] The first requirement is that the DTD cannot be freely altered while the document is stored as a node set. If the DTD is to be changed, one of two things must happen:

[0311] 1. The master document is reassembled prior to the change and the MALTbase to version reconstructed after the change; and

[0312] 2. The whole database is locked for the duration of the change, and every sub-document successfully revalidated before the locks are released.

[0313] The second requirement is that the DOCTYPE element of a sub-document cannot be freely altered This is because, while the sub-document itself is validated by the XML editor, the new element type (amid hence the new element type's matching placeholder) may not be valid within the parent node's content. If such a change is required, it must be performed as follows:

[0314] 1. Copy the content of the node to be modified to a temporary holding area;

[0315] 2. Edit the parent, delete the corresponding placeholder, and insert the stored content in its place;

[0316] 3. Modify the content to change the element type;

[0317] 4. If the content contains placeholders of its own, the child-id attributes must be modified from CCC to ./NNN/CCC, where CCC is the current value of the attribute, and NNN is the child-id of the content being edited (i.e. the child-id of the placeholder removed in step 2); and

[0318] 5. When the parent node is saved, the original child and the original child's descendants will be deleted. Before this happens, any sub-nodes specified in step 4 (and such sub-nodes' descendants) will be copied. So in effect, an insert is performed, followed by a copy, followed by a delete.

[0319] The above technique will work even in the unlikely event that the new element type is not itself a node element. Any attempt to alter a node simply by changing the node's DOCTYPE element will be blocked by the system, which stores the DOCTYPE of each node before the node is edited.

[0320] The final constraint is that the node element set cannot be altered for a MALTbase document. If the node elements do need to be adjusted, then the master document must be reassembled. The master document can then be decomposed back into MALTbase form using the new node element set.

[0321] FIGS. 10a-10f show a graphical representation of a SQL node write back. FIG. 10a shows an exemplary principal node 1000 relating to a chapter 7 that has first, second, third and fourth parts 1001, 1002, 1003 and 1004, respectively, and a note 1005. Each of the first, second, third and fourth parts 1001, 1002, 1003 and 1004 and the note 1005 has an associated child-id. The first part 1001 has a child-id 1, the second part 1002 has a child-id 4, the third part 1003 has a child-id 7, the fourth part 1004 has a child-id a, and the note 1005 has a child-id d. The additional processes accompanying the write-back procedure of a node into the database are now illustrated using the principal node 1000 of FIG. 10a.

[0322] The write-back procedure is considered in an example in which: (i) a part of the principal node 1000 of FIG. 10a is replaced with a part from another location; (ii) a part of the principal node 1000 of 10a is duplicated (perhaps as a preliminary to splitting the material into two new parts); and (iii) a completely new part is inserted into the principal node 1000 of FIG. 10a.

[0323] FIG. 10b shows the editing of the principal node 1000 to create a modified node 1000a by moving, inserting and deleting placeholders corresponding to existing nodes. New sub-node elements are inserted to create new nodes. A fifth part 1006 from another location replaces the second part 1002 of FIG. 10a. The fourth part 1004 of FIG. 10a is duplicated and the duplicate appears as a new sixth part 1004a. Further, a completely new part 1007 is inserted into the modified node 1000a.

[0324] The XML editing application being used (for example, XMetal, Epic, XML Spy) ensures that the new modified node 1000a is valid and the MALTbase strategy ensures that the wider document is also valid. When saving the modified node 1000a shown in FIG. 10b, the following steps occur:

[0325] 1. Generate a list of placeholders: 1, /8/C/3b/2, a, 7, a, d. These placeholders are the child-ids of the parts and the note of the modified node 1000a;

[0326] 2. Generate a list of existing sub-nodes: 1, 4, 7, a, d. These are the child-ids associated with the parts and the note of the node 1000 of FIG. 10a;

[0327] 3. Generate a list of unmatched sub-nodes: 4. Any such sub-node and each such sub-node's associated descendants are deleted In this case, the second part 1002 of FIG. 10a, having a child-id of 4, is deleted, along with any of the second part's descendants; and

[0328] 4. Generate a list of unmatched placeholders: /8/c/3b/2, a. Any such nodes having unmatched placeholders are duplicated, along with any associated descendants, and provisional IDs are assigned to the duplicated nodes.

[0329] FIG. 10c shows the further modified node 1000b in which provisional IDs have been assigned to each of the new fifth part 1006 and fourth part 1004. FIG. 10d shows the allocation of provisional IDs to any placeholder that is out of order. In this instance, the third part 1003 having a child-id of 7 is deemed to be out of order and a new provisional id of 3 is assigned.

[0330] FIG. 10e shows the conversion of any sub-node elements and the replacement of placeholders. The new fifth part 1007 is assigned an id of 4.

[0331] FIG. 10f shows the next stage in the write-back process, in which new child IDs are allocated to placeholders and corresponding nodes and any descendants. If all steps are successful, all such modified nodes are saved. If any step fails, the procedure rolls back to the previous state.

[0332] An analysis of the above process confirms that, provided all the steps are carried out as a single database transaction, the integrity of the database is retained. If any step fails, the whole operation has to be rolled back and the user prompted to abort or try again. Examples of potential failure include child-id attributes that do not correspond to an existing node, failure to obtain read locks on sub-trees being copied etc. However, since the time that any node (other than the principal node) is locked is only a fraction of a second, deadlocks should be rare given the normal access patterns of users within XML text files. Various techniques (such as analyzing child IDs to minimize node ID modifications) can of course be used to increase efficiency.

[0333] General

[0334] A strategy and software, to be known as MALTbase, have been described for converting arbitrary XML data into SQL tables. Unlike conventional object-relational mapping techniques, MALTbase is designed to produce an optimal SQL table set with a minimum of tables and records, but which contains sufficient information for the original XML to be reconstructed on demand. In this way, the performance and management benefits of using SQL are maximized.

[0335] MALTbase is a technology which facilitates the storage and maintenance of very large XML documents. It does this by breaking the original (master) document into a large number of nodes, each of which resides in its own sub-document. A MALTbase node is defined to be the content of any of a set of nominated elements (the node element set). The important distinction between a node and an element is that a node does not explicitly contain the content of any sub-node. Instead, the sub-nodes within a node are represented by placeholders, which are empty tags marking the position of a sub-node, and pointing to the relevant sub-node document.

[0336] One of the greatest benefits of this system is that the nodes are created in such a way that: if you ensure the validity of each node, then the validity of the entire document is guaranteed. It is difficult to overstate the importance of this point, since this feature allows a user to update a single node in isolation. Provided a user's updates leave the node valid against the DTD (as all good XML editors should), then the user can be confident that the larger document as a whole will also be valid, without having to examine anything outside the scope of the node/s being modified.

[0337] The method of converting XML data into SQL tables is preferably practised using a general-purpose computer system 1100, such as that shown in FIG. 11 wherein the processes of FIGS. 3 to 10 may be implemented as software, such as an application program executing within the computer system 1100. In particular, the steps of a method of converting XML data into SQL tables are effected by instructions in the software that are carried out by the computer. The instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part performs one or more methods of FIGS. 3 to 10 and a second part manages a user interface between the first part and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for FIGS. 3 to 10.

[0338] The computer system 1100 comprises a computer module 1101, input devices such as a keyboard 1102 and mouse 1103, output devices including a printer 1115 and a display device 1114. A Modulator-Demodulator (Modem) transceiver device 1116 is used by the computer module 1101 for communicating to and from a communications network 1120, for example connectable via a telephone line 1121 or other functional medium. The modem 1116 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

[0339] The computer module 1101 typically includes at least one processor unit 1105, a memory unit 1106, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output (I/O) interfaces including a video interface 1107, and an I/O interface 1113 for the keyboard 1102 and mouse 1103 and optionally a joystick (not illustrated), and an interface 1108 for the modem 1116. A storage device 1109 is provided and typically includes a hard disk drive 1110 and a floppy disk drive 1111. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive 1112 is typically provided as a non-volatile source of data The components 1105 to 1113 of the computer module 1101 typically communicate via an interconnected bus 1104 and in a manner which results in a conventional mode of operation of the computer system 1100 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

[0340] Typically, the application program is resident on the hard disk drive 1110 and read and controlled in its execution by the processor 1105. Intermediate storage of the program and any data fetched from the network 1120 may be accomplished using the semiconductor memory 1106, possibly in concert with the hard disk drive 1110. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 1112 or 1111, or alternatively may be read by the user from the network 1120 via the modem device 1116. Still farther, the software can also be loaded into the computer system 1100 from other computer readable media. The term computer readable medium as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 1100 for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 1101. Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including email transmissions and information recorded on websites and the like.

[0341] The method of converting XML data into SQL tables may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of FIGS. 3 to 10. Such dedicated hardware may include one or more microprocessors and associated memories.

[0342] Industrial Applicability

[0343] It is apparent from the above that the arrangements described are applicable to any industry that has a need to efficiently access and/or modify XML encoded text-based data, also referred to as document-centric XML. Examples are the electronic publishing industry, document management, publishers and service providers dealing with requirements engineering documents, journal articles, manuals, software and other online help, etc.

[0344] The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.