Tagging XML query results over relational DBMSs

• US 6,934,712 B2
• Filed: 03/19/2001
• Issued: 08/23/2005
• Est. Priority Date: 03/21/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kiernan, Gerald George, Shanmugasundaram, Jayavel, Shekita, Eugene Jon
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/810,167
• Publication Number:
  US 20010037345A1
• Time in Patent Office: 1,618 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/100, 707/102, 715/513, 715/514
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/8358 Query translation
• CPC Class Codes: G06F 16/838 Presentation of query results
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for publishing relational data as XML by translating XML queries into queries against a relational database. Conversion of the relational database into an XML database is not required. Each relational table is mapped to a virtual XML document, and XML queries are issued over these virtual documents. An XML query is parsed and transformed into a language-neutral intermediate representation, which is a sequence of operations describing how the output document is derived from the underlying relational tables. The intermediate representation is then translated into an SQL query over the underlying relational tables. The intermediate representation is also used to generate a tagger graph, which the tagger runtime ‘walks’ to generate the tagged, structured XML output. Each of the nodes of the tagger graph are operators which perform processing on the results of the SQL query. The SQL query is executed, and the SQL query results are then provided to the tagger. The tagger runtime applies the operators of each node to the inputs at that node to produce the structured XML document as a query result, guided by the structure of the tagger graph.

Claims

1. A computer implemented method of tagging results of an XML query over a relational database, said method comprising:

generating a tagger tree graph from said XML query, each node of said tagger tree graph comprising a tagger operator, each tagger operator having a tagger parse tree associated therewith;

calling each tagger operator in accordance with a structure of said tagger tree graph, and evaluating said tagger parse trees associated with each called tagger operator to tag results of said XML query over said relational database.

2. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein said tagger node graph has a top-most tagger operator and a plurality of lower-most tagger operators, said calling and evaluating steps further comprising:

a. starting with said top-most tagger operator, each tagger operator implementing a method to request results from inputs to said tagger operator, said method causing lower level tagger operators connected to said inputs to be called;

b. starting with said lower-most tagger operators, each called tagger operator returning intermediate tagged results to a higher-level connected tagger operator upon evaluating said associated parse tree;

performing steps a and b until an end of said results of said XML query is reached, and said top-most tagger operator producing tagged output XML of said results of said XML query.

3. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein said tagger operators comprise any of a tagger input operator, a tagger scalar operator or a tagger aggregate operator.

4. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein said tagger tree graph includes a tagger operator for each level in a result XML tree of said XML query.

5. A computer implemented method of tagging results of an XML query over a relational database, as per claim 4, wherein said tagger input operators execute in a sorted outer union mode.

6. A computer implemented method of tagging results of an XML query over a relational database, as per claim 5, wherein said tagger input operators comprise a shared tagger row stream.

7. A computer implemented method of tagging results of an XML query over a relational database, as per claim 4, wherein said tagger input operators execute in a node strip mode.

8. A computer implemented method of tagging results of an XML query over a relational database, as per claim 7, wherein each of said tagger operators comprises a tagger row stream.

9. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein each tagger operator performs any of a cr8_elem, a cr8_attr, a cr8_attr_list, a cr8_fragments or a cr8_fragment_list function.

10. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein each tagger operator implements a next method to produce a result row.

11. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, said method further comprising:

parsing said XML query;

transforming said parsed XML query into a language-neutral intermediate representation;

rewriting said language-neutral intermediate representation into an equivalent form easily translated into an SQL query;

translating said equivalent form into one or more SQL queries over said relational database, and

executing said one or more SQL queries to produce said results of said XML query over said relational database.

12. A computer implemented method of tagging results of an XML query over a relational database, as per claim 11, wherein said tagger tree graph is generated from said equivalent form.

13. A computer implemented method of tagging results of an XML query over a relational database, as per claim 11, wherein said tagger tree graph includes a tagger operator for each node in a result XML tree of said XML query.

14. A computer implemented method of tagging results of an XML query over a relational database, as per claim 13, wherein said tagger input operators execute in a sorted outer union mode and said translating step produces a single SQL query to produce a single sorted outer union relational database result.

15. A computer implemented method of tagging results of an XML query over a relational database, as per claim 14, wherein said tagger input operators comprise a shared tagger row stream.

16. A computer implemented method of tagging results of an XML query over a relational database, as per claim 13, wherein said tagger input operators execute in a node strip mode and said translating step produces a set of SQL queries to produce a set of node strip relational database results.

17. A computer implemented method of tagging results of an XML query over a relational database, as per claim 16, wherein each of said tagger operators comprises a tagger row stream.

18. A computer implemented method of tagging results of an XML query over a relational database, as per claim 11, wherein said tagger operators comprise any of a tagger input operator, a tagger scalar operator or a tagger aggregate operator.

19. A computer implemented method of tagging results of an XML query over a relational database, as per claim 11, wherein a number of relational database tables of said relational database are mapped to a number of virtual XML documents and said XML queries are issued over said virtual XML documents.

20. A computer implemented method of tagging results of an XML query over a relational database, as per claim 1, wherein said method operates over a distributed computing network.

21. A computer implemented method of tagging results of an XML query over a relational database, as per claim 20, wherein said method operates over the Internet.

22. A computer-based system for tagging results of an XML query over a relational database, said system comprising:

a tagger runtime component;

