  Users typically interact with a database by asking queries and examining the
results. We refer to the user examining the query results and asking follow-up
questions as query result exploration. Our work builds on two decades of
provenance research useful for query result exploration. Three approaches for
computing provenance have been described in the literature: lazy, eager, and
hybrid. We investigate lazy and eager approaches that utilize constraints that
we have identified in the context of query result exploration, as well as novel
hybrid approaches. For the TPC-H benchmark, these constraints are applicable to
19 out of the 22 queries, and result in a better performance for all queries
that have a join. Furthermore, the performance benefits from our approaches are
significant, sometimes several orders of magnitude.
