Functional Aggregate Queries with Additive Inequalities
  Motivated by fundamental applications in databases and relational machine
learning, we formulate and study the problem of answering functional aggregate
queries (FAQ) in which some of the input factors are defined by a collection of
additive inequalities between variables. We refer to these queries as FAQ-AI
for short.
  To answer FAQ-AI in the Boolean semiring, we define relaxed tree
decompositions and relaxed submodular and fractional hypertree width
parameters. We show that an extension of the InsideOut algorithm using
Chazelle's geometric data structure for solving the semigroup range search
problem can answer Boolean FAQ-AI in time given by these new width parameters.
This new algorithm achieves lower complexity than known solutions for FAQ-AI.
It also recovers some known results in database query answering.
  Our second contribution is a relaxation of the set of polymatroids that gives
rise to the counting version of the submodular width, denoted by #subw. This
new width is sandwiched between the submodular and the fractional hypertree
widths. Any FAQ and FAQ-AI over one semiring can be answered in time
proportional to #subw and respectively to the relaxed version of #subw.
  We present three applications of our FAQ-AI framework to relational machine
learning: k-means clustering, training linear support vector machines, and
training models using non-polynomial loss. These optimization problems can be
solved over a database asymptotically faster than computing the join of the
database relations.
