Fast processing of an XML data stream
First Claim
1. A method of answering a query of semistructured data, comprising the steps of:
- (a) constructing an answer automaton, based at least in part on the query and on a schema of the data; and
(b) applying said answer automaton to the data to answer the query.
1 Assignment
0 Petitions
Accused Products
Abstract
To answer one or more queries of semistructured data, an answer automaton is constructed, based at least in part on the queries and on a schema of the data. The answer automaton is applied to the data to answer the queries. Preferably, to construct the answer automaton, a schema automaton is constructed for the schema, a query automaton is constructed for the queries, and the schema automaton and the query automaton are merged. If there are more than one query, separate query automata are constructed for the different queries and then are united to provide a joint query automaton. Preferably, all the automata are deterministic finite automata. Most preferably, all the automata are isostate automata.
-
Citations
39 Claims
-
1. A method of answering a query of semistructured data, comprising the steps of:
-
(a) constructing an answer automaton, based at least in part on the query and on a schema of the data; and (b) applying said answer automaton to the data to answer the query. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method of answering a plurality of queries of semistructured data, comprising the steps of:
-
(a) constructing an answer automaton, based at least in part on the queries and on a schema of the data; and (b) applying said answer automaton to the data to answer the queries. - View Dependent Claims (16, 17)
-
-
18. A device for processing semistructured data, comprising:
-
(a) a memory for storing executable code for answering at least one query of the data, said executable code including; (i) executable code for constructing an answer automaton, based at least in part on said at least one query and on a schema of the data, and (ii) executable code for applying said answer automaton to the data to answer said at least one query; and (b) a processor for executing said executable code. - View Dependent Claims (19)
-
-
20. A computer-readable storage medium having computer-readable code embodied on said computer-readable storage medium, the computer-readable code for answering at least one query of semistructured data, the computer-readable code comprising:
-
(a) program code for constructing an answer automaton based at least in part on a schema of the data and on the at least one query; and (b) program code for applying said answer automaton to the data to answer said at least one query.
-
-
21. A system for answering a query of semistructured data, comprising:
-
(a) a schema automaton constructor for constructing a schema automaton for a schema of the data; (b) a query automaton constructor for constructing a query automaton for the query; (c) an answer automaton constructor for merging said schema automaton and said query automaton to provide an answer automaton; and (d) an answer automaton engine for applying the answer automaton to the data to answer the query. - View Dependent Claims (22, 23, 24, 25, 26)
-
-
27. An apparatus for answering a plurality of queries of semistructured data, comprising:
-
(a) a schema automaton constructor for constructing a schema automaton for a schema of the data; (b) a query automaton constructor for constructing respective query automata for the queries; (c) a query automaton unite engine for uniting said query automata to provide a joint query automaton; (d) an answer automaton constructor for merging said schema automaton and said joint query automaton to provide an answer automaton; and (e) an answer automaton engine for applying the answer automaton to the data to answer the queries. - View Dependent Claims (28, 29)
-
-
30. A method of answering a query of semistructured data, comprising the steps of:
-
(a) constructing an answer automaton, based at least in part on the query, said constructing including removing redundant symbols from said answer automaton; and (b) applying said answer automaton to the data to answer the query.
-
-
31. A device for processing semistructured data, comprising:
-
(a) a memory for storing executable code for answering a query of the data, said executable code including; (i) executable code for constructing an answer automaton, based at least in part on said query, said constructing including removing redundant symbols from said answer automaton, and (ii) executable code for applying said answer automaton to the data to answer said query; and (b) a processor for executing said executable code. - View Dependent Claims (32)
-
-
33. A computer-readable storage medium having computer-readable code embodied on said computer-readable storage medium, the computer-readable code for answering a query of semistructured data, the computer-readable code comprising:
-
(a) program code for constructing an answer automaton, based at least in part on the query, said constructing including removing redundant symbols from said answer automaton; and (b) program code for applying said answer automaton to the data to answer the query.
-
-
34. A system for answering a query of semistructured data, comprising:
-
(a) an answer automaton constructor for constructing an answer automaton, based at least in part on the query, said constructing including removing redundant symbols from said answer automaton; and (b) an answer automaton engine for applying said answer automaton to the data to answer the query.
-
-
35. A method of answering a query of semistructured data, comprising the steps of:
-
(a) constructing, for the query, a finite query automaton that accepts an alphabet; (b) mapping said alphabet into a set of transition indices of said finite query automaton, thereby transforming said finite query automaton into an isostate query automaton; (c) transforming said isostate query automaton into an answer automaton; and (d) applying said answer automaton to the data to answer the query.
-
-
36. A device for processing semistructured data, comprising:
-
(a) a memory for storing executable code for answering a query of the data, said executable code including; (i) executable code for constructing, for said query, a finite query automaton that accepts an alphabet, (ii) executable code for mapping said alphabet into a set of transition indices of said finite query automaton, thereby transforming said finite query automaton into an isostate query automaton, (iii) executable code for transforming said isostate query automaton into an answer automaton, and (iv) executable code for applying said answer automaton to the data to answer said query; and (b) a processor for executing said executable code. - View Dependent Claims (37)
-
-
38. A computer-readable storage medium having computer-readable code embodied on said computer-readable storage medium, the computer-readable code for answering a query of semistructured data, the computer-readable code comprising:
-
(a) program code for constructing, for the query, a finite query automaton that accepts an alphabet; (b) program code for mapping said alphabet into a set of transition indices of said finite query automaton, thereby transforming said finite query automaton into an isostate query automaton; (c) program code for transforming said isostate query automaton into an answer automaton; and (d) program code for applying said answer automaton to the data to answer the query.
-
-
39. A system for answering a query of semistructured data, comprising:
-
(a) a query automaton constructor for; (i) constructing, for the query, a finite query automaton that accepts an alphabet, and (ii) mapping said alphabet into a set of transition indices of said finite query automaton, thereby transforming said finite query automaton into an isostate query automaton; (b) an answer automaton constructor for transforming said isostate query automaton into an answer automaton; and (c) an answer automaton engine for applying said answer automaton to the data to answer the query.
-
Specification