Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2022-10-12
Συγγραφέας:
ΠΛΑΣ ΚΩΝΣΤΑΝΤΙΝΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Γιάννης Ιωαννίδης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Θεόφιλος Μαΐλης, Μεταδιδακτορικός Ερευνητής, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Πρωτότυπος Τίτλος:
View and Index Selection on Graph Databases
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Επιλογή Όψεων και Ευρετηρίων σε Βάσεις Δεδομένων Γραφημάτων
Περίληψη:
Μια από τις σημαντικότερες πτυχές των βάσεων δεδομένων γραφημάτων με εγγενή
επεξεργασία γράφων είναι η ιδιότητα γειτνίασης χωρίς ευρετήριο (index-free-adjacency),
βάση της οποίας όλοι οι κόμβοι του γράφου έχουν άμεση φυσική διεύθυνση RAM και
δείκτες σε άλλους γειτονικούς κόμβους. Η ιδιότητα γειτνίασης χωρίς ευρετήριο επιταχύνει
την απάντηση ερωτημάτων για ερωτήματα που συνδέονται με έναν (ή περισσότερους)
συγκεκριμένους κόμβους εντός του γραφήματος, δηλαδή τους κόμβους αγκύρωσης
(anchor nodes). Ο αντίστοιχος κόμβος αγκύρωσης χρησιμοποιείται ως σημείο εκκίνησης
για την απάντηση στο ερώτημα εξετάζοντας τους παρακείμενους κόμβους του αντί για
ολόκληρο το γράφημα. Παρόλα αυτά, τα ερωτήματα που δεν αρχίζουν από κόμβους
αγκύρωσης απαντώνται πολύ πιο δύσκολα, καθώς ο σχεδιαστής ερωτημάτων(query
planner) θα πρέπει να εξετάσει ένα μεγάλο μέρος του γραφήματος για να απαντήσει στο
αντίστοιχο ερώτημα. Σε αυτή την εργασία μελετάμε τεχνικές επιλογής όψεων και
ευρετηρίων προκειμένου να επιταχύνουμε την προαναφερθείσα κατηγορία ερωτημάτων.
Αναλύουμε διαφορετικές στρατηγικές επιλογής όψεων και ευρετηρίων για την απάντηση
ερωτημάτων και δείχνουμε ότι, ανάλογα με τα χαρακτηριστικά του ερωτήματος, τη βάση
δεδομένων γραφημάτων και το αντίστοιχο σύνολο απαντήσεων, μια διαφορετική
στρατηγική μπορεί να είναι βέλτιστη μεταξύ των εναλλακτικών λύσεων ευρετηρίασης και
υλοποίησης προβολής. Πριν από την επιλογή των όψεων και των ευρετηρίων, το σύστημά
μας χρησιμοποιεί τεχνικές εξόρυξης προτύπων για να μαντέψει τα χαρακτηριστικά των
μελλοντικών ερωτημάτων. Έτσι, ο αρχικός φόρτος εργασίας του ερωτήματος
αντιπροσωπεύεται από μια πολύ μικρότερη σύνοψη των μοτίβων ερωτημάτων που είναι
πιο πιθανό να εμφανιστούν σε μελλοντικά ερωτήματα, με κάθε μοτίβο να έχει τον
αντίστοιχο αναμενόμενο αριθμό εμφανίσεων. Η στρατηγική επιλογής μας βασίζεται σε μια
στρατηγική επιλογής άπληστης όψεων & ευρετηρίων που σε κάθε βήμα της εκτέλεσής της
προσπαθεί να μεγιστοποιήσει την αναλογία του οφέλους από την υλοποίηση μιας/ενός
όψεως/ευρετηρίου, προς το αντίστοιχο κόστος αποθήκευσής τους. Ο αλγόριθμος επιλογής
μας είναι εμπνευσμένος από τον αντίστοιχο άπληστο αλγόριθμο για τη «Μεγιστοποίηση
μιας μη ελαττούμενης συνάρτησης υποδομοστοιχειωτού συνόλου που υπόκειται σε
περιορισμό σακιδίου». Η πειραματική μας αξιολόγηση δείχνει ότι όλα τα βήματα της
διαδικασίας επιλογής ευρετηρίου ολοκληρώνονται σε λίγα δευτερόλεπτα, ενώ οι
αντίστοιχες επανεγγραφές επιταχύνουν το 15,44% των ερωτημάτων στον φόρτο εργασίας
των ερωτημάτων της DbPedia. Αυτά τα ερωτήματα εκτελούνται στο 1,63% του αρχικού
τους χρόνου κατά μέσο όρο.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
βάσεις δεδομένων γραφημάτων, βελτιστοποίηση ερωτημάτων, επιλογή όψεων, υλοποίηση όψεων, γραφήματα γνώσης
Αρ. σελίδων ευρετηρίου:
4
Αρ. βιβλιογραφικών αναφορών:
84
