Athens University Economics and Business (AUEB)
Formulation and efficient execution of frequent queries in RDF databases
Abstract
dc:descriptionIn this dissertation we first study issues regarding the formulation of frequent queries using semantic data models. We have conducted an extensive empirical analysis for the domain of cultural heritage which led us to identify a set of frequent/recurrent queries that can be considered as predefined queries for the specific domain. By representing such information in the form of RDF graphs, we identify a set of structural types, further developed as query patterns, that are sufficient to represent all the recorded predefined questions. These query patterns are expressed as Datalog rules and SPARQL queries, the variables of which can represent the various domain concepts. We then focus on the efficient execution of frequent queries in RDF databases. We define the notion of shortcut as a one-step substitute for a path query over RDF data, and we study the problem of selecting the most beneficial shortcuts to materialize given a data graph and a query workload. Materializing shortcuts requires additional space thus giving rise to a trade-off between space consumption and speed of query execution. We formulate the shortcut selection problem under a space constraint, which is reduced to a variation of the knapsack problem, known to be NP-hard. To address this problem we develop a greedy algorithm that incrementally selects the most beneficial shortcut to materialize, based on the per unit space benefit, that does not exceed the remaining budget. We also explore an alternative approach whereby, instead of considering a space constraint, we penalize space consumption by the shortcuts through appropriate cost terms in the objective function. The bi-criterion integer linear optimization problem thus obtained is subsequently relaxed to yield a totally unimodular linear optimization problem. Exploiting this feature, which guarantees integrality of the solutions, we develop an additional algorithm that includes the totally unimodular problem as a subproblem and introduces cuts to cope with violated constraints of the original problem. Two different heuristic methods for generating cuts are explored. The performance of all the proposed algorithms is extensively evaluated through a set of experiments, which demonstrate that shortcut materialization significantly reduces the query execution time, while keeping space requirements low.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Dritsou, Vassiliki
- Ντρίτσου, Βασιλική
Subjects
dc:subject × 14- Διατύπωση ερωτήσεων
- Βάσεις δεδομένων RDF
- Αποδοτική εκτέλεση επερωτήσεων
- Μείωση κόστους επερωτήσεων
- Τύποι επερωτήσεων
- Query formulation
- RDF databases
- Efficient query execution
- Query cost reduction
- Query patterns
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/24751