Tractable View-Based Query Rewriting for Knowledge Graphs

Graduate Thesis uoadl:3413042 77 Read counter

Unit:
Department of Informatics and Telecommunications
Πληροφορική
Deposit date:
2024-07-31
Year:
2024
Author:
CHARMANTARIS KONSTANTINOS
Supervisors info:
1) Δρ Κυριακάκος Μιλτιάδης, Εργαστηριακό Διδακτικό Προσωπικό (ΕΔΙΠ), Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
2) Δρ Θεόφιλος Μαΐλης, Ερευνητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Tractable View-Based Query Rewriting for Knowledge Graphs
Languages:
English
Translated title:
Tractable View-Based Query Rewriting for Knowledge Graphs
Summary:
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.
Main subject category:
Science
Keywords:
Knowledge graph, RDF graph, Query rewriting, View selection, Knapsack problem
Index:
No
Number of index pages:
0
Contains images:
Yes
Number of references:
30
Number of pages:
30
Πτυχιακή_Εργασία_Κ_Χαρμαντάρης_1115201900213.pdf (526 KB) Open in new window