Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings

Titolo

Accesso diretto dinamico (ordinato) alla valutazione di query MSO su stringhe compresse da SLP

1. Il Problema

Il lavoro affronta il problema della valutazione di query basate sulla Logica del Secondo Ordine Monadico (MSO) su stringhe. Nello specifico, l'obiettivo non è solo determinare se una stringa soddisfa una formula, ma calcolare l'insieme delle assegnazioni (mapping) delle variabili libere della formula che soddisfano la query.

Poiché l'insieme delle risposte può essere esponenzialmente più grande dell'input, la ricerca si concentra su metodi efficienti per estrarre le risposte senza generarle tutte. Il paper si focalizza su tre aspetti critici:

1. Accesso diretto ordinato (Ranked Direct Access): Data un indice $t$, produrre la $t$-esima risposta (ordinata lessicograficamente) senza dover enumerare le precedenti.
2. Dinamicità: Supportare modifiche alla stringa (o alla sua rappresentazione) dopo la costruzione dell'indice, mantenendo tempi di accesso efficienti.
3. Compressione: Gestire stringhe di grandi dimensioni compresse tramite Programmi a Riga Rettilinea (SLP - Straight-Line Programs), dove la stringa espansa può essere esponenzialmente più lunga della rappresentazione compressa.

Il lavoro migliora un risultato precedente (Bourhis et al., ICDT 2025) riducendo il fattore logaritmico nel tempo di accesso e estendendo la soluzione alle stringhe compresse.

2. Metodologia

L'approccio proposto si basa sulla traduzione della query MSO in un automata vset (un automa a stati finiti che traccia le variabili) e sull'uso di strutture dati matriciali per contare e navigare le risposte.

A. Modellazione tramite Automi Vset

Ogni formula MSO $\phi(x_1, \dots, x_k)$ su una stringa viene convertita in un automa vset non ambiguo e funzionale $A$. Le risposte alla query corrispondono ai percorsi accettanti validi di $A$ sulla stringa $w$.

B. Preprocessing e Strutture Dati (Caso Stringa)

Per una stringa espansa $w$:

1. Matrici di Transizione: Vengono definite matrici $M_{\langle l, r : \tau \rangle}$ di dimensione $|Q| \times |Q|$ (dove $Q$ è l'insieme degli stati) che contano i percorsi parziali tra stati $p$ e $q$ su un intervallo $[l, r]$ della stringa, rispettando un insieme di regole di mappatura $\tau$.
2. Alberi di Matrici: Vengono costruiti $k+1$ alberi binari (dove $k$ è il numero di variabili). Ogni nodo dell'albero memorizza una matrice risultante dal prodotto delle matrici dei figli.
   • La radice rappresenta l'intera stringa.
   • Le foglie rappresentano singoli caratteri.
   • La struttura permette di calcolare il numero di risposte per qualsiasi "fetta" (slice) dell'insieme delle risposte ordinato.
3. Complessità di Preprocessing: $O(|Q|^\omega \cdot |X| \cdot |w|)$, dove $\omega$ è l'esponente della moltiplicazione di matrici.

C. Fase di Accesso (Access Phase)

Per trovare la $t$-esima risposta:

1. Si esegue una ricerca binaria sequenziale per determinare il valore di ogni variabile $x_1, \dots, x_k$.
2. Per determinare $x_i$, si cerca il valore $s_i$ tale che il numero di risposte con $x_i \le s_i$ sia sufficiente a coprire l'indice $t$ corrente.
3. Vengono utilizzati caching (matrici $M^{out}_L$ e $M^{out}_R$) per accumulare i prodotti delle matrici durante la discesa nella ricerca binaria, evitando di ricalcolare i prodotti da zero ad ogni passo.
4. Tempo di Accesso: $O(|Q|^\omega \cdot |X|^2 \cdot \log |w|)$. Questo rappresenta un miglioramento rispetto al precedente $O(\log^2 |w|)$.

D. Estensione agli SLP (Stringhe Comprese)

Per stringhe compresse da un SLP $S$:

1. Gli alberi binari sono sostituiti da strutture grafiche (DAG) che riflettono la struttura dell'SLP.
2. Le matrici sono calcolate dinamicamente sui non-terminali dell'SLP invece che sugli intervalli di caratteri.
3. Si assume che l'SLP sia fortemente bilanciato (profondità $O(\log n)$), ottenibile in tempo lineare.
4. Preprocessing: $O(|Q|^\omega \cdot |X| \cdot |S|)$.
5. Accesso: $O(|Q|^\omega \cdot |X|^2 \cdot \log |w|)$, dove il logaritmo dipende dalla profondità dell'SLP.

E. Gestione delle Modifiche (Edits)

Il lavoro integra un framework di editing (basato su Schmid e Schweikardt, PODS 2022) per gestire operazioni complesse (concatenazione, estrazione, inserimento, copia) su stringhe compresse:

1. Le modifiche all'SLP vengono tradotte in modifiche alla struttura dati delle matrici.
2. L'aggiornamento avviene duplicando i percorsi di non-terminali interessati e propagando le modifiche verso l'alto.
3. Tempo di Aggiornamento: $O(|\psi| \cdot |Q|^\omega \cdot |X| \cdot \log |\text{max\_size}|)$, dove $\psi$ è l'espressione di editing.

3. Risultati Chiave

Il paper presenta i seguenti risultati teorici e pratici:

• Teorema 1 (Stringhe): Per una stringa $w$ e un automa vset non ambiguo $A$, è possibile ottenere accesso diretto ordinato alle risposte in tempo $O(|Q|^\omega \cdot |X|^2 \cdot \log |w|)$ dopo un preprocessing lineare $O(|Q|^\omega \cdot |X| \cdot |w|)$.
• Teorema 6 (SLP): Per una stringa compressa da un SLP $S$, l'accesso diretto ordinato è possibile in tempo $O(|Q|^\omega \cdot |X|^2 \cdot \log |w|)$ dopo un preprocessing $O(|Q|^\omega \cdot |X| \cdot |S|)$.
• Teorema 8 (Dinamicità): È possibile costruire una struttura di accesso diretto modificabile che supporta operazioni di editing complesse con tempi di aggiornamento e accesso logaritmici rispetto alla dimensione della stringa espansa (o massima intermedia).
• Miglioramento: Rispetto al lavoro di Bourhis et al. (ICDT 2025), questo lavoro riduce il fattore logaritmico nel tempo di accesso da $O(\log^2 |w|)$ a $O(\log |w|)$.

4. Significato e Contributi

Questo lavoro è significativo per diversi motivi nel campo della teoria dei database e degli algoritmi su testi:

1. Efficienza nell'Accesso Ordinato: La riduzione del fattore logaritmico nell'accesso diretto è un miglioramento algoritmico sostanziale, rendendo le query MSO più pratiche per l'interazione utente in tempo reale su grandi dataset.
2. Gestione della Compressione: È il primo lavoro che estende l'accesso diretto dinamico alle stringhe compresse da SLP. Questo è cruciale per applicazioni reali dove i dati sono memorizzati in forma compressa (es. log, dati genomici, XML) per risparmiare spazio, ma devono essere interrogati senza decompressione completa.
3. Dinamicità: La capacità di gestire modifiche complesse (non solo aggiornamenti puntuali) mantenendo l'efficienza dell'accesso apre la strada a sistemi di gestione di documenti dinamici che supportano query logiche complesse.
4. Generalità: L'approccio basato su automi vset e matrici è flessibile e può potenzialmente essere esteso ad altri formalismi o strutture dati (come alberi, sebbene il paper menzioni le sfide legate alla contiguità).

In sintesi, il paper fornisce un framework robusto per l'interrogazione efficiente, ordinata e dinamica di dati testuali complessi e compressi, colmando un divario tra la teoria della compressione e l'elaborazione di query logiche avanzate.