In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the answer sets of conjunctive queries. We contribute an efficient algorithm for solving programs in a fragment of LP(CQ). The natural approach constructs a linear program having as many variables as there are elements in the answer set of the queries. Our approach constructs a linear program having the same optimal value but fewer variables. This is done by exploiting the structure of the conjunctive queries using generalized hypertree decompositions of small width to factorize elements of the answer set together. We illustrate the various applications of LP(CQ) programs on three examples: optimizing deliveries of resources, minimizing noise for differential privacy, and computing the s-measure of patterns in graphs as needed for data mining.
翻译:在本文中, 我们研究优化线性程序的问题, 其变量是组合查询的答案。 为此, 我们建议使用语言 LP( CQ) 来指定线性程序, 其限制和客观功能取决于对组合查询的回答组。 我们为在 LP( CQ) 的碎片中解决程序贡献了高效的算法。 自然方法构建了一个线性程序, 其变量与回答组的元素一样多。 我们的方法构建了一个线性程序, 其最佳值相同, 但变量较少。 这是通过利用宽度小的超大树分解法来利用连接查询的结构, 将答案组的元素综合起来。 我们用三个例子来说明LP( CQ) 方案的各种应用: 优化资源交付, 减少差异隐私的噪音, 以及计算数据挖掘所需的图表模式的S- 度 。