Multi-path simultaneous Xpath evaluation over data streams

• US 20060167869A1
• Filed: 01/27/2006
• Published: 07/27/2006
• Est. Priority Date: 01/27/2005
• Status: Abandoned Application

• Current Assignee: Inter
• Original Assignee: Inter
• Inventors: Jones, Kevin
• Application Number:
  US11/341,054
• Publication Number:
  US 20060167869A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

A method and apparatus are provided for performing simultaneous XPath evaluations over an XML data stream. The method includes the steps of providing an XML data stream consisting of a sequence of information items, providing a search query consisting of a graph of search patterns, searching a sequence of information items of the XML data stream along one or more directions using the search patterns and terminating the search of each direction of the one or more directions when no further results are possible.

Claims

1. A method of performing simultaneous XPath evaluations over an XML data stream comprising:

providing an XML data stream consisting of a sequence of information items;

providing a search query consisting of a graph of search patterns;

searching a sequence of information items of the XML data stream along one or more directions using the search patterns; and

terminating the search of each direction of the one or more directions when no further results are possible.

2. The method of performing simultaneous XPath evaluations as in claim 1 wherein the step of searching the sequence further comprises determining a context data item.

3. The method of performing simultaneous XPath evaluations as in claim 1 further comprising completing a first search direction of the graph of search patterns before starting a second search pattern of the graph of search patterns in the particular direction.

4. The method of performing simultaneous XPath evaluations as in claim 3 further comprising determining a direction of the one or more directions based upon a predicate attribute.

5. The method of performing simultaneous XPath evaluations as in claim 1 further comprising storing a location of a match from a first search pattern for use in conjunction with a second search pattern from another location of the graph of search patterns.

6. The method of performing simultaneous XPath evaluations as in claim 1 wherein the one or more directions further comprises a preceding search.

7. The method of performing simultaneous XPath evaluations as in claim 1 wherein the one or more directions further comprises a following search.

8. The method of performing simultaneous XPath evaluations as in claim 1 wherein the one or more directions further comprises an ancestor search.

9. The method of performing simultaneous XPath evaluations as in claim 1 wherein the query further comprises a search of XPath axis types.

10. The method of performing simultaneous XPath evaluations as in claim 1 further comprises linking a first attribute of the first search pattern of the graph search patterns to a second attribute of a second search pattern of the graph of search patterns.

11. The method of performing simultaneous XPath evaluations as in claim 1 wherein the search query further comprises a child and descendent search.

12. The method of performing simultaneous XPath evaluations as in claim 11 further comprising forming a child search pattern followed by a descendent search pattern within the graph of search patterns.

13. The method of performing simultaneous XPath evaluations as in claim 11 further comprising generating a following-parent or preceding parent search pattern as a bridge among siblings

42. The method of performing simultaneous Xpath evaluations over an XML data stream as in claim 1 wherein the plurality of search patterns further comprise a graph of search patterns.

14. An apparatus for performing simultaneous XPath evaluations over an XML data stream comprising:

an XML data stream consisting of a sequence of information items;

means for providing a search query consisting of a graph of search patterns;

means for searching a sequence of information items of the XML data stream along one or more directions using the search patterns; and

means for terminating the search of each direction of the one or more directions when no further results are possible.

15. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the means for searching the sequence further comprises means for determining a context data item.

16. The apparatus for performing simultaneous XPath evaluations as in claim 14 further comprising means for completing a first search direction of the graph of search patterns before starting a second search pattern of the graph of search patterns in the particular direction.

17. The apparatus for performing simultaneous XPath evaluations as in claim 15 further comprising means for determining a direction of the one or more directions based upon a predicate attribute.

18. The apparatus for performing simultaneous XPath evaluations as in claim 14 further comprising means for storing a location of a match from a first search pattern for use in conjunction with a second search pattern from another location of the graph of search patterns.

19. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the one or more directions further comprises a preceding search.

20. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the one or more directions further comprises a following search.

21. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the one or more directions further comprises an ancestor search.

22. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the query further comprises a search of XPath axis types.

23. The apparatus for performing simultaneous XPath evaluations as in claim 14 further comprises means for linking a first attribute of the first search pattern of the graph search patterns to a second attribute of a second search pattern of the graph of search patterns.

24. The apparatus for performing simultaneous XPath evaluations as in claim 14 wherein the search query further comprises a child and descendent search.

25. The apparatus for performing simultaneous XPath evaluations as in claim 24 further comprising means for forming a child search pattern followed by a descendent search pattern within the graph of search patterns.

26. The apparatus for performing simultaneous XPath evaluations as in claim 24 further comprising means for generating a following-parent or preceding parent search pattern as a bridge among siblings

27. A method of performing simultaneous XPath evaluations over an XML data stream comprising:

providing an XML data stream consisting of a sequence of information items;

providing a search query;

searching a sequence of information items of the XML data stream along one or more directions using the search patterns; and

terminating the search of each direction when no further results are possible.

28. The method of performing simultaneous XPath evaluations as in claim 27 wherein the step of providing the search query further comprises generating a graph of search patterns

29. The method of performing simultaneous XPath evaluations as in claim 27 wherein the step of searching the sequence further comprises determining a context data item.

30. The method of performing simultaneous XPath evaluations as in claim 27 further comprising completing a first search direction of the graph of search patterns before starting a second search pattern of the graph of search patterns in the particular direction.

31. The method of performing simultaneous XPath evaluations as in claim 30 further comprising determining a direction of the one or more directions based upon a predicate attribute.

32. The method of performing simultaneous XPath evaluations as in claim 27 further comprising storing a location of a match from a first search pattern for use in conjunction with a second search pattern from another location of the graph of search patterns.

33. The method of performing simultaneous XPath evaluations as in claim 27 wherein the one or more directions further comprises a preceding search.

34. The method of performing simultaneous XPath evaluations as in claim 27 wherein the one or more directions further comprises a following search.

35. The method of performing simultaneous XPath evaluations as in claim 27 wherein the one or more directions further comprises an ancestor search.

36. The method of performing simultaneous XPath evaluations as in claim 27 wherein the query further comprises a search of XPath axis types.

37. The method of performing simultaneous XPath evaluations as in claim 30 further comprises linking a first attribute of the first search pattern of the graph search patterns to a second attribute of a second search pattern of the graph of search patterns.

38. The method of performing simultaneous XPath evaluations as in claim 27 wherein the search query further comprises a child and descendent search.

39. The method of performing simultaneous XPath evaluations as in claim 38 further comprising forming a child search pattern followed by a descendent search pattern within the graph of search patterns.

40. The method of performing simultaneous XPath evaluations as in claim 38 further comprising generating a following-parent or preceding parent search pattern as a bridge among siblings.

41. A method of performing simultaneous Xpath evaluations over an XML data stream comprising:

providing a search query with a plurality of search patterns and a plurality of search axis;

simultaneously searching the XML data stream along the plurality of search axis using the plurality of search patterns; and

terminating the search along each search axis of the plurality of search axis when a match is found between at least some of the plurality of search patterns and XML data stream along the search axis.

43. An apparatus for performing simultaneous Xpath evaluations over an XML data stream comprising:

a search query with a plurality of search patterns and a plurality of search axis;

a search engine that simultaneously searches the XML data stream along the plurality of search axis using the plurality of search patterns; and

a matching processor that terminates the search along each search axis of the plurality of search axis when a match is found between at least some of the plurality of search patterns and XML data stream along the search axis.