Definitions
adom - the active domain of a database instance I, is the set of all constants occuring in I.
completeness - a language L in a complexity class C is complete in C if solving it allows solving all other problems in C, also within C. In this case L is said to have the completeness property in respect to C.
reduction - Let L and K be languages in a complexity class C. If there is a computable mapping f from L to K s.t. for each w, w Î L iff f(w) Î K, then f is said to be a reduction from L to K.
If L is reducible to K and K is complete in respect to C than L is also complete in C.
even - The query even on a unary relation R is defined as follows:
even(R) = true if |R| is even and false otherwise