Tyck till om SwePub Sök
här!
Sökning: WFRF:(Lukaszewicz Witold 1947 )
> (1995-1999) >
Declarative PTIME q...
Declarative PTIME queries for relational databases using quantifier elimination
-
- Doherty, Patrick, 1957- (författare)
- Linköpings universitet,Tekniska högskolan,KPLAB - Laboratoriet för kunskapsbearbetning
-
- Lukaszewicz, Witold, 1947- (författare)
- Linköpings universitet,Tekniska högskolan,KPLAB - Laboratoriet för kunskapsbearbetning
-
- Szalas, Andrzej, 1956- (författare)
- Linköpings universitet,Tekniska högskolan,KPLAB - Laboratoriet för kunskapsbearbetning
-
(creator_code:org_t)
- Oxford University Press, 1999
- 1999
- Engelska.
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press. - 0955-792X .- 1465-363X. ; 9:5, s. 737-758
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer science
- Datavetenskap
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas