Functional Queries in Datalog (Articolo in rivista)

Type
Label
  • Functional Queries in Datalog (Articolo in rivista) (literal)
Anno
  • 2002-01-01T00:00:00+01:00 (literal)
Alternative label
  • Basta Stefano, Flesca Sergio, Greco Sergio (2002)
    Functional Queries in Datalog
    in New generation computing
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Basta Stefano, Flesca Sergio, Greco Sergio (literal)
Pagina inizio
  • 339 (literal)
Pagina fine
  • 371 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 20-4 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto
  • Uno degli aspetti negativi del linguaggio Datalog è rappresentato dal suo limitato potere espressivo. Datalog, infatti, non permette di esprimere tutti i problemi polinomiali ed alcune semplici interrogazioni non possono essere espresse. Nell'articolo, viene presentata una soluzione al problema di estendere Datalog con negazione stratificata in modo da poter esprimere problemi appartenenti alla gerarchia booleana. Tale soluzione prevede (i) l’uso della negazione stratificata, (ii) l’uso dei costrutti choice e should_be, capaci di sfruttare il non-determinismo della semantica dei modelli stabili, (iii) la possibilità di dedurre, dalla sintassi dell’interrogazione, un limite superiore alla complessità dell’interrogazione stessa, (iv) la definizione di un algoritmo che assicura un’efficiente esecuzione delle interrogazioni appartenenti alle diverse classi di complessità. Viene anche mostrato che i risultati ottenuti possono essere utilizzati per il progetto di un linguaggio funzionale per esprimere problemi appartenenti alla gerarchia booleana. Un’interrogazione viene detta funzionale se la sua risposta sotto la semantica della possibilità (esiste un modello che soddisfa l’interrogazione) e della certezza (tutti i modelli soddisfano l’interrogazione) è la stessa. Inoltre, sono state analizzate anche le proprietà delle interrogazioni funzionali sotto le diverse semantiche basate sui modelli stabili. (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • 1- ICAR-CNR; 2- DEIS UNICAL; 3 - DEIS UNICAL (literal)
Titolo
  • Functional Queries in Datalog (literal)
Abstract
  • A functional query is a query whose answer is always defined and unique i.e. it is either true or false in all models. It has been shown that the expressive powers of the various types of stable models, when restricted to the class of DATALOG: functional queries, do not in practice go beyond those of well-founded semantics, except for the least undefined stable models which, instead, capture the whole Boolean hierarchy BH. In this paper we present a \"functional\" language which, by means of a disciplined use of negation, lieves the desired level of expressiveness up to BH. Although the semantics of the new language is partial, all atoms in the source program are defined and possibly undefined atoms are introduced in a rewriting phase to increase the expressive power. We show that the language satisfies \"desirable\" properties better than classical languages with (unstratified) negation and stable model semantics. We present an algorithm for the evaluation of functional queries and we show that exponential time resolution is required for hard problems only. Finally we present the architecture of a prototype of the language which has been developed. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it