System and method for filtering XML documents with XPath expressions

• US 20040010752A1
• Filed: 07/09/2002
• Published: 01/15/2004
• Est. Priority Date: 07/09/2002
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Chan, Chee-Yong, Felber, Pascal A., Rastogi, Rajeev, Garofalakis, Minos N.
• Application Number:
  US10/191,140
• Publication Number:
  US 20040010752A1
• Time in Patent Office: Days
• US Class Current: 715/513
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

A system for, and method of, filtering an XML document with XPath expressions and a selective data dissemination system incorporating the system or the method. In one embodiment, the filtering system includes: (1) a tree builder that builds a document data tree for the XML document and an XPath expression tree based on substrings in the XPath expressions and (2) a tree prober, associated with the tree builder, that employs the XPath expression tree to probe the document data tree and obtain matches with the substrings.

Claims

1. A system for filtering an XML document with XPath expressions, comprising:

a tree builder that builds a document data tree for said XML document and an XPath expression tree based on substrings in said XPath expressions; and

a tree prober, associated with said tree builder, that employs said XPath expression tree to probe said document data tree and obtain matches with said substrings.

2. The system as recited in claim 1 wherein said matches are ordered matches.

3. The system as recited in claim 1 wherein said tree builder comprises an event-based parsing interface.

4. The system as recited in claim 1 wherein said substrings are minimal decompositions of said XPath expressions.

5. The system as recited in claim 1 wherein said tree prober parses said document data tree with said XPath expression tree to detect matching substrings in said XML document and iterates, for each of said matching substrings, through all instances of said matching substrings in said document data tree to determine whether said matching substrings are non-redundant.

6. The system as recited in claim 1 wherein said tree builder builds a substring table for said XPath expression tree.

7. The system as recited in claim 1 wherein said tree prober probes said substring table only for matching substrings that appear as a leaf substring in one of said XPath expressions.

8. A method of searching an XML document, comprising:

building an XPath expression tree based on substrings in XPath expressions;

parsing said XML document with said XPath expression tree to detect matching substrings in said XML document; and

iterating, for each of said matching substrings, through all instances of said matching substrings in said XML document to determine whether said matching substrings are non-redundant.

9. The method as recited in claim 8 wherein said instances are ordered matches.

10. The method as recited in claim 8 wherein said parsing is carried out with an event-based parsing interface.

11. The method as recited in claim 8 wherein said substrings are minimal decompositions of said XPath expressions.

12. The method as recited in claim 8 further comprising building a substring table for said XPath expression tree.

13. The method as recited in claim 12 wherein said probing comprises probing said substring table only for matching substrings that appear as a leaf substring in one of said XPath expressions.

14. A selective data dissemination system, comprising:

a document receiver for receiving XML documents from a plurality of publishers;

a subscription receiver for receiving words of interest from a plurality of subscribers, said words being encapsulable in XPath expressions;

a tree builder that builds a document data tree for said XML document and an XPath expression tree based on substrings in said XPath expressions;

a tree prober that employs said XPath expression tree to probe said document data tree and obtain matches with said substrings; and

a document disseminator that selectively disseminates said XML documents to said plurality of subsribers based on said matches.

15. The system as recited in claim 14 wherein said matches are ordered matches.

16. The system as recited in claim 14 wherein said tree builder comprises an event-based parsing interface.

17. The system as recited in claim 14 wherein said substrings are minimal decompositions of said XPath expressions.

18. The system as recited in claim 14 wherein said tree prober parses said document data tree with said XPath expression tree to detect matching substrings in said XML document and iterates, for each of said matching substrings, through all instances of said matching substrings in said document data tree to determine whether said matching substrings are non-redundant.

19. The system as recited in claim 14 wherein said tree builder builds a substring table for said XPath expression tree.

20. The system as recited in claim 14 wherein said tree prober probes said substring table only for matching substrings that appear as a leaf substring in one of said XPath expressions.