Complessità della Risposta a Query di Percorso sotto Regole Esistenziali Guardate

Un nuovo articolo su arXiv esamina la complessità della risposta a query di percorso regolare bidirezionale (RPQ) e query congiuntive di percorso regolare (CRPQ) su basi di conoscenza con ontologie espresse come regole esistenziali guardate. Lo studio analizza dapprima le regole esistenziali lineari, scoprendo che la risposta a RPQ e CRPQ è NL-completa in complessità dei dati, eguagliando la complessità per i database a grafo semplici. In complessità combinata, entrambi i compiti sono ExpTime-completi in generale, ma RPQ scende a PTime-completo e CRPQ a PSpace-completo quando l'arità dei predicati è limitata. Per le regole guardate, gli autori forniscono una riduzione non banale che mostra che la risposta a RPQ è 2ExpTime-completa in complessità combinata, con un limite inferiore stretto tramite una riduzione da macchine di Turing alternative con spazio esponenziale. L'articolo contribuisce alla risposta a query mediate da ontologia, estendendo lavori precedenti sulle query congiuntive a query navigazionali.