Intuitionistic deductive databases and the polynomial time hierarchy

AbstractDeductive databases are poor at tasks such as planning and design, where one must explore the consequences of hypothetical actions and possibilities. To address this limitation, we have developed a deductive database language in which a user can create hypotheses and draw inferences from them. In earlier work, we established initial results on the complexity and expressibility of this language. In this paper, we establish more comprehensive results by exploring the interaction of negation-as-failure with a natural syntactic restriction called linearity. The main result is a tight connection between intuitionistic logic, database queries, and the polynomial time hierarchy. A tight connection with second-order logic follows as a corollary. First, we show that rulebases in our language fit neatly into a well-established logical framework—intuitionistic logic. Second, we show that linearity reduces their data complexity from PSPACE to NP. Third, we show that negation-as-failure increase their complexity from NP to some level in the polynomial time hierarchy (PHIER). Specifically, linear rulebases with k strata are data complete for ∑kP, the kth level in the hierarchy. Fourth, we show that linear rulebases express exactly the generic database queries in PHIER. Finally, we characterize the generic queries in ∑kP in terms of rulebases with k strata. Unlike many other expressibility results in the literature, these results do not depend on the artificial assumption that the data domain is linearly ordered. We thus establish a strong link between two well-established, but previously unrelated areas: intuitionistic logic and the polynomial time hierarchy