This 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
1998-01-01

Abstract

This 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.
1998
Logic Programming; Datalog; Nondeterministic queries; Expressive power; data complexity
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/124123
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact