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

• US 20050050011A1
• Filed: 08/25/2003
• Published: 03/03/2005
• 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
• Granted Patent: US 7,792,866 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 in at least one node of the plurality of nodes, wherein the at least one child pointer points to a corresponding child node of the plurality of nodes;

b) storing a hint in the at least one child pointer; 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 related to the corresponding child node.

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

4. 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 node tree associated with the structured document;

c3) checking a 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).

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

(c3i) comparing the hint to the query.

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

(c4i) navigating to the corresponding child node if the 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.

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

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

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

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

(c6) checking the 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 node tree if the another child pointer does not exist, and repeating steps (c3) through (c7), wherein the next node becomes the current node.

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

10. The method of claim 4, wherein the query is an Xpath or an Xquery expression.

11. A computer readable medium containing programming instructions 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 instructions for:

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

b) storing a hint in the at least one child pointer; and

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

12. The computer readable medium of claim 11, wherein the hint is related to the corresponding child node.

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

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

c1) receiving a query;

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

c3) checking a 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).

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

(c3i) comparing the hint to the query.

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

(c4i) navigating to the corresponding child node if the 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.

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

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

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

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

(c6) checking the 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 node tree if the another child pointer does not exist, and repeating steps (c3) through (c7), wherein the next node becomes the current node.

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

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

21. 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, 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 in at least one node of the plurality of nodes, wherein the at least one child pointer points to a corresponding child node of the plurality of nodes, and for storing a hint in the at least one child pointers;

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

22. The system of claim 21, wherein the hint is related to the corresponding child node.

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

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

25. The system of claim 24, wherein the database management system is further configured to compare the hint to the query.

26. The system of claim 25, wherein the database management system is further configured to navigate to the corresponding child node if the 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.

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

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

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

30. The system of claim 24, wherein the query is an Xpath or an Xquery expression.