This paper introduces a unified solution to the problem of extending stratified DATALOG to express DB-complexity classes ranging from P to DP. The solution is based on (i) stratified negation as the core of a simple, declarative semantics for negation, (ii) the use of a “choice” construct to capture non-determinism of stable models (iii) the ability to bind a query execution to the complexity class that includes the problem at hand, and (iv) a general algorithm that ensures efficient execution for the different complexity classes. We thus obtain a class of DATALOG programs that preserves computational tractability, while achieving completeness for a wide range of complexity classes.

DATALOG Queries with Stratified Negation and Choice: from P to DP

GRECO, Sergio;SACCA', Domenico;
1995

Abstract

This paper introduces a unified solution to the problem of extending stratified DATALOG to express DB-complexity classes ranging from P to DP. The solution is based on (i) stratified negation as the core of a simple, declarative semantics for negation, (ii) the use of a “choice” construct to capture non-determinism of stable models (iii) the ability to bind a query execution to the complexity class that includes the problem at hand, and (iv) a general algorithm that ensures efficient execution for the different complexity classes. We thus obtain a class of DATALOG programs that preserves computational tractability, while achieving completeness for a wide range of complexity classes.
3-540-58907-4
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/165588
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 10
social impact