# US 2002/0120630 A1 · Method and apparatus for storing semi-structured data in a structured manner

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0120630 A1
- Document ID: US20020120630A1
- Status: Published application
- Kind: A1
- Application number: 09/921,010
- Filed: 2001-08-01
- Published: 2002-08-29
- Earliest claimed: 2000-03-02
- Assignees: Actuate Corporation
- Inventors: David B. Christianson; Denise L. Draper; Konstantin L. Kommissarchik
- Web page: https://patentgrep.com/patent/US20020120630A1

## CPC

- G06F 16/258: {Data format conversion from or to a database}
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- Y10S 707/99945: Object-oriented database structure processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

In response to the provision of a collection of semi-structured data (or its schema), a mapper generates a structured organization to store the collection of semi-structured data. The mapper further collaterally generates a description of how the semi-structured data are stored under the structured organization. In one embodiment, normalized relational tables are used for the structured organization. In alternate embodiments, non-normalized relational tables or other structured organization may also be used. The reverse, that is, the creation of a semistructured data organization for a collection of structured data may also be performed.

## Claims

### Claim 1

A computer-readable medium containing a data structure for mapping between semi-structured data and structured data, the data structure comprising:
for each parent and child relationship in the semi-structured data, a mapping from a parent identifier and a child identifier of the parent and child relationship to a table identifier of a table in the structured data that corresponds to the parent and child relationship.

### Claim 2 (depends on 1)

The computer-readable medium of claim 1 wherein each mapping further includes a parent key identifier and a child key identifier of the table that correspond to the parent identifier and child identifier of the mapping.

### Claim 3 (depends on 2)

The computer-readable medium of claim 2 wherein each mapping further includes an indicator of whether a child of the parent and child relationship is an attribute or an element.

### Claim 4 (depends on 1, 2, 3)

The computer-readable medium of claims 1-3 wherein the data structure supports recursive definition of elements of the semi-structured data.

### Claim 5 (depends on 1, 2, 3, 4)

The computer-readable medium of claims 1-4 wherein the semi-structured data is in XML format.

### Claim 6 (depends on 1, 2, 3, 4, 5)

The computer-readable medium of claims 1-5 wherein the structured data is in a relational format.

### Claim 7 (depends on 1, 2, 3, 4, 5, 6)

The computer-readable medium of claims 1-6 wherein the data structure includes for each child of a parent and child relationship that is also not a parent, a mapping from the child identifier of that child to a table identifier of a table in the structured data.

### Claim 8 (depends on 7)

The computer-readable medium of claim 7 wherein the mapping from the child identifier of that child also maps to a child key identifier in the table.

### Claim 9 (depends on 7, 8)

The computer-readable medium of claims 7-8 wherein the mapping from the child identifier of that child also maps to an indicator as to whether the child is an attribute or an element of its parent.

### Claim 10 (depends on 7, 8, 9)

The computer-readable medium of claims 7-9 wherein the mapping from the child identifier of that child also maps to a child value identifier in the table.

### Claim 11

A method for generating a data structure for mapping between semi-structured data and structured data, the method comprising:
identifying parent and child relationships in the semi-structured data; for each identified parent and child relationship,
identifying a table in the structured data that corresponds to the identified parent and child relationship; and
creating a mapping between the identified parent and child relationship and the identified table.

### Claim 12 (depends on 11)

The method of claim 11 wherein the mapping maps a parent identifier and child identifier of the parent and child relationship to a table identifier of the identified table.

### Claim 13 (depends on 12)

The method of claim 12 wherein each mapping further includes a parent key identifier and a child key identifier of the table that correspond to the parent identifier and child identifier of the mapping.

### Claim 14 (depends on 13)

The method of claim 13 wherein each mapping further includes an indicator of whether a child of the parent and child relationship is an attribute or an element.

### Claim 15 (depends on 12, 13, 14)

The method of claims 12-14 wherein the method supports recursive definition of elements of the semi-structured data.

### Claim 16 (depends on 12, 13, 14, 15)

The method of claims 12-15 wherein the semi-structured data is in XML format.

