Relational database system providing XML query support

• US 6,799,184 B2
• Filed: 01/30/2002
• Issued: 09/28/2004
• Est. Priority Date: 06/21/2001
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Singh, Anupam, Sampath, Srikanth, Eachampadi, Raghavan T., Bhatt, Vadiraja
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/066,134
• Publication Number:
  US 20030101169A1
• Time in Patent Office: 972 Days
• Field of Search: 707/3, 707/102, 707/10, 707/1, 707/104.1, 705/14
• US Class Current: 707/718
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system providing methods enabling data in Extensible Markup Language (“XML”) format to be extracted, transformed and stored in a database, file system or main memory is described. The extraction and transformation process is generalized and can be used on various types of XML data, enabling XML data to be stored and queried using standard database query methodologies. The system includes parse-time functionality to transform XML documents into a structure having an interface that enables efficient access to the underlying data. The system also includes query execution-time functionality providing greater efficiency by bringing only the relevant portions of transformed XML data into memory in response to a query. The system parses and translates queries into a structure that can be executed without the need to write custom application-specific navigation code to search XML data. The system also enables original XML documents (or portions thereof) to be recomposed when required.

Claims

1. A method for transforming Extensible Markup Language (XML) documents for querying using a database query, the method comprising:

receiving an XML document;

transforming said XML document into a transformed object including information from said XML document together with an interface, said interface providing random access to information of interest within said transformed object; and

in response to a database query for information of interest, retrieving said information of interest from said transformed object.

2. The method of claim 1, wherein said step of transforming said XML object includes visiting each element of said XML object in order of occurrence.

3. The method of claim 1, wherein said step of transforming said XML object includes assigning a unique identifier to each element of said XML object.

4. The method of claim 3, wherein said unique identifier is an integer assigned to each element of said XML object in monotonically increasing order.

5. The method of claim 1, wherein said step of transforming said XML object includes using simple API for XML methodology to transform said XML object.

6. The method of claim 1, wherein said step of transforming said XML object includes creating indices for said XML object.

7. The method of claim 1, wherein said step of transforming said XML object includes creating an index of linkage information, said index containing the parent/child relationship of nodes.

8. The method of claim 7, wherein said index of linkage information enables said XML object to be recomposed from said transformed object.

9. The method of claim 1, wherein said step of transforming said XML object includes creating an index of hierarchical information about said XML object.

10. The method of claim 9, wherein said index of hierarchical information is in sorted order, said sorted order based upon the occurrence of information in said XML object.

11. The method of claim 1, wherein said step of transforming said XML object includes creating an index of data values contained in said XML object.

12. The method of claim 11, wherein said index of data values is in sorted order, said sorted order based upon said data values.

13. The method of claim 1, wherein said step of transforming said XML object includes maintaining a table containing a unique identifier for each element in said XML object and offsets to data values for each element having associated data values.

14. The method of claim 1, wherein said database query includes a Structured Query Language (SQL) query.

15. The method of claim 1, wherein said database query includes an XML Query Language (XQL) query.

16. The method of claim 1, wherein said interface includes meta data created during said step of transformation of said XML object.

17. The method of claim 1, wherein said transformed object is stored in a database.

18. The method of claim 1, wherein said transformed object is stored in a relational database.

19. The method of claim 1, further comprising:

providing an application programming interface (API) abstracting interaction with said transformed object to facilitate retrieval of information of interest from said transformed object.

20. A system for transforming Extensible Markup Language (XML) documents for storage in a database, the system comprising:

a parser event processing module for receiving a given XML document as input and verifying that said XML document is well formed;

a transformation module for transforming said given XML document into an object, said object including data from said given XML document and meta data structures to facilitate random access to said data; and

a database for storing said object.

21. The system of claim 20, wherein said database includes a file system.

22. The system of claim 20, wherein said database includes a relational database.

23. The system of claim 20, wherein said database includes system memory.

24. The system of claim 20, wherein said transformation module uses simple API for XML methodology to transform said given XML document.

25. The system of claim 20, wherein said transformation module creates indices for said given XML document.

26. The system of claim 20, wherein said transformation module creates an index containing parent/child relationships for each element in said given XML document.

27. The system of claim 20, wherein said transformation module creates an index containing a list of object identifiers for each unique path in said given XML document.

28. The system of claim 20, wherein said transformation module converts said given XML document into a logical tree in which each element of said given XML document is a node.

29. The system of claim 28, wherein each node is uniquely labeled.

30. The system of claim 28, wherein nodes are labeled in order of occurrence in said given XML document.

31. The system of claim 28, wherein each data value associated with an element is a node without any children nodes.

32. The system of claim 20, wherein said meta data structures include linkage information enabling recomposition of said given XML document.

33. The system of claim 20, wherein said meta data structures include hierarchical information regarding said given XML document.

34. The system of claim 20, wherein said meta data structures include data values from said given XML document in sorted order.

35. The system of claim 20, wherein said meta data structures include a table containing object identifiers and data offsets for each element of said given XML document.

36. The system of claim 20, further comprising:

a query module for executing queries against said database containing said object.

37. The system of claim 36, wherein said query module returns results as an XML object.

38. A system for querying documents in Extensible Markup Language (XML) format using a database query, said system comprising:

a query parsing module for receiving and parsing a given database query into a logical tree;

a query translation module for translation of said logical tree into a query plan, said query plan comprising a format appropriate for execution against transformed XML documents; and

a query execution module for executing said query plan and returning results.

39. The system of claim 38, further comprising:

a path processing module defining and implementing interaction between said query execution module and a data processing system containing transformed XML documents.

40. The system of claim 39, wherein said path processing module includes meta data structures to facilitate access to data in transformed XML documents.

41. The system of claim 39, wherein said path processing module regenerates an XML object in response to a query.

42. The system of claim 39, wherein said path processing module includes an application programming interface (API) abstracting interaction with said data processing system.

43. The system of claim 42, wherein said path processing module includes an implementation of said API including meta data structures to facilitate access to data in XML objects.

44. The system of claim 39, wherein said path processing module regenerates a portion of an XML object in response to a query.

45. The system of claim 38, wherein said query parsing module comprises an XQL parser.

46. The system of claim 38, wherein said query translation module receives a logical tree as input and generates a physical operator tree as output.

47. The system of claim 38, wherein said query execution module receives a physical operator tree as input and generates a result as output.

48. The system of claim 47, wherein said result is returned as an XML object.

49. The system of claim 38, further comprising:

a data structure containing transformed XML documents.

50. The system of claim 49, wherein said data structure includes meta data providing access to data in said transformed XML documents.

51. The system of claim 49, wherein said data structure includes parsed XML data.

52. The system of claim 38, further comprising:

a data store module for receiving XML documents as input and transforming said XML documents into transformed objects, said transformed objects including data from said XML documents and meta data enabling access to said data from said XML documents.

53. The system of claim 42, wherein said data store module includes an interface providing random access to data from said XML documents.

54. A method for transforming a document in tag delimited format to enable access to data in said object, the method comprising:

verifying that said document in tag delimited format is well formed;

transforming said document into a logical tree in which each element of said object is a node of said logical tree;

labeling each said node of said logical tree with a unique identifier; and

generating an interface facilitating random access to data in said logical tree.

55. The method of claim 54, wherein said step of labeling each said node includes assigning an integer to each said node in monotonically increasing order.

56. The method of claim 54, wherein said step of transforming said document includes visiting each element of said object in order of occurrence.

57. The method of claim 54, wherein said step of transforming said document includes using Simple API for XML methodology to transform said document.

58. The method of claim 54, wherein said step of generating an interface includes creating indices for said document.

59. The method of claim 54, wherein said step of generating an interface includes creating an index of linkage information, said index containing the parent/child relationship of nodes.

60. The method of claim 59, wherein said linkage information enables recomposition of said document in tag delimited format.

61. The method of claim 54, wherein said step of generating an interface includes creating an index of hierarchical information about said document.

62. The method of claim 61, wherein said index of hierarchical information is in sorted order, said sorted order based upon the occurrence of information in said document.

63. The method of claim 54, wherein said step of step of generating an interface includes creating an index of data values.

64. The method of claim 63, wherein said index of data values is in sorted order, said sorted order based upon said data values.

65. The method of claim 54, further comprising:

storing said logical tree and interface in a database.

66. A method for transforming documents in Extensible Markup Language (XML) format to enable access to data in said documents, the method comprising:

receiving documents in XML format;

transforming said documents into a transformed object, said transformed object including data from said documents and meta data facilitating access to said data; and

in response to a request, providing data from said documents by performing the substeps of;

parsing said request for data into a logical tree;

transforming said logical tree into a physical plan for execution; and

executing said physical plan against said transformed object and returning data resulting from execution of said physical plan.

67. The method of claim 66, wherein said step of transforming said documents into a transformed object includes providing an interface to data in said transformed object.

68. The method of claim 66, wherein said meta data includes at least one index to data in said transformed object.

69. The method of claim 66, wherein said step of transforming said logical tree into a physical plan includes determining an optimal access plan for obtaining data from said transformed object.

70. The method of claim 66, wherein said step of parsing said request for data includes using an XQL parser.

71. The method of claim 66, wherein said step of executing said physical plan includes using meta data structures of said transformed object.

72. The method of claim 66, wherein said step of executing said physical plan includes using an application programming interface of said transformed object.

73. The method of claim 66, wherein said step of returning data resulting from execution of said physical plan includes returning a well-formed XML document containing said data.