Complessità nel Determinare la Rilevanza delle Query nei Database

Uno studio recente pubblicato su arXiv (2604.22422) esamina le sfide associate alla valutazione della rilevanza di un fatto rispetto a una query congiuntiva booleana (CQ) in un database. La domanda centrale è se un fatto specifico fa parte del sottoinsieme più piccolo del database che soddisfa i requisiti della query. La ricerca rivela che la rilevanza è Σ^p_2-completa per CQ che utilizzano una firma binaria, indicando che è più complessa della valutazione della query. La NP-difficoltà è già stabilita per CQ a catena acicliche. Gli autori sottolineano che gli auto-join (dove più atomi condividono la stessa relazione) contribuiscono significativamente a questa complessità: quando gli auto-join sono limitati o vietati, la complessità della rilevanza si allinea con quella della valutazione della query (NP senza vincoli strutturali).