Back to search

Athens University Economics and Business (AUEB)

Formulation and efficient execution of frequent queries in RDF databases

Abstract

dc:description

In 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/24751

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Dritsou, Vassiliki; Ντρίτσου, Βασιλική. Formulation and efficient execution of frequent queries in RDF databases. Athens University Economics and Business (AUEB), 2011. http://hdl.handle.net/10442/hedi/24751