Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/6076C420-0BBC-4841-AD75-54DEEA60248B | ||
| Year | 2002 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | N. Polyzotis and M. Garofalakis, "Structure and value synopses for XML data graphs", in 28th International Conference on Very Large Data Bases, August 2002, pp. 466-477. | ||
| Appears in Collections |
All existing proposals for querying XML (e.g.,XQuery) rely on a pattern-specification language thatallows (1) path navigation and branching through thelabel structure of the XML data graph, and (2) predicateson the values of specific path/branch nodes, inorder to reach the desired data elements. Optimizingsuch queries depends crucially on the existence of concisesynopsis structures that enable accurate compiletimeselectivity estimates for complex path expressionsover graph-structured XML data. In this paper, weextent our earlier work on structural XSKETCH synopsesand we propose an (augmented) XSKETCH synopsismodel that exploits localized stability and valuedistributionsummaries (e.g., histograms) to accuratelycapture the complex correlation patterns that can existbetween and across path structure and element values inthe data graph. We develop a systematic XSKETCH estimationframework for complex path expressions withvalue predicates and we propose an efficient heuristicalgorithm based on greedy forward selection for buildingan effective XSKETCH for a given amount of space(which is, in general, an N P-hard optimization problem).Implementation results with both synthetic andreal-life data sets verify the effectiveness of our approach.
Copyright © DIAS 2013
