Match-Based Candidate Network Generation for Keyword Queries over Relational Databases

Several systems for processing keyword queries over relational databases rely on the generation and evaluation of Candidate Networks (CNs), i.e., networks of joined relations that when processed as SQL queries, provide a relevant answer to the input keyword query. Although the evaluation of CNs has been extensively addressed in the literature, the problem of generating CNs has received much less attention. We propose a novel approach for generating CNs, wherein the possible matches for the query in the database are efficiently enumerated at first. These query matches are then used to guide the CN generation process, avoiding the exhaustive search procedure used by the current state-of-art approaches. We experimentally show that our approach allows the generation of a compact set of CNs that results in superior quality answers and demands less resources in terms of processing time and memory.