Efficient and Effective Aggregate Keyword Search on Relational Databases

Introduction

More and more relational databases contain textual data and thus keyword search on relational databases becomes popular. Aggregate keyword search (Zhou & Pei, 2009) was recently proposed on relational databases: given a set of keywords, find a set of aggregates such that each aggregate is a group-by covering all query keywords.

Aggregate keyword search on relational databases has attracted a lot of attention (Chen, Wang, & Liu, 2011; Ding, Yu, Zhao, Lin, Han, & Zhai, 2010; Ding, Zhao, Lin, Han, & Zhai, 2010; Draper & Smith, 1981; Koren, Zhang, & Liu, 2008; Li, Xu, Lu, & Qian, 2010; Zhou & Pei, 2009). A few critical challenges have been identified, such as how to develop efficient approaches for finding all minimal group-bys (Zhou & Pei, 2009) or top-k relevant cells (Ding, et al., 2010) to a user given keyword query. To motivate, we revisit the example in Zhou and Pei (2009).

• Example 1 (Motivation) (Zhou & Pei, 2009):Table 1shows a database of tourism event calendar. Such an event calendar is popular in many tourism web sites and travel agents’ databases (or data warehouses). To keep our discussion simple, in the field of description, a set of keywords are extracted. In general, this field can store text description of events.