Semantics and properties of existential quantifiers in deductive databases (Q685471)

Controlled occurrences of existential quantifiers can enhance the expressive power of deductive databases without introducing a null value though existential quantifiers have been generally proposed to represent the null value (exists but unknown). In order to extend the expressive power, the paper considers two types of IDB, namely an acceptable rule and an extended rule, which can have existential quantifiers in the IDB in a restricted way such that no null value is introduced. We present the precise semantics of existential quantifiers in the IDB, and peculiar consequences associated with these rules in deductive databases. Among others, we provide the necessary and sufficient condition under which Horn databases with acceptable rules become indefinite. Major contribution of the paper is to provide a theoretic basis to researches on existential quantifiers of the deductive database applications.