CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThis paper introduces a simple and powerful extension of stratified DATALOG which permits to express various DB-complexity classes. The new language, called DATALOG¬s,c,p, extends DATALOG with stratified negation, a non-deterministic construct, calledchoice, and a weak form of constraints, calledpreference rules, that is, constraints that should be respected but, if they cannot be eventually enforced, they only invalidate the portions of the program which they are concerned with. Although DATALOG with stratified negation is not able to express all polynomial time queries, the introduction of the non-deterministic constructchoice permits to express, exactly, the ‘deterministic fragment’ of the class of DB-queriesP, under the non-deterministic semantics, NP, under the possible semantics, and coNP, under the certain semantics. The introduction of preference rules, further increases the expressive power of the language, and permits to express the complexity classes Σ2p, under the possibility semantics, and Π2p, under the certainty semantics.
Non-determinism and weak constraints in Datalog / Greco, Sergio. - In: NEW GENERATION COMPUTING. - ISSN 0288-3635. - 16 (4)(1998), pp. 373-396.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Non-determinism and weak constraints in Datalog |
| Autori: | |
| Data di pubblicazione: | 1998 |
| Rivista: | |
| Citazione: | Non-determinism and weak constraints in Datalog / Greco, Sergio. - In: NEW GENERATION COMPUTING. - ISSN 0288-3635. - 16 (4)(1998), pp. 373-396. |
| Handle: | http://hdl.handle.net/20.500.11770/124123 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/20.500.11770/124123
Copyright © 2021