  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.
