Array-based extensible document storage format

• US 6,938,204 B1
• Filed: 08/31/2000
• Issued: 08/30/2005
• Est. Priority Date: 08/31/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hind, John R., Li, Yongcheng, Tan, Yih-Shin
• Primary Examiner(s): Feild, Joseph
• Assistant Examiner(s): HILLERY, NATHAN
• Application Number:
  US09/652,296
• Time in Patent Office: 1,825 Days
• Field of Search: 715/515, 715/513, 707/101, 707/102
• US Class Current: 715/234
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Systems and computer program products are provided having a plurality of arrays used to represent structured documents. The arrays include an element name array including an element name entry for each element in the structure document, an element value array including an element value entry for each element in the structured document, an attribute array including an attribute entry for each element in the structured document, a parent array including a parent entry for each element in the structured document and a child array including a child entry for each element in the structured document, The value of each parent entry identifies a parent of the element and the value of each child entry identifies zero or more children of the element.

Claims

1. A computer program product embodied on one or more computer-readable media, the computer program product adapted for representing a source document encoded in an extensible structured notation using a plurality of arrays and comprising:

computer-readable program code means for generating an element name array, the element name array comprising an element name entry for each element in the source document, wherein each element name entry specifies a starting name position and one of (1) a name length or (2) an ending name position;

computer-readable program code means for generating an element value array, the element value array comprising an element value entry for each element in the source document, wherein each element value entry specifies a starting value position and one of (1) a value length or (2) an ending value position;

computer-readable program code means for generating a parent array, the parent array comprising a parent entry for each element in the source document and wherein a value of each parent entry identifies a parent of the element;

computer-readable program code means for generating a child array, the child array comprising a child entry for each element in the source document and wherein a value of each child entry identifies zero or more children of the element; and

computer-readable program code means for storing the generated arrays in memory or writing the generated arrays to one or more storage media.

2. The computer program product according to claim 1, further comprising:

computer-readable program code means for generating an attribute array, the attribute array comprising an attribute entry for each element in the structured document, wherein each attribute entry specifies a reference to a secondary array and wherein the secondary array comprises a secondary attribute entry for each of one or more attributes of those ones of the elements which have attributes, and a null value otherwise; and

wherein each secondary attribute entry specifies a starting name position and one or (1) an ending name position or (2) a length for a name of the attribute, and a starting value position and one or (1) an ending value position or (2) a length for a value of the attribute.

3. The computer program product according to claim 1, wherein the extensible structured notation is XML (Extensible Markup Language).

4. The computer program product according to claim 1, further comprising computer-readable program code means for generating an output structured document from the arrays.

5. A computer program product embodied on one or more computer-readable media, the computer program product adapted for creating a plurality of arrays to represent a source document encoded in a machine-oriented extensible structured notation (“

mXML”

) and comprising;

computer-readable program code means for obtaining a node count from the source document;

computer-readable program code means for generating the arrays based on the node count; and

computer-readable program code means for processing a plurality of node specifications from the source document, further comprising;

computer-readable program code means for obtaining an element name specification from the node specification;

computer-readable program code means for storing element name information in an element name army, using the element name specification;

computer-readable program code means for obtaining an attribute list specification from the node specification;

computer-readable program code means for storing attribute information in an attribute array, using the attribute list specification;

computer-readable program code means for obtaining a child list specification from the node specification;

computer-readable program code means for storing child information in a child array, using the child list specification;

computer-readable program code means for storing parent information in a parent array, using the child list specification;

computer-readable program code means for obtaining an element value specification from the node specification; and

computer-readable program code means for storing element value information in an element value array, using the element specification.

6. The computer program product according to claim 5, further comprising computer-readable program code means for generating an output mXML document by traversing the plurality of arrays.

7. A computer program product embodied on one or more computer-readable media, the computer program product adapted for transforming a structured document and comprising:

computer-readable program code means for creating an array-based representation of the structured document, further comprising;

computer-readable program code means for creating an element name array to store information pertaining to a name of each of a plurality of elements in the structured document;

computer-readable program code means for creating an element value array to store information pertaining to a value of each of the elements;

computer-readable program code means for creating an attribute array to store information pertaining to a name and a value of each of zero or more attributes of each of the elements;

computer-readable program code means for creating a parent array to store information pertaining to a parent of each of the elements; and

computer-readable program code means for creating a child array to store information pertaining to zero or more children of each of the elements;

computer-readable program code means for obtaining an identification of a particular element of the structured document which is to be transformed;

computer-readable program code means for locating an entry for the particular element in the arrays-based representation; and

computer-readable program code means for transforming information represented by the located entry.

8. The computer program product according to claim 7, wherein the identification is an element name and wherein the computer-readable program code means for locating further comprises computer-readable program code means for searching the element name array to find a match with the identification.

9. The computer program product according to claim 7, wherein the identification is an ordinal representing a relative position of the particular element in the structured document, and wherein the computer-readable program code means for locating further comprises computer-readable program code means for using the ordinal as an index to access one or more of the arrays in array-based representation.

10. A method for representing a source document encoded in an extensible structured notation using a plurality of arrays, comprising the steps of:

generating an element name array, the element name array comprising an element name entry for each element in the source document, wherein each element name entry specifies a starting name position and one of (1) a name length or (2) an ending name position;

generating an element value array, the element value array comprising an element value entry for each element in the source document, wherein each element value entry specifies a starting value position and one of (1) a value length or (2) an ending value position;

generating a parent array, the parent array comprising a parent entry for each element in the source document and wherein a value of each parent entry identifies a parent of the element;

generating a child array, the child away comprising a child entry for each element in the source document and wherein a value of each child entry identifies zero or more children of the element; and

storing the generated arrays in memory or writing the generated arrays to one or more storage media.

11. The method according to claim 10, further comprising the steps of:

generating an attribute array, the attribute array comprising an attribute entry for each element in the structured document, wherein each attribute entry specifies a reference to a secondary array and wherein the secondary array comprises a secondary attribute entry for each of one or more attributes of those ones of the elements which have attributes, and a null value otherwise; and

wherein each secondary attribute entry specifies a starting name position and one or (1) an ending name position or (2) a length for a name of the attribute, and a starting value position and one or (1) an ending value position or (2) a length for a value of the attribute.

12. The method according to claim 10, wherein the extensible structured notation is XML (Extensible Markup Language).

13. The method according to claim 10, further comprising the step of generating an output structured document from the arrays.

14. A method for creating a plurality of arrays to represent a source document encoded in a machine-oriented extensible structured notation (“

mXML”

), comprising the steps of;

obtaining a node count from the source document;

generating the arrays based on the node count; and

processing a plurality of node specifications from the source document, further comprising the steps of;

obtaining an element name specification from the node specification;

storing element name information in an element name array, using the element name specification;

obtaining an attribute list specification from the node specification;

storing attribute information in an attribute array, using the attribute list specification;

obtaining a child list specification from the specification;

storing child information in a child array, using the child list specification;

storing parent information in a parent array, using the child list specification;

obtaining an element value specification from the node specification; and

storing element value information in an element value array, using the element specification.

15. The method according to claim 14, further comprising the step of generating an output mXML document by traversing the plurality of arrays.

16. A method for transforming a structured document, comprising the steps of:

creating an array-based representation of the structured document, further comprising the steps of;

creating an element name array to store information pertaining to a name of each of a plurality of elements in the structured document;

creating an element value array to store information pertaining to a value of each of the elements;

creating an attribute array to store information pertaining to a name and a value of each of zero or more attributes of each of the elements;

creating a parent array to store information pertaining to a parent of each of the elements; and

creating a child array to store information pertaining to zero or more children of each of the elements;

obtaining an identification of a particular element of the structured document which is to be transformed;

locating an entry for the particular element in the arrays-based representation; and

transforming information represented by the located entry.

17. The method according to claim 16, wherein the identification is an element name and wherein the locating step further comprises the step of searching the element name array to find a match with the identification.

18. The method according to claim 16, wherein the identification is an ordinal representing a relative position of the particular element in the structured document, and wherein the locating step further comprises the step of using the ordinal as an index to access one or more of the arrays in the array-based representation.