δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Tractable View-Based Query Rewriting for Knowledge Graphs
Σε αυτή την πτυχιακή εργασία, προτείνουμε μια αποδοτική τεχνική για την αναδιατύπωση ερωτημάτων βασισμένη σε όψεις για γραφήματα γνώσης που αναπαρίστανται σε σχεσιακές βάσεις δεδομένων. Συγκεκριμένα, διερευνούμε πώς η αναδιατύπωση ερωτημάτων χρησιμοποιώντας όψεις μπορεί να μειωθεί στο πρόβλημα της Μέγιστης Υποκανονικής Συνάρτησης με Περιορισμό Σακιδίου (knapsack) (πρόβλημα MNssfKc). Δείχνουμε ότι αν χρησιμοποιήσουμε το γραμμικό μοντέλο κόστους για την αξιολόγηση του κόστους εκτέλεσης ενός ερωτήματος, μπορούμε να μειώσουμε το πρόβλημα της αναδιατύπωσης ερωτημάτων χρησιμοποιώντας όψεις στο MNssfKc πρόβλημα. Θα πρέπει να σημειωθεί ότι η συγκεκριμένη μείωση επιτρέπει την επίλυση του MNssfKc και συνεπώς του προβλήματος σε πολυωνυμικό χρόνο σε σχέση με το μέγεθος του ερωτήματος, με προσέγγιση (1 − e^(−1)) της βέλτιστης λύσης.
(EL)
In this work, we propose an efficient technique for view-based query rewriting for knowledge graphs represented in relational databases. Specifically, we investigate how query rewriting using views can be reduced to the problem of Maximizing a Nondecreasing Submodular Set Function Subject to a Knapsack Constraint (MNssfKc problem). We show that if we employ the linear cost model for evaluating the execution cost of a query, we can reduce the problem of query rewriting using views to the MNssfKc problem. It should be noted that the latter reduction allows to solve the MNssfKc and thus the view materialization problem in polynomial time in the size of the query with an (1 − e^(−1)) approximation of the optimal solution.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