### Claim 17 (depends on 12, 13, 14, 15, 16)

The method of claims 12-16 wherein the structured data is in a relational format.

### Claim 18 (depends on 12, 13, 14, 15, 16, 17)

The method of claims 12-17 including for each child of a parent and child relationship that is also not a parent, creating a mapping from the child identifier of that child to a table identifier of a table in the structured data.

### Claim 19 (depends on 18)

The method of claim 18 wherein the mapping from the child identifier of that child also maps to a child key identifier in the table.

### Claim 20 (depends on 18, 19)

The method of claims 18-19 wherein the mapping from the child identifier of that child also maps to an indicator as to whether the child is an attribute or an element of its parent.

### Claim 21 (depends on 18, 19, 20)

The method of claims 18-20 wherein the mapping from the child identifier of that child also maps to a child value identifier in the table.

### Claim 22

A method comprising:
generating a structured organization to store a collection of semi-structured data; and
collaterally generating a description of how the semi-structured data is stored under the structured organization.

### Claim 23 (depends on 22)

The method of claim 22, wherein said collateral generation of a description comprises generating descriptive entries for a description table, with each descriptive entry identifying a first and a second storage column of a storage table for a parent and a child node of a parent and child node pair of the semi-structured data.

### Claim 24 (depends on 23)

The method of claim 23, wherein said collateral generation of a description further comprises generating for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 25 (depends on 22)

The method of claim 22, wherein said generation of a structured organization comprises creating relational storage tables with rows and columns in a normalized manner.

### Claim 26

An apparatus comprising:
a storage medium having stored therein a plurality of programming instructions designed to generate a structured organization to store a collection of semi-structured data, when executed, and to collaterally generate a description of how the semi-structured data are stored under the structured organization; and a processor coupled to the storage medium to execute the programming instructions.

### Claim 27 (depends on 26)

The apparatus of claim 26, wherein the programming instructions are designed to generate the description by generating a description table having a plurality of descriptive entries, with each descriptive entry identifying a first and a second storage column of a storage table of the structured organization for a parent and a child node of a parent and child node pair of the semi-structured data.

### Claim 28 (depends on 27)

The apparatus of claim 27, wherein said programming instructions are further designed to generate for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 29 (depends on 26)

The apparatus of claim 26, wherein said programming instructions are designed to generate a structured organization by creating relational storage tables with rows and columns in a normalized manner.

### Claim 30 (depends on 26)

The apparatus of claim 26, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access databases.

### Claim 31

An article of manufacture comprising:
a recordable medium having recorded thereon a plurality of programming instructions for use to program a system having a processor for executing programming instructions, to enable the system to generate a structured organization to store a collection of semi-structured data, and to collaterally generate a description of how the semi-structured data are stored under the structured organization.

### Claim 32 (depends on 31)

The article of claim 31, wherein said programming instructions enable the system to collaterally generating a description by generating a description table having a plurality of descriptive entries, with each descriptive entry identifying a first and a second storage column of a storage table for a parent and a child node of a parent and child node pair of the semi-structured data.

### Claim 33 (depends on 32)

The article of claim 32, wherein said programming instructions further enable the system to generate for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 34 (depends on 31)

The article of claim 31, wherein said programming instructions enable the system to generate a structured organization by creating relational storage tables with rows and columns in a normalized manner.

### Claim 35 (depends on 31)

The article of claim 31, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access databases.

### Claim 36

A method comprising:
generating a semi-structured data organization for a collection of structured data; and
collaterally generating a description of correspondence between the generated semi-structured data organization and the collection of structured data.

### Claim 37 (depends on 36)

The method of claim 36, wherein said collateral generation of a description comprises generating descriptive entries for a description table, with each descriptive entry identifying a first and a second storage column of a storage table of the structured data for a parent and a child node of a parent and child node pair of the generated semi-structured data organization.

### Claim 38 (depends on 37)

The method of claim 37, wherein said collateral generation of a description further comprises generating for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 39 (depends on 37)

The method of claim 37, wherein said generation of a semi-structured data organization comprises creating an extensible mark-up language (XML) data structure for a collection of relational tables.

