Semantics-driven Approximate Query Answering on Graph Databases

Several database application areas need to deal with graph-modeled datasets. The main features of these datasets are the largeness and the heterogeneity of the data, which make it impractical to answer exact queries. In this paper we present our recent research efforts in modeling flexible query answering capabilities in this context. Flexibility is captured by approximations both on the labels and on the structure of graph-based queries, by guaranteeing semantically meaningful relaxations only. In order to cope with the excess of results, we adapt a well-known top-k retrieval algorithm to our context. The good effectiveness and efficiency of our proposal are proved by an extensive experimental evaluation on different real world datasets.