Riepilogo Tecnico: Interrogazione e Riparazione di Basi di Conoscenza Prioritarie Incoerenti

1. Enunciato del Problema

Il lavoro affronta la sfida della gestione dell'incoerenza nella Risposta alle Query Mediate da Ontologie (OMQA) quando la base di conoscenza (KB) sottostante contiene fatti prioritari. Mentre le semantica standard tolleranti all'incoerenza (come AR, IAR e brave) si basano sul concetto di riparazioni (sottoinsiemi massimali per inclusione consistenti dei dati), spesso non riescono a distinguere tra riparazioni in base all'affidabilità o alla preferenza di specifici fatti.

In contesti di database, Staworko, Chomicki e Marcinkowski (2012) hanno introdotto tre nozioni di riparazioni ottimali (Pareto, globale e completamento) basate su una relazione di priorità tra fatti conflittuali. Questo lavoro indaga il trasferimento di queste nozioni al contesto OMQA, specificamente per Logiche Descrittive leggere (DL-Lite). I problemi fondamentali analizzati sono:

1. Conseguimento della Query: Determinare se una query vale sotto semantica tolleranti all'incoerenza basate su riparazioni ottimali (varianti di AR, IAR e brave).
2. Unicità: Decidere se esiste una singola riparazione ottimale.
3. Enumerazione: Enumerare tutte le riparazioni ottimali.
4. Collegamento all'Argomentazione: Stabilire una corrispondenza formale tra queste riparazioni e le estensioni nei framework di argomentazione astratta.

2. Metodologia

Gli autori adottano una metodologia duplice che combina l'analisi della complessità con la teoria dell'argomentazione astratta.

2.1 Analisi della Complessità

Lo studio si concentra sulla complessità dei dati, dove l'ontologia ($T$) e la query ($q$) sono fissate, e la complessità è misurata rispetto alla dimensione dell'ABox ($A$). L'analisi copre:

• Dialect di DL-Lite: Principalmente $DL\text{-}Lite_{core}$ e $DL\text{-}Lite_{H_{horn}}$.
• Tipi di Riparazione: Riparazioni standard ($SRep$), Pareto-ottimali ($PRep$), Globalmente-ottimali ($GRep$) e di Completamento-ottimali ($CRep$).
• Semantica: Varianti di AR (conseguimento da tutte le riparazioni), IAR (conseguimento dall'intersezione) e brave (conseguimento da almeno una).
• Relazioni di Priorità: Relazioni generali acicliche, relazioni transitve e relazioni strutturate per punteggio (dove le priorità sono derivate da livelli di priorità).

2.2 Mappatura del Framework di Argomentazione

Il lavoro introduce una traduzione innovativa dalle KB prioritarie ai Framework di Argomentazione Basati su Insiemi con Preferenze (PSETAF).

• Argomenti: Asserzioni dell'ABox.
• Attacchi: Derivati da conflitti (sottoinsiemi minimi inconsistenti). Un attacco $S \to \alpha$ si verifica se $S \cup \{\alpha\}$ è inconsistente.
• Preferenze: La relazione di priorità $\succ$ sui fatti è mappata in una relazione di preferenza sugli argomenti.
• Riduzione: Gli autori definiscono una riduzione dai PSETAF ai SETAF standard, permettendo l'applicazione di semantica di argomentazione consolidate (stabile, preferita, fondata) per definire le riparazioni.

3. Contributi e Risultati Chiave

3.1 Complessità dei Compiti di Ragionamento

Il lavoro fornisce un quadro quasi completo della complessità dei dati per il ragionamento con riparazioni ottimali in DL-Lite.

• Verifica della Riparazione:
  • Pareto e Completamento: In P (tempo polinomiale).
  • Globale: coNP-completo.
• Conseguimento della Query:
  • Pareto/Completamento (AR/IAR): coNP-completo.
  • Pareto/Completamento (Brave): NP-completo.
  • Globale (AR/IAR): $\Pi^p_2$-completo.
  • Globale (Brave): $\Sigma^p_2$-completo.
  • Nota: A differenza delle riparazioni standard dove le semantica IAR e brave sono trattabili (in $AC^0$), l'introduzione di criteri di ottimalità aumenta generalmente la complessità al secondo livello della gerarchia polinomiale per le riparazioni globali.
• Unicità ed Enumerazione:
  • Unicità Pareto: coNP-completo.
  • Unicità Globale: $\Pi^p_2$-completo.
  • Enumerazione: L'enumerazione delle riparazioni Pareto e Globali non è in TOTALP (non può essere eseguita con tempo totale polinomiale) per $DL\text{-}Lite_{core}$. Tuttavia, per le riparazioni di Completamento-ottimali, l'enumerazione è in DELAYP (ritardo polinomiale) per conflitti binari.
• Transitività: Se la relazione di priorità è transitiva, l'unicità per le riparazioni Globali diventa trattabile (P), sebbene gli altri limiti inferiori rimangano invariati.

3.2 Connessione all'Argomentazione

Un contributo teorico centrale è la mappatura precisa tra riparazioni ottimali ed estensioni di argomentazione:

• Riparazioni Pareto-Ottimali: Corrispondono esattamente alle estensioni stabili del PSETAF associato.
• Estensioni Preferite: Sotto ipotesi ragionevoli (in particolare, se la relazione di priorità è transitiva o i conflitti sono binari), le riparazioni Pareto-ottimali coincidono anche con le estensioni preferite.
• Riparazioni Globali e di Completamento: Queste corrispondono a sottoinsiemi propri delle estensioni stabili ma attualmente mancano di un analogo diretto nella letteratura standard sull'argomentazione.

3.3 Semantica Fondata

Ispirati dall'estensione fondata nell'argomentazione, gli autori propongono una nuova semantica per le KB prioritarie:

• Definizione: Una query è conseguita sotto la semantica fondata se vale nell'estensione fondata del PSETAF associato.
• Proprietà:
  • L'estensione fondata è un sottoinsieme di ogni riparazione Pareto-ottimale (un'under-approssimazione di P-IAR).
  • È strettamente più produttiva (contiene più asserzioni) della semantica Elect proposta di recente.
  • Complessità: Il conseguimento della query sotto la semantica fondata è P-completo nella complessità dei dati per $DL\text{-}Lite_{H_{horn}}$.