### Claim 40

An apparatus comprising: a storage medium having stored therein a plurality of programming instructions designed to generate a semi-structured data organization for a collection of structured data, when executed, and to collaterally generate a description of correspondence between the semi-structured data organization and the structured data; and a processor coupled to the storage medium to execute the programming instructions.

### Claim 41 (depends on 40)

The apparatus of claim 40, wherein the programming instructions are designed to generate the description by generating a description table having a plurality of descriptive entries, with each descriptive entry identifying a first and a second storage column of a storage table of the structured data for a parent and a child node of a parent and child node pair of the generated semi-structured data organization.

### Claim 42 (depends on 41)

The apparatus of claim 41, wherein said programming instructions are further designed to generate for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 43 (depends on 40)

The apparatus of claim 40, wherein said programming instructions are designed to create an extensible mark-up language (XML) data structure for a collection of relational tables.

### Claim 44 (depends on 40)

The apparatus of claim 40, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access databases.

### Claim 45

An article of manufacture comprising:
a recordable medium having recorded thereon a plurality of programming instructions for use to program a system having a processor for executing programming instructions, to enable the system to generate a semi-structured data organization for a collection of structured data, and to collaterally generate a description of correspondence between the semi-structured data organization and the structured data.

### Claim 46 (depends on 45)

The article of claim 45, wherein said programming instructions enable the system to collaterally generating a description by generating a description table having a plurality of descriptive entries, with each descriptive entry identifying a first and a second storage column of a storage table of the structured data for a parent and a child node of a parent and child node pair of the generated semi-structured data organization.

### Claim 47 (depends on 46)

The article of claim 46, wherein said programming instructions further enable the system to generate for each of a selected one or ones of said descriptive entries a context qualifier for at least a selected one of the parent and the child node.

### Claim 48 (depends on 45)

The article of claim 45, wherein said programming instructions enable the system to create an extensible mark-up language (XML) data structure for a collection of relational tables.

### Claim 49 (depends on 45)

The article of claim 45, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access databases.

### Claim 50

A method comprising:
pre-processing semi-structured queries in an information page employing semi-structured data to identify the data to be selectively retrieved from the semi-structured data, and the storage locations of the data in a collection of structured data comprising the semi-structured data, referencing a description of how the semi-structured data are stored in the collection of structured data;
generating equivalent structured queries to retrieve the data from the collection of structured data; and
replacing the semi-structured queries with the equivalent structured queries.

### Claim 51 (depends on 50)

The method of claim 50, wherein said pre-processing of semi-structured queries is also performed to identify join conditions for joining relational storage tables of said collection of structured data to retrieve the data.

### Claim 52 (depends on 50)

The method of claim 50, wherein said pre-processing of semi-structured queries comprises pre-processing matching templates of said semi-structured queries.

### Claim 53 (depends on 52)

The method of claim 52, wherein said pre-processing matching templates comprises pre-processing of data extraction commands within each of the matching templates.

### Claim 54 (depends on 50)

The method of claim 50, wherein said generation of equivalent structured queries comprises generating structured queries, and control structures controlling repeated execution of the generated structured queries.

### Claim 55

An apparatus comprising:
a storage medium having stored therein a plurality of programming instructions designed
to pre-process semi-structured queries in an information page employing semi-structured data to identify the data to be selectively retrieved from the semi-structured data, and the storage locations of the data in a collection of structured data comprising the semi-structured data, referencing a description of how the semi-structured data are stored in the collection of structured data,
to generate equivalent structured queries to retrieve the data from the collection of structured data, and
to replace the semi-structured queries with the equivalent structured queries; and
a processor coupled to the storage medium to execute the programming instructions.

### Claim 56 (depends on 55)

The apparatus of claim 55, wherein said programming instructions are also designed to pre-process the semi-structured queries to identify join conditions for joining relational storage tables of said collection of structured data to retrieve the data.

### Claim 57 (depends on 55)

The apparatus of claim 55, wherein said programming instructions are designed to pre-process matching templates of said semi-structured queries.

### Claim 58 (depends on 57)

