@TECHREPORT{R-96-34,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-96-34+ps},
NUMBER = {R-96-34},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Doherty, Patrick and Lukaszewicz, Witold and Szalas, Andrzej},
TITLE = {Declarative PTIME Queries to Relational Databases},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-34+abstr},
ABSTRACT = {In this paper, we consider the problem of expressing and computing PTIME queries to relational deductive databases in a purely declarative query language, 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 fixpoint 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 quantifiers may be used and a query is simply a restricted first-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 quantifier elimination techniques and also extend the method to incomplete relational databases using intuitions from Circumscription. 
}