Incomplete information in RDF databases with an emphasis on the geospatial domain

Abstract

Incomplete information has been studied in-depth in relational databases and knowledge representation, but not much has been done in semantic web frameworks such as RDF. In this Thesis we propose an extension of RDF, called RDFi, for the representation and querying of incomplete information for property values. The RDFi framework is parameterized with a constraint language and serves for expressing partial knowledge about property values through the formulation of constraints. We give the syntax and formal semantics of RDFi and extend the compositional semantics of SPARQL to capture the new elements introduced in RDFi for the capturing of incomplete information. We show two fragments of SPARQL that can be used to evaluate queries over RDFi in a semantically correct way and only with respect to a subset of their answers corresponding to the so-called certain answers. Our work around RDFi completes by giving an algorithm for the computation of certain answers and studying the data complexity of the associated decision problem named certainty. The rest of our work is more practical. Motivated by the rapid increase in the size of linked geospatial data published on the web, we give a strong emphasis on the geospatial domain. We point out that the recent OGC standard GeoSPARQL for the querying of geospatial information provides a rich language, but at the same time it covers a number of weaknesses pertaining to the handling of incomplete information that leading to incomplete answers. In this context, we demonstrate the expressivity of the RDFi framework showing that it can be employed to give semantics to GeoSPARQL. We continue by discussing possible ways through which these problems can be amended using constraint propagation techniques developed in the area of qualitative spatial reasoning and then presenting an implementation as an extension to the system Strabon as well as a corresponding evaluation using linked geospatial datasets. Prompted by the negative results of this evaluation we then study how consistency checking of very large real-world networks, such as the linked geospatial datasets, can be done efficiently.

Η διαχείριση μη πλήρους πληροφορίας έχει μελετηθεί σε βάθος στις σχεσιακές βάσεις δεδομένων και στην αναπαράσταση γνώσης, αλλά στην περιοχή του σημασιολογικού ιστού και στα σχετικά με αυτή μοντέλα αναπαράστασης γνώσης, όπως το RDF, δεν έχει μελετηθεί αρκετά. Σε αυτή τη διατριβή προτείνουμε μία επέκταση του μοντέλου RDF που λέγεται RDFi για την αναπαράσταση μη πλήρους πληροφορίας για τιμές ιδιοτήτων και την αποτίμηση ερωτημάτων εκφρασμένων στη γλώσσα SPARQL. Το πλαίσιο RDFi παραμετροποιείται με μία γλώσσα περιορισμών που εξυπηρετεί την έκφραση μερικής γνώσης για τιμές ιδιοτήτων μέσω του σχηματισμού κατάλληλων περιορισμών. Δίνουμε το συντακτικό, ορίζουμε τη σημασιολογία του RDFi με τυπικό τρόπο βασιζόμενοι στην σημασιολογία πιθανών κόσμων, και επεκτείνουμε τους τελεστές της SPARQL έτσι ώστε να συλλάβουμε τα νέα στοιχεία που έχουν εισαχθεί στο RDFi για την αναπαράσταση μη πλήρους πληροφορίας. Μελετάμε την ορθότητα της επέκτασης αυτής και αποδεικνύουμε ότι υπάρχουν δύο υποκλάσεις της SPARQL που θα μπορούσαν να οδηγήσουν στην ορθή αποτίμηση ερωτημάτων πάνω από το RDFi βάσει της ορισθείσας σημασιολογίας, αλλά μόνο αν οι απαντήσεις περιοριστούν στις επονομαζόμενες βέβαιες απαντήσεις. Η εργασία μας γύρω από το πλαίσιο RDFi ολοκληρώνεται παρουσιάζοντας έναν αλγόριθμο για τον υπολογισμό των βέβαιων απαντήσεων ενός ερωτήματος SPARQL και τη μελέτη της πολυπλοκότητας δεδομένων του σχετικού με αυτό προβλήματος απόφασης και έναν αριθμό από γλώσσες περιορισμών που μπορούν να χρησιμοποιηθούν για να εκφράσουν μη πλήρη πληροφορία για χρονικά, χωρικά, γεωχωρικά, και άλλα δεδομένα. Το υπόλοιπο της εργασίας μας είναι πιο πρακτικό. Παρακινούμενοι από την ραγδαία αύξηση του μεγέθους των διασυνδεδεμένων γεωχωρικών δεδομένων που έχουν δημοσιευθεί τελευταία στον ιστό, δίνουμε βαρύτητα στο γεωχωρικό πεδίο. Επισημαίνουμε ότι το πρόσφατο πρότυπο GeoSPARQL που προτάθηκε από την κοινοπραξία για τα γεωχωρικά δεδομένα OGC για την αποτίμηση ερωτημάτων πάνω από γεωχωρικά δεδομένα εκφρασμένα στο RDF ενώ παρέχει μία πλούσια γλώσσα, την ίδια στιγμή φέρει έναν αριθμό αδυναμιών όσον αφορά στη διαχείριση μη πλήρους πληροφορίας, οι οποίες οδηγούν σε ημιτελές απαντήσεις. Υπό αυτό το πρίσμα, επιδεικνύουμε την εκφραστικότητα του πλαισίου RDFi δείχνοντας ότι θα μπορούσε να χρησιμοποιηθεί ώστε να ορίσει τη σημασιολογία της GeoSPARQL με τυπικό τρόπο καθώς επίσης και να επιλύσει ορισμένες από τις αδυναμίες της. Συνεχίζουμε με τη συζήτηση διάφορων τρόπων μέσω των οποίων τα προβλήματα που προκύπτουν από αυτές τις αδυναμίες θα μπορούσαν να διορθωθούν και προτείνουμε ως καταλληλότερη λύση τη χρήση τεχνικών από την ερευνητική περιοχή του ποιοτικού χωρικού συμπερασμού που βασίζονται σε αλγορίθμους διάδοσης περιορισμών. Παρουσιάζουμε την υλοποίηση μίας τέτοιας επέκτασης στη γεωχωρική RDF βάση δεδομένων Strabon καθώς επίσης και την αξιολόγησή της χρησιμοποιώντας διασυνδεδεμένα χωρικά σύνολα δεδομένων. Παρακινούμενοι από τα αρνητικά αποτελέσματα της αξιολόγησης μελετάμε και υλοποιούμε αλγορίθμους για τον έλεγχο συνέπειας και τη διάδοση περιορισμών σε πολύ μεγάλα και πραγματικά δίκτυα περιορισμών, όπως τα διασυνδεδεμένα γεωχωρικά σύνολα δεδομένων, και δείχνουμε ότι μπορούν να οδηγήσουν σε αποδοτικές υλοποιήσεις.