LiU Electronic Press
Full-text not available in DiVA
Author:
Doherty, Patrick (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab)
Lukaszewicz, Witold (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab)
Szalas, Andrzej (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab)
Title:
Declarative PTIME queries for relational databases using quantifier elimination
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, The Institute of Technology
Publication type:
Article in journal (Refereed)
Language:
English
Publisher: Oxford University Press
Status:
Published
In:
Journal of logic and computation (Print)(ISSN 0955-792X)(EISSN 1465-363X)
Volume:
9
Issue:
5
Pages:
737-758
Year of publ.:
1999
URI:
urn:nbn:se:liu:diva-41616
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-41616
Local ID:
58394
Subject category:
Computer Science
SVEP category:
Computer science
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.

Available from:
2009-10-10
Created:
2009-10-10
Last updated:
2011-02-23
Statistics:
15 hits