Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

Structure and value synopses for XML data graphs

Polyzotis, Neoklis, Garofalakis Minos

Πλήρης Εγγραφή

---

Περίληψη

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.

Υπηρεσίες