means for generating a tagger tree graph from said XML query, each node of said tagger tree graph comprising a tagger operator;

means for generating a tagger parse tree associated with each tagger operator, and wherein

said tagger runtime component calls each tagger operator in accordance with a structure of said tagger tree graph and evaluates said tagger parse trees associated with each called tagger operator to tag results of said XML query over said relational database.

23. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein said tagger node graph has a top-most tagger operator and a plurality of lower-most tagger operators, and to perform said calling and evaluating, said tagger runtime component further:

a. starting with said top-most tagger operator, causing each tagger operator to implement a method to request results from inputs to said tagger operator, said method causing lower-level tagger operators connected to said inputs to be called;

b. starting with said lower-most tagger operators, causing each called tagger operator to return intermediate tagged results to a higher-level connected tagger operator upon evaluating said associated parse tree;

performing steps a and b until an end of said results of said XML query is reached, and upon reaching an end of said results of said XML query, causing said top-most tagger operator to produce a tagged output XML document of said results of said XML query.

24. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein said tagger operators comprise any of a tagger input operator, a tagger scalar operator or a tagger aggregate operator.

25. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein said tagger graph includes a tagger input operator for each node in a result XML tree of said XML query.

26. A computer-based system for tagging results of an XML query over a relational database, as per claim 25, wherein said tagger input operators execute in a sorted outer union mode.

27. A computer-based system for tagging results of an XML query over a relational database, as per claim 26, wherein said tagger input operators comprise a shared tagger row stream.

28. A computer-based system for tagging results of an XML query over a relational database, as per claim 25, wherein said tagger input operators execute in a node strip mode.

29. A computer-based system for tagging results of an XML query over a relational database, as per claim 28, wherein each of said tagger operators comprises a tagger row stream.

30. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein each tagger operator performs any of a cr8_elem, a cr8_attr, a cr8_attr_list, a cr8_fragments or a cr8_fragment_list function.

31. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein each tagger operator implements a next method to produce a result row.

32. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, said system further comprising:

a parser, said parser parsing said XML query and transforming said parsed XML query into a language-neutral intermediate representation;

a rewrite engine, said rewrite engine rewriting said language-neutral intermediate representation into an equivalent form easily translated into an SQL query;

a translator, said translator translating said equivalent form into one or more SQL queries over said relational database, and

an RDBMS, said RDBMS executing said one or more SQL queries to produce said results of said XML query over said relational database.

33. A computer-based system for tagging results of an XML query over a relational database, as per claim 32, wherein said tagger graph is generated from said equivalent form.

34. A computer-based system for tagging results of an XML query over a relational database, as per claim 32, wherein said tagger graph includes a tagger input operator for each node in a result XML tree of said XML query.

35. A computer-based system for tagging results of an XML query over a relational database, as per claim 34, wherein said tagger input operators execute in a sorted outer union mode and said translator produces a single SQL query to produce a single sorted outer union relational database result.

36. A computer-based system for tagging results of an XML query over a relational database, as per claim 35, wherein said tagger input operators comprise a shared tagger row stream.

37. A computer-based system for tagging results of an XML query over a relational database, as per claim 34, wherein said tagger input operators execute in a node strip mode and said translator produces a set of SQL queries to produce a set of node strip relational database results.

38. A computer-based system for tagging results of an XML query over a relational database, as per claim 37, wherein each of said tagger operators comprises a tagger row stream.

39. A computer-based system for tagging results of an XML query over a relational database, as per claim 32, wherein said tagger operators comprise any of a tagger input operator, a tagger scalar operator or a tagger aggregate operator.

40. A computer-based system for tagging results of an XML query over a relational database, as per claim 32, said system further comprising:

a schema mapper, said schema mapper mapping a number of relational database tables of said relational database to a number of virtual XML documents, and

an XML-QL engine, said XML-QL engine issuing said XML queries over said virtual XML documents.

41. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein said system operates over a distributed computing network.

42. A computer-based system for tagging results of an XML query over a relational database, as per claim 41, wherein said system operates over the Internet.

43. A computer-based system for tagging results of an XML query over a relational database, as per claim 22, wherein said tagger runtime operates outside an RDBMS.

44. A computer program product comprising a machine-readable medium including computer readable program code therein for tagging results of an XML query over a relational database comprising:

computer readable program code generating a tagger tree graph from said XML query, each node of said tagger tree graph comprising a tagger operator, each tagger operator having a tagger parse tree associated therewith;

computer readable program code calling each tagger operator in accordance with a structure of said tagger tree graph, and

computer readable program code evaluating said tagger parse trees associated with each called tagger operator to tag results of said XML query over said relational database.

45. A computer program product comprising a machine-readable medium including computer readable program code therein for tagging results of an XML query over a relational database as per claim 44, wherein said generated tagger node graph has a topmost tagger operator and a plurality of lower-most tagger operators, said calling and evaluating computer readable program code further comprising:

computer readable program code for performing;

a. starting with said top-most tagger operator, each tagger operator requesting results from inputs to said tagger operator, said request causing lower-level tagger operators connected to said inputs to be called;

b. starting with said lower-most tagger operators, each called tagger operator returning intermediate tagged results to a higher-level connected tagger operator upon evaluating said associated parse tree;

performing steps a and b until an end of said results of said XML query is reached, and said top-most tagger operator producing tagged output XML of said results of said XML query.