| Περίληψη |
Η μεγάλη ανάπτυξη του Σημασιολογικού Ιστού καθιστά όλο και πιο ευρύτερη την χρήση εφαρμογών που στηρίζονται σε αυτόν. H πιο ενδεικτική κι ευρύτερα αποδεκτή κατηγορία εφαρμογών του είναι οι Διαδικτυακές Πύλες, με πλέον χαρακτηριστικό παράδειγμα τον Κατάλογο Netscape Open Directory (ODP). Η δομή της πύλης αυτή συνίσταται σε εκτεταμένες ιεραρχίες υποκλάσεων (isA) από διάφορα επιμέρους θέματα. Συνεπώς, η βελτιστοποίηση της πλοήγησης σε αυτού του είδους τις πύλες που μεταφράζεται σε επερωτήσεις μεταβατικού κλεισίματος, είναι ένα ανοικτό πρόβλημα. Συγκεκριμένα, θα συνηγορήσουμε στην χρήση σχημάτων κωδικοποίησης για την μοντελοποίηση των θεματικών αυτών ιεραρχιών στοχεύοντας στην απάντηση βασικών επερωτήσεων όπως είναι ο έλεγχος υπαλληλίας, απόγονοι, πρόγονοι, ?κοντινότερος? κοινός πρόγονος κλπ. Βασικός στόχος μας με την επιλογή των σχημάτων για την κωδικοποίηση των ιεραρχιών είναι η αποφυγή του υπολογισμού των χρονοβόρων μεταβατικών κλεισιμάτων, λαμβάνοντας υπόψη ότι α) οι ιεραρχίες υπαλληλίας των κλάσεων των πυλών μπορεί να κυμαίνονται μεταξύ απλών δέντρων και σύνθετων DAGs κι άρα θα πρέπει το σχήμα κωδικοποίησης να μπορεί να ανταποκριθεί σε μια λογική αύξηση του χώρου αποθήκευσης και του χρόνου εκτέλεσης των επερωτήσεων, και β) η πλοήγηση στα σχήματα των πυλών βασίζεται στην ανάκτηση κλάσεων με την χρήση σύνθετων συνθηκών φιλτραρίσματος στις σχέσεις υπαλληλίας κι συνεπώς χρειάζεται η δημιουργία ετικετών για τις κλάσεις, να είναι κατάλληλη ώστε να μπορούν ικανοποιητικά να χρησιμοποιηθούν από δεδομένους δείκτες μιας βάσης Αρχικά, θα παρουσιάσουμε μια ποιοτική σύγκριση των τριών βασικών κατηγοριών σχημάτων κωδικοποίησης, που είναι α) τα σχήματα με χρήση διανυσμάτων - δηφίων, β) τα σχήματα με χρήση προθέματος και γ) τα σχήματα με χρήση διαστημάτων. Κατόπιν, θα προχωρήσουμε στην παρουσίαση δυο επιμέρους σχημάτων κωδικοποίησης ως βέλτιστες επιλογές κρίνοντάς τα ως προς την ικανοποιητική υλοποίηση των επερωτήσεων με ετικέτες, χρησιμοποιώντας ένα καθιερωμένο σχεσιακό σύστημα διαχείρισης βάσεων δεδομένων. Αναφορικά, πρόκειται για το σχήμα του Dewey με χρήση προθέματος και για το σχήμα με χρήση διαστήματος των Agrawal, Borgida και Jagadish. Η επιμέρους σύγκριση των δυο σχημάτων αυτών θα γίνει με μία πειραματική αξιολόγηση τους με βάση τα κριτήρια του χρόνου εκτέλεσης των προαναφερθέντων βασικών επερωτήσεων αλλά και του αναγκαίου χώρου αποθήκευσης των κωδικοποιημένων ιεραρχιών χρησιμοποιώντας το σύστημα διαχείρισης βάσεων δεδομένων της PostgreSQL. Ως πεδίο δοκιμής της αξιολόγησης αυτής θα χρησιμοποιήσουμε κατ? αρχήν τις 16 θεματικές ιεραρχίες του ODP καταλόγου που έχουν την μορφολογία δέντρου, αλλά εν συνεχεία με την παραγωγή ενός συνθετικά δημιουργούμενου γράφου εκ των ιεραρχιών αυτών θα επεκτείνουμε την αξιολόγηση αυτή. Τέλος η σύγκριση αυτή παράλληλα θα μελετήσει και την επίδραση της χρήση ή μη της δυνατότητας συμπίεσης των ετικετών στην έκφραση κι υλοποίηση των επερωτήσεων αυτών. Τα αποτελέσματα από την πειραματική αξιολόγηση της χρήσης των δυο σχημάτων κωδικοποίησης είναι αρχικά ότι οι επερωτήσεις τους είναι 2 μέχρι και 3 φορές πιο γρήγορες έναντι των αντίστοιχων στα μεταβατικά κλεισίματα. Για την περίπτωση του δέντρου τα δυο σχήματα κωδικοποίησης έχουν σχεδόν παρόμοιες επιδόσεις στις επερωτήσεις, με τον Dewey να απαιτεί κατά μέσο όρο 8 φορές περισσότερο έναντι του Agrawal. Στην περίπτωση του γράφου έχουμε μια επιβάρυνση στο χώρο αποθήκευσης 2,24 φορές περισσότερο έναντι του δέντρου στον Agrawal (με συμπίεση) και 2,76 φορές περισσότερο (χωρίς συμπίεση), και 2,71 φορές περισσότερο στον Dewey (με συμπίεση). Από την άλλη πλευρά ο χρόνος εκτέλεσης των επερωτήσεων είναι κατά μέσο όρο 5 φορές μεγαλύτερος από ότι την περίπτωση του δέντρου για τον Agrawal, ενώ του Dewey είναι 38 φορές μεγαλύτερος. Τέλος, συγκρίνοντας και τα δυο σχήματα κωδικοποίησης για τις περιπτώσεις για με αλλά και χωρίς συμπίεση, έχουμε παρόμοιους χρόνους εκτέλεσης.
|
Σχήματα Κωδικοποίησης για το Σημασιολογικό Ιστό
