| One of the fundamental features of deductive database systems (or expert database systems) is the deductive capabilities which derive from the use of the IDB (a set of rules) and an inference rule. As for IDB, most researchers investigate a function-free database, thus excluding the possibility of the occurrence of Skolem functions in the IDB. However, the necessity of existential quantifiers in the IDB is evident when we try to define a view which requires a division operation. In order to extend the expressive power, we introduce two types of IDB rules, 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. Our work is mainly concentrated on the identification of the properties of those rules and the development of an elegant method which handles existential quantifiers according to their semantics in the context of deductive databases.;As a first step, we identify the precise semantics of existential quantifiers in a rule and, based on that, define an expansion form of the rule which shows its semantics clearly. We present how to derive the expansion form effectively and automatically. One interesting consequence associated with the acceptable rule is that a Horn DB becomes potentially indefinite. We provide a necessary and sufficient condition under which indefiniteness actually occurs and also show the definiteness of the extended rule. Next we propose a new approach, the substitution rule, which will be used to handle the extended rule efficiently in a query compilation phase. This approach contrasts with the conventional method based on the resolution principle which possibly involves Skolem functions. The compilation of extended rules based on the substitution rule is addressed. We consider the compilation of a set of recursive extended rules, too. The major results is the recognition of an upper bound on the number of iteration steps necessary to answer a query, independent of the contents of the EDB. |
