Approximate Lineage for Probabilistic Databases (VLDB 2008) – Chris Re, Dan Suciu
INPUT: monotone k + 1 DNF lambdat
OUTPUT: small sufficient lambdas with e-approximation
Suff(lambdat, e)
Step1: Arithmetize the original lineage formula.
Step2: Approximate using sparse Fourier series.
Step3: Get a (s, e) approximation of the Fourier series (use KM algorithm etc).