Method and system for querying structured documents stored in their native format in a database

• US 7,792,866 B2
• Filed: 08/25/2003
• Issued: 09/07/2010
• Est. Priority Date: 08/25/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Van Der Linden, Robbert C., Vickery, Brain S., Mayr, Stefan Tobias
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US10/648,752
• Publication Number:
  US 20050050011A1
• Time in Patent Office: 2,570 Days
• Field of Search: 707/3, 707/102, 707/100, 707/101, 707/203, 395/600, 715/513, 715/514
• US Class Current: 707/797
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A method and system for querying a structured document stored in its native format in a database, where the structured document includes a plurality of nodes that form a hierarchical node tree, is disclosed. The method includes providing at least one child pointer in each of the plurality of nodes, where the at least one child pointer points to a corresponding child node of the plurality of nodes, and storing a hint in each of the at least one child pointers. The hint is then utilized to navigate the hierarchical node tree during query evaluation.

Claims

1. A method for querying a structured document stored in its native format in a database, wherein the structured document comprises a plurality of nodes that form a hierarchical node tree, the method comprising the steps of:

(a) providing at least one child pointer within at least one of the plurality of nodes in the hierarchical node tree, wherein the at least one child pointer points to a corresponding child node in the hierarchical node tree;

(b) storing a hint within the at least one child pointer, the hint being related to the corresponding child node, wherein the at least one child pointer further comprises a node slot number of the corresponding child node; and

(c) utilizing the hint to determine whether to navigate to the corresponding child node during query evaluation.

2. The method of claim 1, wherein the hint is a portion of the corresponding child node'"'"'s name.

3. The method of claim 1, wherein utilizing step (c) further comprises:

(c1) receiving a query;

(c2) navigating to a current node of the plurality of nodes in the hierarchical node tree associated with the structured document;

(c3) checking a first hint stored in a first child pointer in the current node; and

(c4) navigating to the corresponding child node based on the checking in step (c3).

4. The method of claim 3, wherein checking step (c3) further comprises:

(c3i) comparing the first hint to the query.

5. The method of claim 4, wherein navigating step (c4) further comprises:

(c4i) navigating to the corresponding child node if the first hint matches the query; and

(c4ii) comparing the child node'"'"'s name and namespace to the query to determine whether the child node satisfies the query.

6. The method of claim 4, wherein navigating step (c4) further comprises:

(c4i) skipping over the corresponding child node if the first hint does not match the query.

7. The method of claim 3, wherein the utilizing step (c) further comprises:

(c5) determining whether another child pointer exists in the current node;

(c6) checking another hint stored in the another child pointer if the another child pointer exists, and navigating to the corresponding child node based on the checking;

(c7) repeating steps (c5) and (c6); and

(c8) navigating to a next node of the plurality of nodes in the hierarchical node tree if the another child pointer does not exist, and repeating steps (c3) through (c7), wherein the next node becomes the current node.

8. The method of claim 1, wherein the structured document is written in Extensible Markup Language.

9. The method of claim 3, wherein the query is an Xpath or an Xquery expression.

28. The method of claim 1, wherein each of the plurality of nodes in the hierarchical node tree specifies a type of node, one or more nodes in the hierarchical node tree being of a text-type and one or more other nodes in the hierarchical tree being of a non-text type.

31. The method of claim 1, wherein the at least one node in the hierarchic node tree further includes at least one other child pointer, the at least one other child pointer pointing to itself or to an in-lined character array.

10. A computer readable medium containing a computer program for querying a structured document stored in its native format in a database, wherein the structured document comprises a plurality of nodes that form a hierarchical node tree, the computer program comprising instructions for:

(a) providing at least one child pointer within at least one of the plurality of nodes, in the hierarchical node tree, wherein the at least one child pointer points to a corresponding child node in the hierarchical node tree;

(b) storing a hint within the at least one child pointer, the hint being related to the corresponding child node, wherein the at least one child pointer further comprises a node slot number of the corresponding child node; and

(c) utilizing the hint to determine whether to navigate to the corresponding child node during query evaluation.

11. The computer readable medium of claim 10, wherein the hint is a portion of the corresponding child node'"'"'s name.

12. The computer readable medium of claim 10, wherein utilizing instruction (c) further comprises:

(c1) receiving a query;

(c2) navigating to a current node of the plurality of nodes in the hierarchical node tree associated with the structured document;

(c3) checking a first hint stored in a first child pointer in the current node; and

(c4) navigating to the corresponding child node based on the checking in step (c3).

13. The computer readable medium of claim 12, wherein checking instruction (c3) further comprises:

(c3i) comparing the first hint to the query.

14. The computer readable medium of claim 13, wherein navigating instruction (c4) further comprises:

(c4i) navigating to the corresponding child node if the first hint matches the query; and

(c4ii) comparing the child node'"'"'s name and namespace to the query to determine whether the child node satisfies the query.

15. The computer readable medium of claim 13, wherein navigating instruction (c4) further comprises:

(c4i) skipping over the corresponding child node if the first hint does not match the query.

16. The computer readable medium of claim 12, wherein the utilizing instruction (c) further comprises:

(c5) determining whether another child pointer exists in the current node;

(c6) checking another hint stored in the another child pointer if the another child pointer exists, and navigating to the corresponding child node based on the checking;

(c7) repeating steps (c5) and (c6); and

(c8) navigating to a next node of the plurality of nodes in the hierarchical node tree if the another child pointer does not exist, and repeating steps (c3) through (c7), wherein the next node becomes the current node.

17. The computer readable medium of claim 10, wherein the structured document is written in Extensible Markup Language.

18. The computer readable medium of claim 12, wherein the query is an Xpath or an Xquery expression.

29. The computer readable medium of claim 10, wherein each of the plurality of nodes in the hierarchical node tree specifies a type of node, one or more nodes in the hierarchical node tree being of a text-type and one or more other nodes in the hierarchical tree being of a non-text type.

32. The computer readable medium of claim 10, wherein the at least one node in the hierarchical node tree further includes at least one other child pointer, the at least one other child pointer pointing to itself or to an in-lined character array.

19. A system for querying a structured document stored in its native format in a database, wherein the structured document comprises a plurality of nodes that form a hierarchical node tree, the system comprising:

a computer system coupled to at least one data storage device;

a database management system in the computer system; and

a storage mechanism in the database management system for providing at least one child pointer within at least one of the plurality of nodes in the hierarchical node tree, wherein the at least one child pointer points to a corresponding child node in the hierarchical node tree, and storing a hint within the at least one child pointer, the hint being related to the corresponding child node, wherein the at least one child pointer further comprises a node slot number of the corresponding child node;

wherein the a database management system utilizes the hint to determine whether to navigate to the corresponding child node during query evaluation.

20. The system of claim 19, wherein the hint is a portion of the corresponding child node'"'"'s name.

21. The system of claim 19, wherein the database management system is configured to receive a query, to navigate to a current node of the plurality of nodes in the hierarchical node tree associated with the structured document, to check a first hint stored in a first child pointer in the current node, and to navigate to the corresponding child node based on the checking.

22. The system of claim 21, wherein the database management system is further configured to compare the first hint to the query.

23. The system of claim 22, wherein the database management system is further configured to navigate to the corresponding child node if the first hint matches the query, and to compare the child node'"'"'s name and namespace to the query to determine whether the child node satisfies the query.

24. The system of claim 22, wherein the database management system is further configured to skip over the corresponding child node if the fist hint does not match the query.

25. The system of claim 21, wherein the database management system is further configured to determine whether another child pointer exists in the current node, to check another hint stored in the another child pointer if the another child pointer exists, to navigate to the corresponding child node based on the checking, and to navigate to a next node of the plurality of nodes in the hierarchical node tree if the another child pointer does not exist.

26. The system of claim 19, wherein the structured document is written in Extensible Markup Language.

27. The system of claim 21, wherein the query is an Xpath or an Xquery expression.

30. The system of claim 19, wherein each of the plurality of nodes in the hierarchical node tree specifies a type of node, one or more nodes in the hierarchical node tree being of a ten-type and one or more other nodes in the hierarchical tree being of a non-text type.

33. The system of claim 19, wherein the at least one node in the hierarchical node tree further includes at least one other child pointer, the at least one other child pointer pointing to itself or to an in-lined character array.