Efficient peer-to-peer data management

Abstract

Internet has led to a fundamental increase of information that is avail- able to its users over the latest years. The users want to express their needs by simple means, such as queries and they want their queries to be evaluated without caring where the data are placed or how the queries are optimized. The work presented in this thesis contributes to the goal of declarative and efficient management of Web content in distributed settings and it is divided into two main chapters. In the first chapter we study OptimAX, an optimizer for the Active XML language which is able to rewrite a given Active XML document to an equivalent document which would, very likely, have smaller execution cost. With OptimAX we focus on the problem of distributed query optimization in the Active XML setting and we present two interesting case studies inspired by the R&D projects in which our group has been involved. In the second chapter, we propose solutions to the optimization problem from a different perspective. We optimize queries using a set of precomputed queries (materialized views). We have developed a peer-to-peer platform, called ViP2P (views in peer-to-peer) that gives to the users the opportunity to publish their XML documents and to specify views over these documents using a tree pattern language. Whenever a user asks a query, the system will try to find views that can be combined in order to find a rewriting equivalent to the asked query. We have carried WAN experiments that show the scalability of the ViP2P platform.

Το Διαδίκτυο έχει οδηγήσει σε μια θεμελιώδη αύξηση των πληροφοριών που είναι διαθέσιμες στους χρήστες τα τελευταία χρόνια. Οι χρήστες επιθυμούν να εκφράζουν τις ανάγκες τους με απλούς τρόπους, όπως μέσω ερωτημάτων, και θέλουν τα ερωτήματα αυτά να αξιολογούνται χωρίς να χρειάζεται να γνωρίζουν πού βρίσκονται τα δεδομένα ή πως βελτιστοποιούνται. Η εργασία που παρουσιάζεται σε αυτή τη διατριβή συμβάλλει στον στόχο της δηλωτικής και αποδοτικής διαχείρισης του περιεχομένου του Web σε κατανεμημένα περιβάλλοντα και χωρίζεται σε δύο βασικά κεφάλαια. Στο πρώτο κεφάλαιο μελετάμε τον OptimAX, έναν βελτιστοποιητή για τη γλώσσα Active XML, ο οποίος είναι ικανός να αναδιατυπώνει ένα έγγραφο Active XML σε ένα ισοδύναμο έγγραφο που, με μεγάλη πιθανότητα, θα έχει μικρότερο κόστος εκτέλεσης. Με τον OptimAX εστιάζουμε στο πρόβλημα της κατανεμημένης βελτιστοποίησης ερωτημάτων στο πλαίσιο του Active XML και παρουσιάζουμε δύο ενδιαφέρουσες μελέτες, εμπνευσμένες από ερευνητικά και αναπτυξιακά έργα στα οποία συμμετείχε η ομάδα μας. Στο δεύτερο κεφάλαιο, προτείνουμε λύσεις στο πρόβλημα της βελτιστοποίησης από διαφορετική σκοπιά. Βελτιστοποιούμε ερωτήματα χρησιμοποιώντας ένα σύνολο προϋπολογισμένων ερωτημάτων (υλοποιημένες όψεις). Έχουμε αναπτύξει μια πλατφόρμα peer-to-peer, που ονομάζεται ViP2P (views in peer-to-peer), η οποία δίνει τη δυνατότητα στους χρήστες να δημοσιεύουν τα έγγραφα XML τους και να ορίζουν όψεις πάνω σε αυτά χρησιμοποιώντας μια γλώσσα μοτίβων δέντρου (tree pattern language). Όταν ένας χρήστης υποβάλει ένα ερώτημα, το σύστημα προσπαθεί να βρει όψεις που μπορούν να συνδυαστούν ώστε να παραχθεί ένα ισοδύναμο ερώτημα με αυτό που υποβλήθηκε. Πραγματοποιήσαμε πειράματα σε ευρείας περιοχής δίκτυα (WAN), τα οποία δείχνουν την επεκτασιμότητα της πλατφόρμας ViP2P.

Le développement de l’internet a conduit à une grande augmentation de l’information disponible pour les utilisateurs. Ces utilisateurs veulent exprimer leur besoins de manière simple, par l’intermédiaire des requêtes, et ils veulent que ces requêtes soient évaluées sans se soucier où les données sont placées ou comment les requêtes sont évaluées. Le travail qui est présenté dans cette thèse contribue à l’objectif de la gestion du contenu du Web de manière déclarative et efficace et il est composé de deux parties. Dans le premier partie, nous présentons OptimAX, un optimiseur pour la langage Active XML qui est capable de reécrire un document Active XML donné dans un autre document équivalent dont l’évaluation sera plus efficace. OptimAX contribue à résoudre le problème d’optimisation des requêtes distribuées dans le cadre d’Active XML et nous présentons deux études de cas. Dans le deuxième partie, nous proposons une solution au problème de l’optimisation d’un point de vue différent. Nous optimisons des requêtes en utilisant un ensemble des requêtes pré-calculées (vues matérialisées). Nous avons développé une plateforme pair-à-pair, qui s’appelle ViP2P (views in peer-to-peer) qui permet aux utilisateurs de publier des documents XML et de spécifier des vues sur ces documents en utilisant une langage de motifs d’arbres. Quand un utilisateur pose une requête, le système essaiera de trouver des vues qui peuvent être combinées pour construire une réécriture équivalente à la requête. Nous avons fait des expérimentations en utilisant des ordinateurs des différents laboratoires en France et nous avons montré que notre plateforme passe à l’échelle jusqu’à plusieurs GB de données.