Streaming XPath algorithm for XPath expressions with predicates
First Claim
1. A method for evaluating a path query, the path query corresponding to a query tree including a plurality of query nodes, at least one query node of the plurality of query nodes corresponding to at least one predicate and having a level, the at least one predicate being for at least one previous query node, the method comprising:
- scanning a plurality of data nodes of a document to provide a data tree;
determining if the plurality of data nodes matches the plurality of query nodes;
placing data related to the data node in match stacks corresponding to matched query nodes, the data for the at least one query node including at least one attribute corresponding to the at least one predicate; and
propagating a matching of the at least one query node backward to a matching of the at least one previous query node.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system for evaluating a path query are disclosed. The path query corresponds to a query tree including a plurality of query nodes. At least one query node corresponds to at least one predicate and is at a level. The predicate(s) are evaluated for previous query node(s). The method and system include scanning data nodes of a document and determining if the data nodes match the query nodes. The method and system also include placing data related to the data node in match stacks corresponding to matched query nodes. The data for the query node(s) include attribute(s) corresponding to the predicate(s). The method and system further include propagating a matching of the at least one query node backward to a matching of the at least one previous query node.
-
Citations
18 Claims
-
1. A method for evaluating a path query, the path query corresponding to a query tree including a plurality of query nodes, at least one query node of the plurality of query nodes corresponding to at least one predicate and having a level, the at least one predicate being for at least one previous query node, the method comprising:
-
scanning a plurality of data nodes of a document to provide a data tree;
determining if the plurality of data nodes matches the plurality of query nodes;
placing data related to the data node in match stacks corresponding to matched query nodes, the data for the at least one query node including at least one attribute corresponding to the at least one predicate; and
propagating a matching of the at least one query node backward to a matching of the at least one previous query node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 16)
-
-
9. A computer-readable medium containing a program for evaluating a path query, the path query corresponding to a query tree including a plurality of query nodes, at least one query node of the plurality of query nodes corresponding to at least one predicate and having a level, the at least one predicate being for at least one previous query node, the program including instructions for:
-
scanning a plurality of data nodes of a document to provide a data tree;
determining if the plurality of data nodes matches the plurality of query nodes;
placing data related to the data node in match stacks corresponding to matched query nodes, the data for the at least one query node including at least one attribute corresponding to the at least one predicate; and
propagating a matching of the at least one query node backward to a matching of the at least one previous query node. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
17. A system for evaluating a query, the system comprising:
-
a query tree including a plurality of query nodes, at least one query node of the plurality of query nodes corresponding at least one predicate and having a level, the at least one predicate being evaluated for at least one previous query node, the query tree for using determining if a plurality of data nodes of a data tree corresponding to a scanned document matches the plurality of query nodes, and a matching of the at least one query node to be propagated backward to a matching of the at least one previous query node; and
a plurality of matched stacks for storing data related to the data node in match stacks corresponding to matched query nodes, the data for the at least one query node including at least one attribute corresponding to the at least one predicate. - View Dependent Claims (18)
-
Specification