Declarative ptime queries to relational databases.
Patrick Doherty, Witold Łukaszewicz, Andrzej Szałas · 1996
In this paper, we consider the problem of expressing and computing PTIME queries to relational deductive databases in a purely declarative query language we introduce, called SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME and the whole class of PTIME queries is expressible in SHQL. Although similar results have been proven for xpoint languages and extensions to datalog, the claim is that SHQL has the advantage of being purely declarative, where the negation operator is interpreted as classical negation, mixed quanti ers may be used and a query is simply a restricted rst-order theory not limited by the rule-based syntactic restrictions associated with logic programs in general. We describe the PTIME algorithm used to compute queries in SHQL which is based in part on quanti er elimination techniques and also consider extending the method to incomplete relational databases using intuitions related to circumscription techniques. This article is published in the Journal of Logic and Computation 9(5):737-758, 1999. 1