Name
Abstract | ||
|---|---|---|
All known algorithms for evaluating advanced XPath queries (e.g., ones with predicates or with closure axes) on XML streams employ buffers to temporarily store fragments of the document stream. In many cases, these buffers grow very large and constitute a major memory bottleneck. In this paper, we identify two broad classes of evaluation problems that independently necessitate the use of large memory buffers in evaluation of queries over XML streams: (1) full-fledged evaluation (as opposed to just filtering) of queries with predicates; (2) evaluation (whether full-fledged or filtering) of queries with "multi-variate" predicates.We prove quantitative lower bounds on the amount of memory required in each of these scenarios. The bounds are stated in terms of novel document properties that we define. We show that these scenarios, in combination with query evaluation over recursive documents, cover the cases in which large buffers are required. Finally, we present algorithms that match the lower bounds for an important fragment of XPath. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1065167.1065195 | PODS |
Keywords | Field | DocType |
full-fledged evaluation,evaluation problem,xml stream,major memory bottleneck,large memory buffer,query evaluation,document stream,large buffer,lower bound,advanced xpath query,consistency,concurrency control,serializability,anomaly,two phase locking,snapshot isolation | Bottleneck,Snapshot isolation,Serializability,XML,Concurrency control,Computer science,Two-phase locking,Theoretical computer science,XPath,Recursion | Conference |
ISBN | Citations | PageRank |
1-59593-062-0 | 39 | 1.42 |
References | Authors | |
23 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ziv Bar-Yossef | 1 | 1776 | 118.00 |
| Marcus Fontoura | 2 | 1116 | 61.74 |
| Vanja Josifovski | 3 | 2265 | 148.84 |