{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:21Z","timestamp":1753894401480,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this paper, we study the problem of optimizing a linear program whose\nvariables are the answers to a conjunctive query. For this we propose the\nlanguage LP(CQ) for specifying linear programs whose constraints and objective\nfunctions depend on the answer sets of conjunctive queries. We contribute an\nefficient algorithm for solving programs in a fragment of LP(CQ). The natural\napproach constructs a linear program having as many variables as there are\nelements in the answer set of the queries. Our approach constructs a linear\nprogram having the same optimal value but fewer variables. This is done by\nexploiting the structure of the conjunctive queries using generalized hypertree\ndecompositions of small width to factorize elements of the answer set together.\nWe illustrate the various applications of LP(CQ) programs on three examples:\noptimizing deliveries of resources, minimizing noise for differential privacy,\nand computing the s-measure of patterns in graphs as needed for data mining.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:9)2024","type":"journal-article","created":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T10:43:02Z","timestamp":1707475382000},"source":"Crossref","is-referenced-by-count":1,"title":["Linear Programs with Conjunctive Database Queries"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Florent","family":"Capelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Crosetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Niehren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Ramon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,1,26]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12949\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12949\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T10:43:04Z","timestamp":1707475384000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,26]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:9)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2210.16694v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2210.16694v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2210.16694","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2210.16694","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,1,26]]},"article-number":"10232"}}