The apparatus of claim 57, wherein said programming instructions are further designed to pre-process data extraction commands within each of the matching templates.

### Claim 59 (depends on 55)

The apparatus of claim 55, wherein said programming instructions are designed to generate structured queries, and control structures controlling repeated execution of the generated structured queries.

### Claim 60 (depends on 55)

The apparatus of claim 55, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access data bases.

### Claim 61

An article of manufacture comprising:
a recordable medium having recorded thereon a plurality of programming instructions for use to program a system having a processor for executing programming instructions, to enable the system
to pre-process semi-structured queries in an information page employing semi-structured data to identify the data to be selectively retrieved from the semi-structured data, and the storage locations of the data in a collection of structured data comprising the semi-structured data, referencing a description of how the semi-structured data are stored in the collection of structured data,
to generate equivalent structured queries to retrieve the data from the collection of structured data, and
to replace the semi-structured queries with the equivalent structured queries.

### Claim 62 (depends on 61)

The article of claim 61, wherein said programming instructions are also designed to enable the system to pre-process the semi-structured queries to identify join conditions for joining relational storage tables of said collection of structured data to retrieve the data.

### Claim 63 (depends on 61)

The article of claim 61, wherein said programming instructions are designed to enable the system to pre-process matching templates of said semi-structured queries.

### Claim 64 (depends on 63)

The article of claim 63, wherein said programming instructions are further designed to enable the system to pre-process data extraction commands within each of the matching templates.

### Claim 65 (depends on 61)

The article of claim 61, wherein said programming instructions are designed to enable the system to generate structured queries, and control structures controlling repeated execution of the generated structured queries.

### Claim 66 (depends on 61)

The article of claim 61, wherein said programming instructions are a subset of a larger collection of programming instructions implementing a selected one of a database manager and a development toolkit that facilitates development of applications that access data bases.

### Claim 67

A method comprising:
storing pre-processed information pages formed with a language that provides for semi-structured queries, and employing semi-structured data, where the semi-structured queries have been pre-replaced with equivalent structured queries to retrieve the data to be retrieved by the semi-structured queries from the semi-structured data, from a collection of structured data comprising the semi-structured data instead;
receiving a request for a selected one of the information pages;
dynamically completing the information page, executing the replacement structured queries; and
returning the dynamically completed information page.

### Claim 68 (depends on 67)

The method of claim 67, wherein the method further comprises
pre-processing the semi-structured queries of each information page employing semi-structured data to identify the data to be selectively retrieved from the semi-structured data, and the storage locations of the data in the collection of structured data comprising the semi-structured data, referencing a description of how the semi-structured data are stored in the collection of structured data
generating equivalent structured queries to retrieve the data from the collection of structured data; and
replacing the semi-structured queries with the equivalent structured queries.

### Claim 69 (depends on 68)

The method of claim 68, wherein said pre-processing of semi-structured queries is also performed to identify join conditions for joining relational storage tables of the collection of structured data to retrieve the data.

### Claim 70 (depends on 68)

The method of claim 68, wherein said generation of equivalent structured queries comprises generating structured queries, and control structures controlling repeated execution of the generated structured queries.

### Claim 71

An apparatus comprising:
a network interface coupling the apparatus to a data network;
a storage medium having stored therein pre-processed information pages formed with a language that provides for semi-structured queries, and employing semi-structured data, where the semi-structured queries have been pre-replaced with equivalent structured queries to retrieve the data to be retrieved by the semi-structured queries from the semi-structured data, from a collection of structured data comprising the semi-structured data instead; and
a processor coupled to the network interface and the storage medium to receive a request from a client for a selected one of the information pages from the data network, and in response, dynamically completing the information page, executing the replacement structured queries, and returning the dynamically completed information page to the client through the data network.

### Claim 72 (depends on 71)

The apparatus of claim 71, wherein the apparatus is a web server, the language is extensible script language (XSL), the information pages are XSL documents, and the semi-structured data are extensible mark-up language (XML) data.

### Claim 73 (depends on 72)

The apparatus of claim 72, wherein the structured data are relational data and the structured queries are formed using the structured query language (SQL).
