liu.seSearch for publications in DiVA
ReferencesLink to record
Permanent link

Direct link
Declarative PTIME queries for relational databases using quantifier elimination
1999 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 9, no 5, 737-758Artikel i tidskrift (Refereed) Published
Abstract [en]

In this paper, we consider the problem of expressing and computing queries on relational deductive databases in a purely declarative query language, called SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME (polynomial time) 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 consider extending the method to incomplete relational databases using intuitions related to circumscription techniques.

National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-41616 (URN)10.1093/logcom/9.5.737 (DOI)58394 (Local ID)oai:DiVA.org:liu-41616 (OAI)
Available from2009-10-10 Created:2009-10-10 Last updated:2011-02-23

Open Access in DiVA

No fulltext

Other links

Publisher's fulltext

Search in DiVA

By author/editor
Doherty, PatrickLukaszewicz, WitoldSzalas, Andrzej
By organisation
The Institute of TechnologyKPLAB - Knowledge Processing Lab
In the same journal
Journal of logic and computation (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Citations

Web of Science®:

Altmetric score

Totalt: 16 hits
ReferencesLink to record
Permanent link

Direct link