Riassunto Tecnico: "How Hard is it to Decide if a Fact is Relevant to a Query?"

1. Il Problema: Rilevanza delle Query

Il paper affronta il problema fondamentale della rilevanza delle query (query relevance) nel contesto dei database relazionali e della rappresentazione della conoscenza (Knowledge Representation).

Dato un database $D$, una query congiuntiva (CQ) $q$ e un fatto $f \in D$, il problema consiste nel decidere se $f$ è rilevante per $q$ rispetto a $D$. La rilevanza è definita in termini di supporti minimi: un fatto $f$ è rilevante se appartiene ad almeno un sottoinsieme minimo di fatti $S \subseteq D$ tale che $S$ soddisfi la query ($S \models q$).

Questo problema è cruciale per le tecniche di spiegazione delle query (query answer explanation): identificare i fatti rilevanti permette di riassumere le cause di una risposta o di aiutare gli utenti nel debugging di risultati inaspettati.

2. Metodologia e Approccio

Gli autori analizzano la complessità computazionale del problema attraverso tre lenti principali:

1. Conjunctive Queries (CQ) pure: Analisi della complessità combinata basata sulla struttura della query.
2. Ontology-Mediated Queries (OMQ): Analisi nel contesto di query mediate da ontologie (nello specifico, il linguaggio di descrizione $DL\text{-}Lite_R$), dove la risposta è determinata dall'interazione tra dati (ABox) e assiomi (TBox).
3. Minimal Homomorphisms on Graphs: Un approccio astratto basato sulla teoria dei grafi per studiare la rilevanza come problema di immagine omomorfica minima.

La metodologia si basa sull'identificazione dei "colpevoli" della complessità (ovvero le caratteristiche strutturali che rendono il problema difficile) e sulla proposta di nuovi parametri di larghezza (width) per delimitare classi di query trattabili.

3. Contributi Chiave e Risultati

A. Conjunctive Queries (CQ)

Il paper dimostra che la rilevanza è intrinsecamente più difficile della semplice valutazione della query (query evaluation). Mentre la valutazione di CQ è $\text{NP}$-completa, la rilevanza è $\Sigma^p_2$-completa.

• Il ruolo dei Self-Join: Gli autori identificano nei self-join (l'uso multiplo della stessa relazione nella query) la causa principale dell'incremento di complessità.
• Self-Join Width ($sjw$): Viene introdotto un nuovo parametro, la self-join width. Se il numero di self-join è limitato, la complessità della rilevanza scende al livello della valutazione della query:
  • Per CQ con $sjw$ limitato: $\text{NP}$-completo.
  • Per CQ con $sjw$ limitato e hypertree width limitata: $\text{LogCFL}$-completo.
• Chain Queries: Viene dimostrato che anche per query molto semplici come le chain queries (catene di relazioni), il problema rimane $\text{NP}$-completo.

B. Ontology-Mediated Queries (OMQ)

Nel contesto delle ontologie $DL\text{-}Lite_R$, la complessità è influenzata dall'interazione tra la query e gli assiomi dell'ontologia.

• Interaction Width ($iw$): Gli autori introducono la interaction width, che generalizza il concetto di "interazione libera" (interaction-free). Un'ontologia è interaction-free se un fatto dell'ABox può soddisfare al massimo un atomo della query in un unico modo.
• Risultati di complessità:
  • Se la interaction width è limitata, la rilevanza non è più difficile della valutazione della query.
  • Se si limitano contemporaneamente la interaction width e la treewidth, il problema diventa efficiente ($\text{LogCFL}$ o $\text{NL}$ per query acicliche con foglie limitate).

C. Teoria dei Grafi (Minimal Homomorphisms)

Il paper fornisce una prova di durezza "pura" studiando il problema dell'immagine omomorfica minima su grafi diretti e non diretti.

• Viene dimostrato che il problema MinHomd (diretto) e MinHomu (non diretto) sono entrambi $\Sigma^p_2$-completi.
• Questo risultato implica che la durezza della rilevanza delle CQ ($\Sigma^p_2$) sussiste anche quando si utilizza una singola relazione binaria.

4. Significato e Implicazioni

Il lavoro ha un impatto significativo su diversi fronti:

1. Teoria della Complessità: Fornisce una mappatura precisa della gerarchia di complessità per la rilevanza, distinguendo chiaramente tra ciò che rende difficile la valutazione e ciò che rende difficile la spiegazione (rilevanza).
2. Sistemi di Spiegazione (Explainable AI/DB): Identifica classi di query "ben comportate" per le quali è possibile implementare algoritmi efficienti per generare spiegazioni (minimal supports).
3. Design di Linguaggi: Suggerisce che, per rendere i sistemi di ragionamento su ontologie più spiegabili, è preferibile limitare l'interazione tra gli atomi della query e le inferenze dell'ontologia (limitando la interaction width).

Sintesi dei Risultati di Complessità (Tabella Riassuntiva)

Classe di Query	Valutazione (Combined)	Rilevanza (Combined)
CQ Generiche	$\text{NP}$	$\Sigma^p_2$
CQ con $sjw < \infty$	$\text{NP}$	$\text{NP}$
CQ con $sjw < \infty$ e $hw < \infty$	$\text{LogCFL}$	$\text{LogCFL}$
OMQ ($DL\text{-}Lite_R$, CQ)	$\text{NP}$	$\Sigma^p_2$
OMQ con $iw < \infty$	$\text{NP}$	$\text{NP}$
OMQ con $iw < \infty$ e $tw < \infty$	$\text{LogCFL}$	$\text{LogCFL}$