{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:21:48Z","timestamp":1760170908738},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Keyword search (KWS) over relational databases has recently received significant attention. Many solutions and many prototypes have been developed. This task requires addressing many issues, including robustness, accuracy, reliability, and privacy. An emerging issue, however, appears to be performance related: current KWS systems have unpredictable running times. In particular, for certain queries it takes too long to produce answers, and for others the system may even fail to return (e.g., after exhausting memory). In this paper we argue that as today's users have been \"spoiled\" by the performance of Internet search engines, KWS systems should return whatever answers they can produce quickly and then provide users with options for exploring any portion of the answer space not covered by these answers. Our basic idea is to produce answers that can be generated quickly as in today's KWS systems, then to show users query forms that characterize the unexplored portion of the answer space. Combining KWS systems with forms allows us to bypass the performance problems inherent to KWS without compromising query coverage. We provide a proof of concept for this proposed approach, and discuss the challenges encountered in building this hybrid system. Finally, we present experiments over real-world datasets to demonstrate the feasibility of the proposed solution.<\/jats:p>","DOI":"10.14778\/1920841.1920863","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"140-149","source":"Crossref","is-referenced-by-count":26,"title":["Toward scalable keyword search over relational data"],"prefix":"10.14778","volume":"3","author":[{"given":"Akanksha","family":"Baid","sequence":"first","affiliation":[{"name":"University of Wisconsin, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"Rae","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiexing","family":"Li","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"AnHai","family":"Doan","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Naughton","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB '02","author":"Aditya B.","unstructured":"B. Aditya , G. Bhalotia , S. Chakrabarti , A. Hulgeri , C. Nakhe , P. Parag , and S. Sudarshan . BANKS: browsing and keyword searching in relational databases . In VLDB '02 . B. Aditya, G. Bhalotia, S. Chakrabarti, A. Hulgeri, C. Nakhe, P. Parag, and S. Sudarshan. BANKS: browsing and keyword searching in relational databases. In VLDB '02."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564782"},{"key":"e_1_2_1_3_1","unstructured":"A. Bernstein and E. Kaufmann. Making the semantic web accessible to the casual user: Empirical evidence on the usefulness of semiformal query languages. In TKDE.  A. Bernstein and E. Kaufmann. Making the semantic web accessible to the casual user: Empirical evidence on the usefulness of semiformal query languages. In TKDE ."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559966"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559883"},{"key":"e_1_2_1_6_1","unstructured":"DBLife. http:\/\/dblife.cs.wisc.edu .  DBLife. http:\/\/dblife.cs.wisc.edu ."},{"key":"e_1_2_1_7_1","unstructured":"DBLP. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/ .  DBLP. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/ ."},{"key":"e_1_2_1_8_1","volume-title":"ICDE '07","author":"Ding B.","unstructured":"B. Ding , J. X. Yu , S. Wang , L. Qin , X. Zhang , and X. Lin . Finding top-k min-cost connected trees in databases . In ICDE '07 . B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin. Finding top-k min-cost connected trees in databases. In ICDE '07."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376708"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"V. Hristidis L. Gravano and Y. Papakonstantinou. Efficient IR-style keyword search over relational databases. In VLDB '2003.   V. Hristidis L. Gravano and Y. Papakonstantinou. Efficient IR-style keyword search over relational databases. In VLDB '2003 .","DOI":"10.1016\/B978-012722442-8\/50080-X"},{"key":"e_1_2_1_12_1","volume-title":"VLDB '02","author":"Hristidis V.","unstructured":"V. Hristidis and Y. Papakonstantinou . Discover: keyword search in relational databases . In VLDB '02 . V. Hristidis and Y. Papakonstantinou. Discover: keyword search in relational databases. In VLDB '02."},{"key":"e_1_2_1_13_1","volume-title":"Proc. VLDB Endow., 1(1).","author":"Jayapandian M.","unstructured":"M. Jayapandian and H. V. Jagadish . Automated creation of a forms-based database query interface . Proc. VLDB Endow., 1(1). M. Jayapandian and H. V. Jagadish. Automated creation of a forms-based database query interface. Proc. VLDB Endow., 1(1)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.29"},{"key":"e_1_2_1_15_1","volume-title":"VLDB '05","author":"Kacholia V.","unstructured":"V. Kacholia , S. Pandit , S. Chakrabarti , S. Sudarshan , R. Desai , and H. Karambelkar . Bidirectional expansion for keyword search on graph databases . In VLDB '05 . V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In VLDB '05."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142591"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.64"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516406"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559918"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376706"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.196"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559997"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142536"},{"key":"e_1_2_1_25_1","unstructured":"Lucene. http:\/\/apache.lucene.org .  Lucene. http:\/\/apache.lucene.org ."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247495"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559917"},{"key":"e_1_2_1_29_1","volume-title":"ICDE '07","author":"Sayyadian M.","unstructured":"M. Sayyadian , H. Lekhac , A. Doan , and L. Gravano . Efficient keyword search across heterogeneous relational databases . In ICDE '07 . M. Sayyadian, H. Lekhac, A. Doan, and L. Gravano. Efficient keyword search across heterogeneous relational databases. In ICDE '07."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376705"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:47:17Z","timestamp":1672228037000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920863"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920863","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}