On testing soundness of relational expressions

摘要

Informally, a query is sound if it always returns only tuples that are logically implied by the database state and the constraints. We capture the notion of soundness formally using the total tuples in the representative instance of a state. We show that for monotone expressions, the notion of soundness and the notion of losslessness proposed by Maier et al. coincide. Consequently, testing soundness of tableau expressions is reduced to the implication problem of dependencies. We also shown that the problem of testing soundness of expressions in general is undecidable. Finally we find some necessary conditions and some sufficient conditions for an expression involving set difference to be sound.