Querying communities in relational databases

Publication Type:
Conference Proceeding
Proceedings - International Conference on Data Engineering, 2009, pp. 724 - 735
Issue Date:
Filename Description Size
Thumbnail2013002376OK.pdf425.71 kB
Adobe PDF
Full metadata record
Keyword search on relational databases provides users with insights that they can not easily observe using the traditional RDBMS techniques. Here, an l-keyword query is specified by a set of l keywords, {k1, k 2, ⋯ , kl}. It finds how the tuples that contain the keywords are connected in a relational database via the possible foreign key references. Conceptually, it is to find some structural information in a database graph, where nodes are tuples and edges are foreign key references. The existing work studied how to find connected trees for an l-keyword query. However, a tree may only show partial information about how those tuples that contain the keywords are connected. In this paper, we focus on finding communities for an l-keyword query. A community is an induced subgraph that contains all the l-keywords within a given distance. We propose new efficient algorithms to find all/top-k communities which consume small memory, for an l-keyword query. For topk l-keyword queries, our algorithm allows users to interactively enlarge k at run time. We conducted extensive performance studies using two large real datasets to confirm the efficiency of our algorithms. © 2009 IEEE.
Please use this identifier to cite or link to this item: