Combining Query Translation with Query Answering for Efficient Keyword Search

Keyword search has been regarded as an intuitive paradigm for searching not only documents but also data, especially when the users are not familiar with the data and the query language. Two types of approaches can be distinguished. Answers to keywords can be computed by searching for matching subgraphs directly in the data. The alternative to this is keyword translation, which is based on searching the data schema for matching join graphs, which are then translated to queries. Answering these queries is performed in the later stage. While clear advantages have been shown for the approaches based on query translation, we observe that processing done during query translation has some overlaps with the processing needed for query answering. We propose a tight integration of query translation with query answering. Instead of using the schema, we employ a bisimulation-based structure index graph. Searching this index for matching subgraphs results not only in queries, but also candidate answers. We propose a set of algorithms which allow for an incremental process, where intermediate results computed during query translation can be reused for query answering. In experiments, we show that this integrated approach consistently outperforms the state of the art.