Method for converting relational data into XML

• US 6,785,673 B1
• Filed: 12/28/2001
• Issued: 08/31/2004
• Est. Priority Date: 02/09/2000
• Status: Expired due to Term

• Current Assignee: Alto Dynamics, LLC (IP Investments Group LLC)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Tan, Wang-Chiew, Suciu, Dan, Fernandez, Maria F., Morishima, Atsuyuki
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/029,211
• Time in Patent Office: 977 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/101, 707/102, 707/103, 707/200, 707/201, 707/500, 707/513, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• 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: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method for converting relational data to XML (eXtensible Markup Language) is provided. The method can use a greedy algorithm to efficiently construct materialized XML views of relational databases. A greedy algorithm designed for XML view definition queries is provided for decomposing a large query into smaller queries and determining which query will run faster without actually running the query.

Claims

1. A method for converting relational data from a relational database into extensible markup language (XML) comprising steps of:

storing a view query that defines a XML view of the relational database;

receiving a user query to access XML data in the XML view of the relational database;

forming an executable query by determining a composition of the view query and the user query;

applying a greedy algorithm to the executable query to form a data extraction portion and an XML construction portion;

transmitting the data extraction portion to the relational database;

receiving at least one tuple stream from the relational database according to the data extraction portion; and

merging the at least one tuple stream and the SML construction portion to generate an XML document, wherein the XML view is capable of defining a document of arbitrary nesting depth.

2. The method according to claim 1, wherein the user query is in XML-QL.

3. The method according to claim 2, wherein the view query is a RXL query.

4. The method according to claim 3, wherein the executable query is another RXL query.

5. The method device according to claim 1, wherein said step of receiving the user query includes receiving the user query from an application over a distributed network.

6. The method according to claim 1, wherein the data extraction portion includes at least one SQL query.

7. The method according to claim 6, wherein the XML construction portion is an XML template.

8. The method according to claim 6, wherein said step of receiving the at least one tuple stream includes receiving one tuple stream for each SQL-query included in the data extraction portion.

9. The method according to claim 1, wherein the step of applying a greedy algorithm to the executable query to form the data extraction portion and the XML construction portion includes the steps of:

converting the executable query into a view tree having plural nodes, each of the nodes having a query;

comparing queries of two adjacent nodes with a combination of the queries of the two adjacent nodes;

selecting either the queries of the two adjacent nodes or the combination of the queries of the two adjacent nodes based on cost; and

repeating said comparing and said selecting of queries until no combination of queries of two adjacent nodes has a cost lower than a cost of the corresponding separate queries.

10. The method according to claim 1, wherein the step of merging the at least one tuple stream and the XML construction portion to generate an XML document includes applying an integration and tagging algorithm.

11. The method according to claim 10, wherein the step of applying an integration and tagging algorithm includes the steps of:

receiving the at least one tuple stream, the at least one tuple stream having plural tuples with a corresponding node index for each tuple;

comparing a node index of a first tuple with a node index of a second tuple; and

emitting an XML tag based on said comparing.

12. A computer readable medium including a set of executable instructions stored thereon for converting relational data stored in a relational database into XML data, the set of instructions including:

forming an executable query from a view query and a user query that defines an XML view of the relational database and a user query;

applying a greedy algorithm to the executable query to forma a data extraction portion and an XML construction portion; and

merging the at least one tuple stream and the SML construction portion to generate an XML document, wherein the XML view is capable of defining a document of arbitrary nesting depth.

13. The computer readable medium according to claim 12, wherein the view query is a RXL query.

14. The computer readable medium according to claim 13, wherein the executable query is another RXL query.

15. The computer readable medium according to claim 12, wherein the data extraction portion includes at least one SQL query.

16. The computer readable medium according to claim 15, wherein said step of receiving the at least one tuple stream includes retrieving one tuple stream for each SQL-query included in the data extraction portion.

17. The computer readable medium according to claim 12, wherein the step of applying a greedy algorithm to the executable query to form a data extraction portion and an XML construction portion includes the steps of:

converting the executable query into a view tree having plural nodes, each of the nodes having a query;

comparing queries of two adjacent nodes with a combination of the queries of the two adjacent nodes; and

selecting either the queries of the two adjacent nodes or the combination of the queries of the two adjacent nodes based on cost.

18. The computer readable medium according to claim 12, wherein the step of merging the at least one tuple stream and the XML construction portion to generate an XML document includes applying an integration and tagging algorithm.

19. The computer readable medium according to claim 18, wherein the step of applying an integration and tagging algorithm includes the steps of:

receiving the at least one tuple stream, the at least one tuple stream having plural tuples with a corresponding node index for each tuple;

comparing a node index of a first tuple with a node index of a second tuple; and

emitting an XML tag based on said comparing.

20. A computer system for converting relational data in a relational database into XML data, and said system comprising:

a query composer module configured to form an executable query from a view query and a user query that defines an XML view of the relational data and a user query;

a translator module coupled to the query composer module configured to receive the executable query, partition the executable query through the use of a greedy algorithm, and transmit the data extraction portion to a relational database;

an XML generator module configured to receive the XML-construction portion from said translator module, receive at least one tuple stream from the relational database based on data extraction portion, and merge the at least one tuple stream and the XML-construction portion generate an XML document, wherein the XML view is capable of defining a document of arbitrary nesting depth.

21. The computer system according to claim 20, wherein said translator module receives a description of a schema of the relational data prior to partitioning the executable query.

22. The computer system according to claim 20, wherein the user query is in XML-QL, the view query is a RXL query and the executable query is another RXL query.

23. The computer system according to claim 20, wherein said query composer module is configured to receive the user query from an application over a distributed network.

24. The computer system according to claim 23, wherein said XML generator module is configured to transmit the XML document to the application over the distributed network.

25. The computer system according to claim 20, wherein the data extraction portion includes at least one SQL query.

26. The computer system according to claim 25, wherein said XML generator module receives one tuple stream for each SQL-query included in the data extraction portion.

27. The computer system according to claim 20, wherein the data extraction portion is executable by the relational database.

28. The computer system according to claim 20, wherein the query composer module includes

a pattern matcher module configured to match patterns of the user query and the view query to obtain a solutions relation, in which each tuple represents a match; and

a rewriter module configured to rewrite each tuple.

29. The computer system according to claim 20, wherein the XML generator module merges the at least one tuple stream and the XML construction portion to generate an XML document by applying an integration and tagging algorithm.