Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Structure and value synopses for XML data graphs

Polyzotis, Neoklis, Garofalakis Minos

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


URI: http://purl.tuc.gr/dl/dias/6076C420-0BBC-4841-AD75-54DEEA60248B
Έτος 2002
Τύπος Πλήρης Δημοσίευση σε Συνέδριο
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά 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.
Εμφανίζεται στις Συλλογές

Περίληψη

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.

Υπηρεσίες

Στατιστικά