Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Sintesi Tecnica: Semantica Basata sui Costi per l'Interrogazione di Basi di Conoscenza Pesate Inconsistenti

Enunciato del Problema
L'interrogazione di query mediata da ontologie (OMQA) si basa su basi di conoscenza (KB) di logica descrittiva (DL) composte da un TBox (ontologia) e un ABox (dati). La semantica classica dell'OMQA, basata sulla logica del primo ordine, non fornisce risposte informative quando la KB è inconsistente, poiché tutto è conseguito da una contraddizione. Sebbene gli approcci esistenti gestiscano l'inconsistenza tramite riparazioni (ad esempio, AR e semantica brave), questi tipicamente assumono che il TBox sia affidabile e modificano solo l'ABox. Inoltre, le semantiche di riparazione standard spesso trattano tutte le asserzioni come ugualmente affidabili o si affidano alla massimalità basata sulla cardinalità, mancando di un modo sfumato per dare priorità alle informazioni conflittuali in base a diversi gradi di fiducia.

Questo articolo affronta la sfida di interrogare KB di DL inconsistenti introducendo un framework quantitativo. Il problema centrale è definire risposte certe e possibili significative quando sia gli assiomi del TBox che le asserzioni dell'ABox possono essere violati, con le violazioni penalizzate secondo pesi assegnati.

Metodologia e Framework
Gli autori propongono un framework di Base di Conoscenza Pesata (WKB), denotato con $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$.

• Pesi: Una funzione di costo $\omega$ assegna un valore in $\mathbb{N}_{>0} \cup \{+\infty\}$ a ogni assioma in $\mathcal{T}$ e asserzione in $\mathcal{A}$. I pesi infiniti rappresentano vincoli "hard" che devono essere soddisfatti, mentre i pesi finiti rappresentano vincoli "soft" dove valori più elevati indicano una maggiore affidabilità.
• Costo dell'Interpretazione: Il costo di un'interpretazione $I$ è definito come la somma dei pesi di tutti gli assiomi e le asserzioni violati. Specificamente, per un'inclusione di concetti $\tau$, il costo include $\omega_\tau \times |vio_\tau(I)|$, dove $vio_\tau(I)$ è l'insieme degli elementi del dominio che violano l'inclusione. Le asserzioni possono essere violate al massimo una volta.
• Semantica: L'articolo definisce quattro semantiche di entailment per le query basate sul costo delle interpretazioni:
  1. Certa con costo $k$-limitato ($K_\omega \models^k_c q$): $q$ è valida in tutte le interpretazioni con costo $\le k$.
  2. Possibile con costo $k$-limitato ($K_\omega \models^k_p q$): $q$ è valida in almeno un' interpretazione con costo $\le k$.
  3. Certa con costo ottimo ($K_\omega \models^{opt}_c q$): $q$ è valida in tutte le interpretazioni con costo minimo ($optc(K_\omega)$).
  4. Possibile con costo ottimo ($K_\omega \models^{opt}_p q$): $q$ è valida in almeno un' interpretazione con costo minimo.

Il framework generalizza le esistenti semantiche di riparazione. Nello specifico, quando gli assiomi del TBox hanno pesi infiniti, la semantica del costo ottimo coincide con la semantica $\le_\omega$-AR (Bienvenu, Bourgaux e Goasdoué 2014), che seleziona le riparazioni che massimizzano la somma dei pesi delle asserzioni mantenute.

Contributi Principali
Il contributo primario è un'analisi completa della complessità combinata e dei dati dei principali problemi decisionali in questo contesto:

1. Soddisfacibilità con Costo Limitato (BCS): Determinare se esiste un'interpretazione con costo $\le k$.
2. Riconoscimento di Risposte Certe e Possibili: Decidere l'entailment sotto le quattro definite semantiche.

Lo studio copre una gamma di logiche descrittive che vanno dalla leggera $\mathcal{EL}^\bot$ alla espressiva $\mathcal{ALCO}$ (e $\mathcal{ALCO}^\mathcal{Q}$ per le prove dei limiti superiori), gestendo sia Query di Istanza (IQ) che Conjunctive Queries (CQ).

Risultati di Complessità
L'articolo stabilisce limiti di complessità stretti, riassunti come segue:

• Complessità Combinata:

  • La maggior parte dei problemi è EXPTIME-completa.
  • Il riconoscimento di risposte certe per le CQ (sia limitate che a costo ottimo) è 2EXPTIME-completo. Questa alta complessità deriva dalla necessità di verificare l'entailment attraverso tutti i modelli di un costo specifico, il che è correlato alle KB circoscritte.
  • Questi limiti valgono anche quando i pesi e il limite di costo $k$ sono codificati in binario.

• Complessità dei Dati:

  • Soddisfacibilità con Costo Limitato (BCS): NP-completa.
  • Risposta a Costo Limitato (IQ/CQ): NP-completa (possibile) e coNP-completa (certa).
  • Risposta a Costo Ottimo: La complessità dipende fortemente dalla codifica dei pesi:
    • Se i pesi sono codificati in unaria o limitati indipendentemente dalla dimensione dell'ABox, i problemi sono $\Theta^p_2$-completi (risolvibili in tempo polinomiale con chiamate logaritmiche a un oracolo NP).
    • Se i pesi sono codificati in binario e possono essere esponenziali rispetto alla dimensione dell'ABox, i problemi diventano $\Delta^p_2$-completi (risolvibili in tempo polinomiale con accesso a un oracolo NP).
  • L'articolo nota che per la semantica della risposta certa a costo ottimo con pesi binari, il limite superiore rimane aperto, sebbene i limiti inferiori siano $\Delta^p_2$-hard.

Significatività e Rivendicazioni
Gli autori affermano di fornire un "quadro quasi completo" del panorama della complessità per l'interrogazione di KB inconsistenti sotto una semantica basata sui costi. La significatività del lavoro risiede in:

1. Flessibilità Quantitativa: Andare oltre la consistenza binaria verso un approccio graduato in cui le risposte possono essere classificate o filtrate in base alla loro "robustezza" (ovvero, se valgono in interpretazioni vicine al costo ottimale).
2. Generalizzazione: Unificare i concetti di vincoli soft nei database (Carmeli et al. 2021) e riparazioni pesate nelle ontologie, mostrando che le semantiche di costo ottimo generalizzano naturalmente le semantiche di riparazione preferite.
3. Profondità Tecnica: Le prove di complessità sfruttano e adattano tecniche avanzate di ragionamento DL, tra cui:
   • Filtrazione e proprietà di modelli limitati per stabilire i limiti superiori.
   • Riduzioni dal rispondere a query di cardinalità e dalle KB circoscritte per stabilire i limiti inferiori.
   • Adattamenti delle costruzioni di "interlacciamento" e "quoziente" dalla letteratura sulle query di conteggio (Manière 2022) per gestire i vincoli specifici delle violazioni pesate.

L'articolo conclude identificando direzioni future, specificamente l'estensione di questi risultati alle DL con ruoli inversi, inclusioni di ruoli e ruoli funzionali (ad esempio, la famiglia DL-Lite), notando che le attuali tecniche per i limiti superiori non si trasferiscono facilmente a questi costrutti. Evidenzia inoltre la sfida dello sviluppo di algoritmi pratici per l'implementazione.