Ευέλικτη αναζήτηση σε δεδομένα XML

Abstract

Το μοντέλο δεδομένων XML χρησιμοποιείται πλέον σε πολλές κοινές εφαρμογές, όπως π.χ. οι βάσεις δεδομένων, ο σημασιολογικός ιστός και η ανταλλαγή πληροφοριών. Πολλές γλώσσες ερωτήσεων έχουν προτάξει για την εξαγωγή δεδομένων από ένα XML έγγραφο, όπως για παράδειγμα η XPath και η XQuery. Η αποτίμηση των ερωτήσεων αυτών έχει αποτελέσει αντικείμενο μελέτης για πληθώρα ερευνητικών εργασιών. Το μεγαλύτερο μέρος της έρευνας όμως στο χώρο έχει εστιάσει στην αποτίμηση απλών μορφών ερωτήσεων, όπως οι ερωτήσεις μονοπατιού και οι ερωτήσεις δέντρου, οι οποίες δεν επαρκούν να καλύψουν τις συνεχώς αυξανόμενες ανάγκες. Στα πλαίσια της παρούσας διδακτορικής διατριβής, μελετώνται ερωτήσεις χωρίς σαφή δομή, οι οποίες παρέχουν μεγάλη ευελιξία στο χρήστη, επιτρέποντάς του να εξάγει πληροφορίες από πολλές πηγές ταυτόχρονα ή από πηγές των οποίων τη δομή δε γνωρίζει πλήρως. Τέτοιες ερωτήσεις μπορούν να εκφραστούν στις πρότυπες γλώσσες ερωτήσεων XPath και XQuery. Παρόλα αυτά, δεν έχουν ως τώρα προταθεί αλγόριθμοι για την επεξεργασία και αποτίμησή τους. Οι ερωτήσεις μερικού μονοπατιού και μερικού δέντρου μπορούν να τεθούν ισοδύναμα σε μια κανονική μορφή, η οποία είναι κατευθυνόμενος ακυκλικός γράφος. Για το σκοπό αυτό, εισάγεται ένα συνεπές και πλήρες σύνολο κανόνων εξαγωγής δομικών εκφράσεων, παρέχονται αναγκαίες και ικανές συνθήκες για τον έλεγχο ικανοποιησιμότητας, και παρέχονται συνθήκες για αναγνώριση πλεοναζόντων κόμβων. Για την αποτίμηση ερωτήσεων μερικού μονοπατιού και μερικού δέντρου, αναπτύσσονται οι ολιστικοί αλγόριθμοι στοίβας PartialPathStack και PartialTrceStack αντίστοιχα. Οι αλγόριθμοι αυτοί εκμεταλλεύονται μια τοπολογική διάταξη των κόμβων στην ερώτηση και ταιριάζουν ολιστικά την ερώτηση πάνω στο δέντρο XML. Ορίζεται ο απόλυτος και ο σχετικός εγκλεισμός ερωτήσεων. Μια ερώτηση εγκλείεται απόλυτα σε μια άλλη αν σε οποιοδήποτε δέντρο XML τα αποτέλεσματα της πρώτης ερώτησης είναι υποσύνολο των αποτελεσμάτων της δεύτερης. Μια ερώτηση εγκλείεται σε μια άλλη σε σχέση με κάποιο δέντρο XML αν τα αποτέλεσματα της πρώτης ερώτησης στο δέντρο αυτό είναι υποσύνολο των αποτελεσμάτων της δεύτερης. Ο σχετικός εγκλεισμός είναι πιο αργός. Για την επιτάχυνση του, παρέχονται ευριστικές τεχνικές. Όλοι οι αλγόριθμοι αποτίμησης και εγκλεισμού έχουν υλοποιηθεί και μια εκτενής πειραματική αξιολόγηση έχει διενεργηθεί. Τα πειραματικά αποτελέσματα επιβεβαιώνουν την ανωτερότητα των προτεινόμενων αλγορίθμων αποτίμησης έναντι άλλων αλγορίθμων που αποτελούν επέκταση υπαρχόντων αλγορίθμων για ερωτήσεις μονοπατιού και δέντρου. Τέλος, τα πειράματα πιστοποιούν την προσφορά των ευριστικών τεχνικών στον έλεγχο του σχετικού εγκλεισμού.