1. Home page
  2. Search

Tractable View-Based Query Rewriting for Knowledge Graphs

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Tractable View-Based Query Rewriting for Knowledge Graphs
ΧΑΡΜΑΝΤΑΡΗΣ ΚΩΝΣΤΑΝΤΙΝΟΣ (EL)
CHARMANTARIS KONSTANTINOS (EN)
born_digital_graduate_thesis
Πτυχιακή Εργασία (EL)
Graduate Thesis (EN)
2024
Σε αυτή την πτυχιακή εργασία, προτείνουμε μια αποδοτική τεχνική για την αναδιατύπωση ερωτημάτων βασισμένη σε όψεις για γραφήματα γνώσης που αναπαρίστανται σε σχεσιακές βάσεις δεδομένων. Συγκεκριμένα, διερευνούμε πώς η αναδιατύπωση ερωτημάτων χρησιμοποιώντας όψεις μπορεί να μειωθεί στο πρόβλημα της Μέγιστης Υποκανονικής Συνάρτησης με Περιορισμό Σακιδίου (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)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών » Πληροφορική
Σχολή Θετικών Επιστημών » Τμήμα Πληροφορικής & Τηλεπικοινωνιών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Graduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)