Querying Communities in Relational Databases

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
Proceedings of the 25th International Conference on Data Engineering, 2009, pp. 724 - 735
Issue Date:
2009-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002376OK.pdf425.71 kB
Adobe PDF
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, k2, middot middot middot , 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 top k 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
Please use this identifier to cite or link to this item: