{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T01:29:49Z","timestamp":1791250189619,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T00:00:00Z","timestamp":1451865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>\n            We investigate the problem of learning join queries from user examples. The user is presented with a set of candidate tuples and is asked to label them as\n            <jats:italic>positive<\/jats:italic>\n            or\n            <jats:italic>negative<\/jats:italic>\n            examples, depending on whether or not she would like the tuples as part of the join result. The goal is to quickly infer an arbitrary\n            <jats:italic>n<\/jats:italic>\n            -ary join predicate across an arbitrary number\n            <jats:italic>m<\/jats:italic>\n            of relations while keeping the number of user interactions as minimal as possible. We assume no prior knowledge of the integrity constraints across the involved relations. Inferring the join predicate across multiple relations when the referential constraints are unknown may occur in several applications, such as data integration, reverse engineering of database queries, and schema inference. In such scenarios, the number of tuples involved in the join is typically large. We introduce a set of strategies that let us inspect the search space and aggressively prune what we call\n            <jats:italic>uninformative<\/jats:italic>\n            tuples, and we directly present to the user the\n            <jats:italic>informative<\/jats:italic>\n            ones\u2014that is, those that allow the user to quickly find the goal query she has in mind. In this article, we focus on the inference of joins with equality predicates and also allow disjunctive join predicates and projection in the queries. We precisely characterize the frontier between tractability and intractability for the following problems of interest in these settings: consistency checking, learnability, and deciding the informativeness of a tuple. Next, we propose several strategies for presenting tuples to the user in a given order that allows minimization of the number of interactions. We show the efficiency of our approach through an experimental study on both benchmark and synthetic datasets.\n          <\/jats:p>","DOI":"10.1145\/2818637","type":"journal-article","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T14:04:54Z","timestamp":1452175494000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Learning Join Queries from User Examples"],"prefix":"10.1145","volume":"40","author":[{"given":"Angela","family":"Bonifati","sequence":"first","affiliation":[{"name":"University of Lyon 1, University of Lille 1, Inria LINKS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Radu","family":"Ciucanu","sequence":"additional","affiliation":[{"name":"University of Oxford, University of Lille 1, Inria LINKS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u0142awek","family":"Staworko","sequence":"additional","affiliation":[{"name":"University of Lille 3, Inria LINKS, University of Edinburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465220"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367542"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989338"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402784"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08921-7_60"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1841909.1841911"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the EDBT Conference. 109--120","author":"Bonifati A.","unstructured":"A. Bonifati , R. Ciucanu , and A. Lemay . 2015. Learning path queries on graph databases . In Proceedings of the EDBT Conference. 109--120 . A. Bonifati, R. Ciucanu, and A. Lemay. 2015. Learning path queries on graph databases. In Proceedings of the EDBT Conference. 109--120."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the EDBT Conference. 451--462","author":"Bonifati A.","unstructured":"A. Bonifati , R. Ciucanu , and S. Staworko . 2014a. Interactive inference of join queries . Proceedings of the EDBT Conference. 451--462 . A. Bonifati, R. Ciucanu, and S. Staworko. 2014a. Interactive inference of join queries. Proceedings of the EDBT Conference. 451--462."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733025"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448525"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804683"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.221"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989331"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667055"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247483"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"M. J. Kearns and U. V. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.   M. J. Kearns and U. V. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807122"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047487"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402797"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90055-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213846"},{"key":"e_1_2_1_28_1","volume-title":"Artificial Intelligence: A Modern Approach. Pearson Education.","author":"Russell S. J.","year":"2010","unstructured":"S. J. Russell and P. Norvig . 2010 . Artificial Intelligence: A Modern Approach. Pearson Education. S. J. Russell and P. Norvig. 2010. Artificial Intelligence: A Modern Approach. Pearson Education."},{"key":"e_1_2_1_29_1","volume-title":"Meet Charles, big data query advisor. In Proceedings of the CIDR Conference. 1--6.","author":"Sellam T.","unstructured":"T. Sellam and M. L. Kersten . 2013 . Meet Charles, big data query advisor. In Proceedings of the CIDR Conference. 1--6. T. Sellam and M. L. Kersten. 2013. Meet Charles, big data query advisor. In Proceedings of the CIDR Conference. 1--6."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274592"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2539032.2539035"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559902"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28692"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465280"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448954"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465320"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1499949.1500034"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818637","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:49Z","timestamp":1750225369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,4]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2818637"],"URL":"https:\/\/doi.org\/10.1145\/2818637","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,4]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}