Managing evolution in web data through complex changes

Abstract

Data published on the web frequently change, as errors may need to be fixed or new knowledge has to be incorporated. Data consumers need to know what changed among versions, as well as how and why. In our view, for understanding data evolution changes should be treated as first-class-citizens. Treating changes as first-class-citizens poses several challenges regarding modeling, defining, detecting and querying changes. In this thesis, we study these directions and work upon two basic standards for web data: RDF and XML.First, we proposed modeling and supporting simple and complex changes, as well as any relations among them, for interpreting evolution on RDF(S) knowledge-bases. Furthermore, we formally defined an intuitive, user-friendly language, based on change semantics for defining complex changes. Moreover, we presented a detection algorithm for the proposed complex change definition language. Also, the correctness of the proposed implementation with respect to the language semantics is presented. Finally, we extensively evaluated the proposed approach both qualitatively and experimentally.Second, we proposed a query language named evo-path, an XPath extension for querying both data versions and changes in the context of semistructured XML data. This work builds upon evo-graph, a model that captures evolving data along with changes, and evoXML, an XML representation of evo-graph. Also, we implemented and experimentally evaluated the basic concepts of evo-graph in the C2D framework, using XML technologies.

Τα δεδομένα που δημοσιεύονται στον ιστό συχνά αλλάζουν, καθώς πιθανά σφάλματα ενδέχεται να πρέπει να διορθωθούν ή να ενσωματωθεί νέα γνώση. Οι χρήστες των δεδομένων πρέπει να γνωρίζουν τί άλλαξε μεταξύ των εκδόσεων, καθώς επίσης πώς και γιατί. Για την κατανόηση της εξέλιξης των δεδομένων, θεωρούμε ότι οι αλλαγές θα πρέπει να αντιμετωπίζονται ως πρώτης τάξης πολίτες. Η αντιμετώπιση των αλλαγών ως πρώτης τάξης πολίτες θέτει πολλές προκλήσεις σχετικά με τη μοντελοποίηση, τον ορισμό, τον εντοπισμό και την επερώτηση αλλαγών. Σε αυτή τη διατριβή, μελετάμε αυτές τις κατευθύνσεις και εργαζόμαστε πάνω σε δύο βασικά πρότυπα για τα δεδομένα ιστού: το RDF και το XML. Πρώτον, προτείναμε τη μοντελοποίηση και την υποστήριξη απλών και σύνθετων αλλαγών, καθώς και τυχόν σχέσεων μεταξύ τους, για την ερμηνεία της εξέλιξης σε βάσεις γνώσης δεδομένων RDF(S). Επιπλέον, ορίσαμε τυπικά μια διαισθητική, φιλική προς τον χρήστη γλώσσα, βασισμένη στη σημασιολογία των αλλαγών για τον ορισμό σύνθετων αλλαγών. Ακόμη, παρουσιάσαμε έναν αλγόριθμο για τον εντοπισμό στιγμιότυπων σύνθετων αλλαγών για την προτεινόμενη γλώσσα ορισμού σύνθετων αλλαγών. Επίσης, παρουσιάστηκε η ορθότητα του προτεινόμενου αλγορίθμου σε σχέση με τη σημασιολογία της γλώσσας. Τέλος, αξιολογήσαμε εκτενώς την προτεινόμενη προσέγγιση τόσο ποιοτικά όσο και πειραματικά. Δεύτερον, προτείναμε μια γλώσσα επερωτήσεων που ονομάζεται evo-path, ως επέκταση της XPath για την επερώτηση τόσο εκδόσεων των δεδομένων όσο και αλλαγών στο πλαίσιο ημιδομημένων δεδομένων XML. Αυτή η εργασία βασίζεται στο evo-graph, ένα μοντέλο που καταγράφει εξελισσόμενα δεδομένα μαζί με αλλαγές, και στο evoXML, μια XML αναπαράσταση του evo-graph. Επίσης, υλοποιήσαμε και αξιολογήσαμε πειραματικά τις βασικές έννοιες του evo-graph στο πλαίσιο «C2D», χρησιμοποιώντας τεχνολογίες XML.