Method and apparatus for storing semi-structured data in a structured manner

• US 7,707,159 B2
• Filed: 07/25/2006
• Issued: 04/27/2010
• Est. Priority Date: 03/02/2000
• Status: Expired due to Term

• Current Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Original Assignee: Actuate Corporation (Open Text Corporation)
• Inventors: Kommissarchik, Konstantin L., Christianson, David B., Draper, Denise L.
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US11/493,786
• Publication Number:
  US 20060265410A1
• Time in Patent Office: 1,372 Days
• Field of Search: 707 2- 5, 707/101, 707/102, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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

1. A method implemented by an apparatus including a processor and a memory, 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 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;

replacing the semi-structured queries with the equivalent structured queries;

wherein generating equivalent structured queries to retrieve the data from the collection of structured data is performed using a data structure including the description of how the semi-structured data are stored in the collection of structured data;

wherein the description of how the semi-structured data are stored in the collection of structured data includes a mapping between the semi-structured data and the structured data that indicates hierarchical information of the semi-structured data.

2. The method of claim 1, 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.

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

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

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

6. The method as recited in claim 1, wherein the data structure includes:

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.

7. The method as recited in claim 1, further comprising:

receiving a request for the information page;

dynamically completing the information page;

executing the replacement structured queries; and

returning the dynamically completed information page.

8. The method as recited in claim 1, wherein the information page is one of a plurality of information pages that are formed with a language that provides for semi-structured queries.

9. The method as recited in claim 6, 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.

10. The method as recited in claim 9, wherein each mapping further includes an indicator of whether a child of the parent and child relationship is an attribute or an element.

11. The method as recited in claim 6, wherein the data structure supports recursive definition of elements of the semi-structured data.

12. The method as recited in claim 6, wherein the semi-structured data is in XML format.

13. The method as recited in claim 6, wherein the structured data is in a relational format.

14. The method as recited in claim 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.

15. The method as recited in claim 14, wherein the mapping from the child identifier of that child also maps to a child key identifier in the table.

16. The method as recited in claim 14, 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.

17. The method as recited in claim 14, wherein the mapping from the child identifier of that child also maps to a child value identifier in the table.

18. The method as recited in claim 1, wherein the data structure is generated by performing the following steps:

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.

19. The method as recited in claim 18, wherein the mapping maps a parent identifier and child identifier of the parent and child relationship to a table identifier of the identified table.

20. The method as recited in claim 19, 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.

21. The method as recited in claim 20, wherein each mapping further includes an indicator of whether a child of the parent and child relationship is an attribute or an element.

22. The method as recited in claim 19, wherein the semi-structured data is in XML format, and wherein the structured data is in a relational format.

23. The method as recited in claim 19, wherein the semi-structured data is in XML format.

24. The method as recited in claim 19, wherein the structured data is in a relational format.

25. The method as recited in claim 19, wherein the data structure is generated by further performing the following steps:

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.

26. The method as recited in claim 25 wherein the mapping from the child identifier of that child also maps to a child key identifier in the table.

27. The method as recited in claim 25 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.

28. The method as recited in claim 25, wherein the mapping from the child identifier of that child also maps to a child value identifier in the table.

29. 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 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;

wherein the instructions designed to generate equivalent structured queries to retrieve the data from the collection of structured data access a data structure including the description of how the semi-structured data are stored in the collection of structured data;

wherein the description of how the semi-structured data are stored in the collection of structured data includes a mapping between the semi-structured data and the structured data that indicates hierarchical information of the semi-structured data; and

a processor coupled to the storage medium to execute the programming instructions.

30. The apparatus of claim 29, 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.

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

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

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

34. The apparatus of claim 29, 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.

35. 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 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 using a data structure including the description of how the semi-structured data are stored in the collection of structured data;

wherein the description of how the semi-structured data are stored in the collection of structured data includes a mapping between the semi-structured data and the structured data that indicates hierarchical information of the semi-structured data, and

to replace the semi-structured queries with the equivalent structured queries.

36. The article of claim 35, 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.

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

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

39. The article of claim 35, 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.

40. The article of claim 35, 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.

41. An apparatus comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

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;

formed with a language that provides for semi-structured queries;

wherein generating equivalent structured queries to retrieve the data from the collection of structured data is performed using a data structure including the description of how the semi-structured data are stored in the collection of structured data;

wherein the description of how the semi-structured data are stored in the collection of structured data includes a mapping between the semi-structured data and the structured data that indicates hierarchical information of the semi-structured data.

42. The apparatus of claim 41, 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.

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