| Περίληψη |
Ο Σημασιολογικός Ιστός (ΣΙ) είναι μια εξελισσόμενη επέκταση του Παγκόσμιου
Ιστού στην οποία το περιεχόμενο μπορεί να εκφραστεί όχι μόνο με φυσική γλώσσα
αλλά και με τυπικές γλώσσες (π.χ. RDF/S ), που επιτρέπουν την παροχή προηγ-
μένων υπηρεσιών αναζήτησης, διαμοιρασμού και ολοκλήρωσης πληροφορίας. Η ρήση
του Ηράκλειτου «τα πάντα ρει» ισχύει και στον ΣΙ, αφού οι πόροι (resources), οι οντο-
λογίες, τα μεταδεδομένα διαρκώς αλλάζουν και εξελίσσονται. Εκ τούτου η ικανότητα
υπολογισμού των διαφορών μεταξύ δύο Βάσεων Γνώσεων (ΒΓ) RDF/S , στο εξής
Δέλτα, είναι πολύ σημαντική. Συγκεκριμένα, τα Δέλτα μπορούν (α) να βοηθήσουν
τους χρήστες στην κατανόηση της εξέλιξης της γνώσης, και (β) να μειώσουν τον
όγκο των δεδομένων που χρειάζεται να ανταλλαχθούν και διαχειριστούν στο δίκτυο
για την ανάπτυξη υπηρεσιών συγχρονισμού, διαχείρισης εκδόσεων και αντιγράφων.
Το πρόβλημα της σύγκρισης δεν είναι απλό διότι η RDF υποστηρίζει ανώνυμους
κόμβους. ΄Ενας ανώνυμος κόμβος είναι ένας κόμβος σε ένα ΡΔΦ γράφο, ο οποίος
δεν είναι ούτε URI, ούτε literal και επομένως δεν έχει εξωτερική ταυτότητα. Αρκετές
βάσεις γνώσεων περιλαμβάνουν μεγάλο ποσοστό ανώνυμων κόμβων (π.χ. το 7.5%
των Διασυνδεδεμένων Δεδομένων εκτιμάται ότι αντιστοιχεί σε ανώνυμους κόμβους),
καθώς είναι κατάλληλοι για την αναπαράσταση σύνθετων γνωρισμάτων ή κόμβων των
οποίων η ταυτότητα είναι άγνωστη, αλλά οι ιδιότητες τους (είτε literals ή συνδέσεις
τους με άλλους κόμβους) είναι γνωστές. Η θεώρηση των ανώνυμων κόμβων σαν
μοναδικές σταθερές στους δύο γράφους δε βοηθάει ούτε στον εντοπισμό ισοδύναμων
γράφων, ούτε στη μείωση του Δέλτα. Αντιθέτως, με την αντιστοίχιση των ανώνυμων
κόμβων του ενός γράφου με τους ανώνυμους κόμβους του άλλου γράφου μπορούμε να
μειώσουμε σημαντικά το παραγόμενο Δέλτα. Η παρούσα εργασία είναι η πρώτη εργα-
σία που εστιάζει σε μεθόδους αντιστοίχισης των ανώνυμων κόμβων προσεγγίζοντας
το πρόβλημα ως πρόβλημα βελτιστοποίησης με στόχο την εύρεση της αντιστοίχι-
σης που οδηγεί στο ελάχιστο σε μέγεθος Δέλτα (ελάχιστο πλήθος τριπλετών που
πρέπει να διαγραφούν και να προστεθούν για να γίνουν οι δύο γράφοι ισοδύναμοι).
Αποδεικνύουμε ότι η εύρεση της βέλτιστης αντιστοίχισης είναι NP-Hard στη γενική
περίπτωση ανάγοντας το πρόβλημα της αντιστοίχισης στο πρόβλημα του ισομορφισμού
υπογράφων. Επιπλέον αποδυκνείουμε ότι όταν οι γράφοι δεν περιέχουν ανώνυμους
κόμβους που συνδέονται άμεσα μεταξύ τους (ήτοι, καμία τριπλέτα δεν περιέχει πε-
ρισσότερους από έναν ανώνυμους κόμβους), τότε ο πολυωνυμικής πολυπλοκότητας
Ουγγρικός αλγόριθμος μπορεί να δώσει τη βέλτιστη λύση. Για τη γενική περίπτωση
προτείνουμε διάφορους πολυωνυμικούς αλγορίθμους, που μπορούν να λύσουν το πρό-
βλημα προσεγγιστικά. Για να είναι εφικτή η εφαρμογή των μεθόδων μας ακόμα και
σε πολύ μεγάλες βάσεις γνώσεων, που περιέχουν μεγάλο πλήθος ανώνυμων κόμβων,
δίνουμε έναν προσεγγιστικό αλγόριθμο με NlogN πολυπλοκότητα ο οποίος βασίζεται
σε υπογραφές. Τέλος, για τους προτεινόμενους αλγόριθμους, αναφέρουμε εκτεταμέ-
να συγκριτικά πειραματικά αποτελέσματα επί πραγματικών και συνθετικά παραγμένων
ΒΓ, σχετικά με τις επιδόσεις τους στη μείωση του Δέλτα (και την απόκλιση τους
από το βέλτιστο), στον εντοπισμό ισοδύναμων γράφων, και τις υπολογιστικές τους
7
απαιτήσεις. Τα αποτελέσματα είναι πολύ ενδιαφέροντα. Ενδεικτικά, ο αλγόριθμος
που βασίζεται σε υπογραφές μπορεί να αντιστοιχίσει βάσεις που έχουν μέχρι και 150
χιλιάδες ανώνυμους κόμβους σε λίγα δευτερόλεπτα και U% απόκλιση από το βέλτιστο.
|
On Computing Deltas of RDF/S Knowledge Bases with Blank Nodes