• Implementazione: L'estensione fondata può essere calcolata tramite la semantica ben fondata di un programma logico normale, o approssimata da una query del primo ordine (SQL) per profondità di iterazione fisse.

4. Significato e Affermazioni

Il lavoro rivendica importanza in tre aree principali:

1. Paesaggio della Complessità: Chiarisce che, sebbene le riparazioni ottimali offrano una gestione dell'incoerenza più sfumata, comportano un costo computazionale significativo rispetto alle riparazioni standard, spingendo spesso i problemi al secondo livello della gerarchia polinomiale. Tuttavia, identifica casi specifici trattabili (conseguimento Pareto/Completamento, semantica fondata).
2. Ponte con l'Argomentazione: Stabilisce un legame rigoroso tra le riparazioni di database prioritarie e l'argomentazione astratta. Dimostrando che le riparazioni Pareto-ottimali sono estensioni stabili, il lavoro colloca l'OMQA in un contesto teorico più ampio, permettendo l'importazione di risultati dall'argomentazione (ad esempio, proprietà di coerenza dei framework simmetrici).
3. Semantica Pratica: La proposta della semantica fondata offre un'alternativa trattabile per la gestione dell'incoerenza. Fornisce un'approssimazione calcolabile in tempo polinomiale della semantica Pareto-IAR che è più informativa delle alternative esistenti come Elect. Il lavoro dimostra che questa semantica può essere implementata utilizzando la programmazione logica standard o sistemi di database relazionali.

Gli autori notano che, sebbene non rispondano definitivamente a quale delle tre nozioni di riparazione ottimale (Pareto, Globale, Completamento) sia "più naturale", la corrispondenza delle riparazioni Pareto con le estensioni stabili e preferite suggerisce una forte giustificazione teorica per la loro adozione. Il lavoro contribuisce anche con nuovi risultati tecnici alla comunità dell'argomentazione, come la coerenza dei PSETAF fortemente simmetrici con preferenze transitve.