Keyword pattern graph relaxation for selective result space expansion on linked data

Keyword search is a popular technique for querying the ever growing repositories of RDF graph data. In recent years different approaches leverage a structural summary of the graph data to address the typical keyword search related problems. These approaches compute queries (pattern graphs) corresponding to alternative interpretations of the keyword query and the user selects one that matches her intention to be evaluated against the data. Though promising, these approaches suffer from a drawback: because summaries are approximate representations of the data, they might return empty answers or miss results which are relevant to the user intent. In this paper, we present a novel approach which combines the use of the structural summary and the user feedback with a relaxation technique for pattern graphs. We leverage pattern graph homomorphisms to define relaxed pattern graphs that are able to extract more results potentially of interest to the user. We introduce an operation on pattern graphs and we show that it can produce all relaxed pattern graphs. To guarantee that the result pattern graphs are as close to the initial pattern graph as possible, we devise different metrics to measure the degree of relaxation of a pattern graph.We design an algorithm that computes relaxed pattern graphs with non-empty answers in relaxation order. Finally, we run experiments to measure the effectiveness of our ranking of relaxed pattern graphs and the efficiency of our system.