{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T03:23:46Z","timestamp":1790133826910,"version":"4.0.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,9,30]],"date-time":"2018-09-30T00:00:00Z","timestamp":1538265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DEFT","award":["FA8750-13-2-0039"],"award-info":[{"award-number":["FA8750-13-2-0039"]}]},{"name":"MEMEX and SIMPLEX"},{"name":"DARPA's projects XDATA","award":["FA8750-12-2-0335"],"award-info":[{"award-number":["FA8750-12-2-0335"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>In the design of analytical procedures and machine learning solutions, a critical and time-consuming task is that of feature engineering, for which various recipes and tooling approaches have been developed. In this article, we embark on the establishment of database foundations for feature engineering. We propose a formal framework for classification in the context of a relational database. The goal of this framework is to open the way to research and techniques to assist developers with the task of feature engineering by utilizing the database\u2019s modeling and understanding of data and queries and by deploying the well-studied principles of database management. As a first step, we demonstrate the usefulness of this framework by formally defining three key algorithmic challenges. The first challenge is that of separability, which is the problem of determining the existence of feature queries that agree with the training examples. The second is that of evaluating the VC dimension of the model class with respect to a given sequence of feature queries. The third challenge is identifiability, which is the task of testing for a property of independence among features that are represented as database queries. We give preliminary results on these challenges for the case where features are defined by means of conjunctive queries, and, in particular, we study the implication of various traditional syntactic restrictions on the inherent computational complexity.<\/jats:p>","DOI":"10.1145\/3268931","type":"journal-article","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T12:11:00Z","timestamp":1540901460000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Relational Framework for Classifier Engineering"],"prefix":"10.1145","volume":"43","author":[{"given":"Benny","family":"Kimelfeld","sequence":"first","affiliation":[{"name":"Technion -- Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"R\u00e9","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,10,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Varun Aggarwal and Sassoon Kosian. 2011. Feature Selection and Dimension Reduction Techniques in SAS.  Varun Aggarwal and Sassoon Kosian. 2011. Feature Selection and Dimension Reduction Techniques in SAS."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185366"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Sixth Biennial Conference on Innovative Data Systems Research. http:\/\/web.eecs.umich.edu\/ michjc\/papers\/mythical_man.pdf.","author":"Anderson Michael","year":"2013"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733054"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022642604085"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-8261-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00003-3"},{"key":"e_1_2_1_8_1","article-title":"Hinge-loss markov random fields and probabilistic soft logic","volume":"18","author":"Bach Stephen H.","year":"2017","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_2_1_10_1","first-page":"463","article-title":"Rademacher and Gaussian complexities: Risk bounds and structural results","volume":"3","author":"Bartlett Peter L.","year":"2002","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_11_1","volume-title":"Intelligent Systems Reference Library","volume":"49","author":"Bengio Yoshua"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"David E. Boyce. 1974. Optimal Subset Selection: Multiple Regression Interdependence and Optimal Network Algorithms. Springer-Verlag.   David E. Boyce. 1974. Optimal Subset Selection: Multiple Regression Interdependence and Optimal Network Algorithms. Springer-Verlag.","DOI":"10.1007\/978-3-642-46311-2_3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2890492"},{"key":"e_1_2_1_18_1","unstructured":"George Dantzig. 1998. Linear Programming and Extensions. Princeton University Press.  George Dantzig. 1998. Linear Programming and Extensions. Princeton University Press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2463665"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI\u201999)","author":"Friedman Nir","year":"1999"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2074094.2074112"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944968"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Isabelle Guyon Steve Gunn Masoud Nikravesh and Lotfi A. Zadeh. 2006. Feature Extraction: Foundations and Applications (Studies in Fuzziness and Soft Computing). Springer-Verlag New York Inc. Secaucus NJ USA.   Isabelle Guyon Steve Gunn Masoud Nikravesh and Lotfi A. Zadeh. 2006. Feature Extraction: Foundations and Applications (Studies in Fuzziness and Soft Computing). Springer-Verlag New York Inc. Secaucus NJ USA.","DOI":"10.1007\/978-3-540-35488-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Trevor Hastie Robert Tibshirani and Jerome Friedman. 2001. The Elements of Statistical Learning: Data Mining Inference and Prediction. Springer.  Trevor Hastie Robert Tibshirani and Jerome Friedman. 2001. The Elements of Statistical Learning: Data Mining Inference and Prediction. Springer.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"e_1_2_1_29_1","volume-title":"Machine Learning: Proceedings of the Eleventh International Conference. Morgan Kaufmann, 121--129","author":"John George H.","year":"1994"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.219"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629550"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034797"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Yann LeCun Yoshua Bengio and Geoffrey Hinton. 2015. Deep learning. Nature 521 7553 (2015) 436--444.  Yann LeCun Yoshua Bengio and Geoffrey Hinton. 2015. Deep learning. Nature 521 7553 (2015) 436--444.","DOI":"10.1038\/nature14539"},{"key":"e_1_2_1_34_1","unstructured":"Erich Leo Lehmann and George Casella. 1998. Theory of Point Estimation. Vol. 31. Springer.  Erich Leo Lehmann and George Casella. 1998. Theory of Point Estimation. Vol. 31. Springer."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI\u201997)","author":"Milch Brian","year":"2005"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI\u201997)","volume":"2","author":"Sato Taisuke","year":"1997"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.   Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809991"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/72.788640"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.5.851"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90274-0"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases","author":"Yannakakis Mihalis","year":"1981"},{"key":"e_1_2_1_47_1","volume-title":"ICML (JMLR Proceedings)","volume":"28","author":"Zemel Richard S.","year":"2013"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877204"},{"key":"e_1_2_1_49_1","unstructured":"Indre Zliobaite. 2015. A survey on measuring indirect discrimination in machine learning. CoRR abs\/1511.00148 (2015).  Indre Zliobaite. 2015. A survey on measuring indirect discrimination in machine learning. CoRR abs\/1511.00148 (2015)."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3268931","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3268931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:19Z","timestamp":1750212439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3268931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,30]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3268931"],"URL":"https:\/\/doi.org\/10.1145\/3268931","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,30]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}