Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
CHARMANTARIS KONSTANTINOS
Supervisors info:
1) Δρ Κυριακάκος Μιλτιάδης, Εργαστηριακό Διδακτικό Προσωπικό (ΕΔΙΠ), Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
2) Δρ Θεόφιλος Μαΐλης, Ερευνητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Tractable View-Based Query Rewriting for Knowledge Graphs
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