  Estimating the output size of a query is a fundamental yet longstanding
problem in database query processing. Traditional cardinality estimators used
by database systems can routinely underestimate the true output size by orders
of magnitude, which leads to significant system performance penalty. Recently,
upper bounds have been proposed that are based on information inequalities and
incorporate sizes and max-degrees from input relations, yet they their main
benefit is limited to cyclic queries, because they degenerate to rather trivial
formulas on acyclic queries.
  We introduce a significant extension of the upper bounds, by incorporating
$\ell_p$-norms of the degree sequences of join attributes. Our bounds are
significantly lower than previously known bounds, even when applied to acyclic
queries. These bounds are also based on information theory, they come with a
matching query evaluation algorithm, are computable in exponential time in the
query size, and are provably tight when all degrees are "simple".
