| Abstract : | Η επιστήμη της πληροφορικής έχει ολοένα και περισσότερο τον ρόλο να αντιμετωπίζει δεδομένα με αβεβαιότητα. Data integration, δίκτυα αισθητήρων, παρακολούθηση κινούμενων αντικειμένων και αναζήτηση στον παγκόσμιο ιστό είναι οι κυριότερες αιτίες που το προκαλούν αυτό. Η αβεβαιότητα εντοπίζεται με δύο μορφές: είτε με την ύπαρξη μιας εγγραφής βάση μιας πιθανότητας είτε με την μη μονοσήμαντη τιμή σε ένα γνώρισμα. Μια εύκολη λύση θα ήταν η εξαίρεση των αβέβαιων εγγραφών αλλά μπορεί έτσι να εξαιρεθούν πολλές εγγραφές εκ των οποίων πολλές μπορούν να συνεισφέρουν πάρα πολύ στην αποτίμηση ενός ερωτήματος. Επομένως η «εξυγίανση» των δεδομένων είναι η λύση που δεν αντιμετωπίζει το πρόβλημα αλλά το αποφεύγει. Είναι λογικό ότι οι υπάρχουσες σχεσιακές βάσεις δεδομένων δε μπορούν να διαχειριστούν την αβεβαιότητα καθόσον προϋποθέτουν ντετερμινισμό. Όμως μια ενδεχόμενη λύση δε θα πρέπει να είναι και μακριά από αυτές και μάλιστα να τηρεί και τους βασικούς κανόνες τους. Μέχρι στιγμής δεν υπάρχει εμπορικό RDBMS που να διαχειρίζεται την αβεβαιότητα αλλά όλες οι μελέτες έχουν κατασταλάξει σε ένα κοινό πλαίσιο αναφοράς και προδιαγραφές που αυτό θα πρέπει να εκπληρώνει.Ένας πρώτος τρόπος διαχείρισης της αβεβαιότητας στις εγγραφές είναι η προσπάθεια αποτύπωσης όλων των δυνατών περιπτώσεων στις οποίες ισχύουν οι κανόνες των κλασσικών Β.Δ. και που η κάθε μια περίπτωση ισχύει βάση μιας πιθανότητας. Αυτά τα δυνατά στιγμιότυπα του κόσμου που μοντελοποιείται ονομάζονται πιθανοί κόσμοι στους οποίους οι εγγραφές αντιμετωπίζονται ως ενδεχόμενα με αβεβαιότητα και οι πιθανοί κόσμοι ως γεγονότα εγγραφών. Ένα ερώτημα για να υπολογιστεί υπολογίζεται σε κάθε πιθανό κόσμο και για το τελικό αποτέλεσμα συνυπολογίζονται τα ενδιάμεσα αποτελέσματα. Ωστόσο αυτή η λύση απαιτεί πολύ χώρο και έχει περισσότερο θεωρητική σκοπιμότητα.Στη συνέχεια αναλύεται το μοντέλο των δεδομένων και τους διάφορους τρόπους που προτάθηκαν για την έκφραση της αβεβαιότητας. Επίσης αναφέρονται τα μοντέλα της αβεβαιότητας τα οποία είναι: το επεκταμένο σχεσιακό μοντέλο το οποίο διαχειρίζεται την αβεβαιότητα σε γνώρισμα που η τιμή του είναι γνωστό ότι βρίσκεται ανάμεσα σε ένα διάστημα, το μοντέλο των διπλοεγγραφών στο οποίο κάθε εγγραφή περιέχεται με όλες τις δυνατές της εκφάνσεις. Αυτό εγκυμονεί κινδύνους και γι’ αυτό προτείνεται και μια βελτίωση του με τη χρήση της καταγωγής της κάθε εγγραφής. Το τελευταίο μοντέλο προτείνει ένα τρόπο για την κανονικοποίηση της αβεβαιότητας με την δημιουργία επιπλέον πινάκων.Όσον αφορά την σημασιολογία των επερωτήσεων επέρχονται αλλαγές από την κλασσική έννοια. Η πιθανότητα θα πρέπει να λαμβάνεται σαν αποτέλεσμα και κατά συνέπεια σαν κριτήριο του ερωτήματος. Σε συστήματα που διαχειρίζονται γενετικές πληροφορίες προτάθηκε μια υπερφόρτωση του υπάρχοντος τελεστή ‘LIKE’. Επίσης σε περιπτώσεις που ένα γνώρισμα αποτελείται από μια «αναλογία» συστατικών προτάθηκε μία μέθοδος βαθμολόγησης (πιθανότητας ταύτισης) μιας τιμής γνωρίσματος προς αναγνώριση με αυτές που περιέχονται στη βάση δεδομένων.Στη συνέχεια ορίζονται κάποια ερωτήματα που μπορούν να απαντηθούν με τη χρήση των πιθανών κόσμων. Οι k εγγραφές που έχουν το μεγαλύτερο άθροισμα πιθανότητας στους κόσμους που τις περιέχουν είναι οι απάντηση σε ένα U-Topk ερώτημα. Στις περιπτώσεις που οι κόσμοι περιέχουν τις εγγραφές τους σε φθίνουσα ταξινόμηση τότε η εγγραφή με την μεγαλύτερη πιθανότητα είναι το αποτέλεσμα στο ερώτημα U-1Rank, με τις δύο μεγαλύτερες στο U-2Rank κ.α. Οι k εγγραφές με το μεγαλύτερο άθροισμα που περιέχονται στο Top-k του κάθε κόσμου είναι το αποτέλεσμα του ερωτήματος PT-k. Οι παραπάνω ορισμοί βαθμολογούν τις εγγραφές με βάση την πιθανότητά τους χωρίς να λαμβάνεται υπόψη η βαθμολόγηση της ίδια της εγγραφής. Αυτό προσπαθεί να επιλύσει το c-Typical-Topk ερώτημα που το αποτέλεσμα του περιέχει εγγραφές τις οποίες βαθμολογεί ανάλογα με το score και την πιθανότητα τους.Επεκτείνοντας το προηγούμενο ερώτημα, μία άλλη ενδιαφέρουσα κατηγορία είναι αυτής με εγγραφές με αβέβαιη βαθμολογία. Σε αυτή την περίπτωση προτείνεται ένας τρόπος διάταξης τους με τη δημιουργία των γραμμικών επεκτάσεων κατ’ αναλογία με τους πιθανούς κόσμους. Σ’ αυτές ορίζονται άλλη μία γκάμα χρήσιμων ερωτημάτων.Ακόμη εξετάζεται αναλυτικά η περίπτωση ερωτημάτων σε αντικείμενα των οποίων τα στιγμιότυπα έχουν μια πιθανότητα εμφάνισης. Ορίζεται πότε ένα στιγμιότυπο «επικρατεί» σε ένα άλλο με βάση ένα τρίτο στιγμιότυπο αναφοράς και υπολογίζεται η πιθανότητα ένα αντικείμενο να «επικρατεί» σε ένα άλλο. Το ερώτημα που ορίζεται εδώ είναι τα k αντικείμενα που έχουν την μεγαλύτερη βαθμολογία στην επικράτηση.Έχοντας κάνει μια γενική αναφορά στα ερωτήματα με αβεβαιότητα ορίζεται πλέον από την παρούσα αναφορά το join σε αντικείμενα στα οποία μπορεί να οριστεί μια σχέση διάταξης και απόστασης μεταξύ τους. Στη συνέχεια το πρόβλημα μοντελοποιείται και επιλύεται με διάφορους τρόπους ενώ αυτοί συγκρίνονται μεταξύ τους. Ακόμη ο βέλτιστος τρόπος δοκιμάζεται πως συμπεριφέρεται με ποιοτικές και ποσοτικές αλλαγές στα δεδομένα.Επιπρόσθετα, εξετάστηκε το join σε αντικείμενα που περιέχουν γνώρισμα με εύρος. Και εδώ το πρόβλημα ορίστηκε και επιλύθηκε με διάφορους τρόπους και δοκιμάστηκε η συμπεριφορά του προγράμματος στις αλλαγές στα δεδομένα.Η παρούσα εργασία κλείνει με την αναφορά σε join πινάκων με γνωρίσματα με εύρος στην οποία δεν είναι κριτήριο η αυστηρή επικάλυψη, αλλά η ευρύτερη επικάλυψη με επέκταση βάση μιας παραμέτρου c. Σε αυτήν την περίπτωση υπολογίζεται η πιθανότητα του join, όπως επίσης και άλλων τελεστών ( >).
The computer science has increasingly the role to deal with data uncertainty. Data integration, sensor networks, tracking moving objects and web search are the main reasons that cause this. The uncertainty lies in two forms: either the existence of a record based on a probability or a non-uniquely value to a property. An easy solution would be to remove records of uncertain but in this case records which can contribute very much to a valuation question might be excluded. Therefore, the "consolidation" of the data is the solution does not address the problem but avoids it. The existing relational databases can not handle the uncertainty as it presupposes determinism. However, any solution should not be and away from them but it should also keep the basic rules. Up to now there is no commercial RDBMS to manage the uncertainty, but all studies have settled on a common frame of reference and specifications that should be met.A first approach to the management of uncertainty in the records is an effort capture all possible cases in which the rules of classic D.B. are valid and each case is valid on a based probability.These powerful snapshots of the world modeled called possible worlds in which records are treated as contingent on uncertainty and possible worlds as events records. To calculate a query, it is estimated at every possible world and for the final result interimediate results are included. However, this solution requires too much space and is more theoretical considerations. Then we analyze the model data and the various methods proposed for the expression of uncertainty. Also we have the following models of uncertainty which are: the extended relational model that manages the uncertainty in the attribute value is known as being between one time, the model of double entries in which each record contains all the possible manifestations. This poses a risk and therefore proposed a better use of the origin of each record. The latter model suggests a way for the dis-join the uncertainty in the creation of additional tables.Regarding the semantics of queries there are differences from the classical sense. The probability should be taken as a result and therefore as a criterion to the query. In systems that manage genetic data an overload of the existing operator 'LIKE' was suggested. Also in cases where a property is a 'proportion' of components a scoring method (probability of identity) of a property value to be recognized as those contained in the database was proposed.Next some questions were set to be answered with the use of possible worlds.The k records that have the largest sum probability in worlds which containing them is the answer to a U-Topk query. In cases Where worlds contain the records in descending order, then the record with the largest probability is the result of the query U-1Rank, with the two largest is the result in the U-2Rank etc. The k records with the largest sum given to the Top-k of each world is the result of the ruling PT-k.These definitions rate the records based on their probability without taking into account the rating of the same recording.This tries to solve the c-Typical-Topk query where the result contains the records which are rated according to the score and the probability of them.Extending the previous question, another interesting matter is that with the records of uncertain rate. In this case a way to provision through the creation of linear extensions along the lines of possible worlds is suggested. In the last one, other relevant queries are defined.Also we consider in detail a case of queries to objects which their instances have a probability accurance. We define when an instance is preferable to another based on a third instance reference and calculate the probability of an object to "prevail" in another. The query which is referred here is the k objects that have the highest score in prevalence.Having made a general reference to these queries, uncertainty is now defined in this report to join the objects which may define a connection device and the distance between them. Then the problem is modelled and solved in different ways which are compared with each other. Even the best way is tested on how it behaves with qualitative and quantitative changes in the data.Additionally, "join" to objects which include properties to a range was tested. Here the problem was defined and resolved with several ways and the behaviour of the program was tested on data changes.This paper concludes with a reference to a join table for traits with a range in which there is a strict criterion overlapping, but the larger overlap with an extension on a parameter c. In this case the join's probability is calculated, as well as other operators ( >).
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.