一句话：提出 LP(CQ) 语言，并用广义超树分解因子化答案集元素，以更少变量高效求解合取查询定义的线性规划。
本文研究变量为合取查询答案集的线性规划优化问题。作者提出 LP(CQ) 语言，用于描述约束和目标函数依赖于合取查询答案集的线性规划。针对 LP(CQ) 的一个片段，他们给出高效求解算法：不同于按答案集元素逐个建立变量的自然做法，该方法利用合取查询的结构，借助小宽度广义超树分解对答案集元素进行因子化，构造变量更少但最优值相同的线性规划，从而降低求解规模。文中用资源配送优化、差分隐私噪声最小化以及数据挖掘中图模式 s-measure 计算三个例子说明 LP(CQ) 的多种应用。
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.
@article{paperbot2782,
title = {Linear Programs with Conjunctive Database Queries},
author = {Florent Capelli and Nicolas Crosetti and Joachim Niehren and Jan Ramon},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 1},
year = {2024},
doi = {10.46298/lmcs-20(1:9)2024}
}