💻 computer science

PathFinder: A unified approach for handling paths in graph query languages

Questo articolo introduce PathFinder, un approccio unificato e altamente efficiente per l'elaborazione di query di percorso nei moderni linguaggi di grafo che sfrutta una rappresentazione compatta dei percorsi e un'esecuzione in pipeline per ottenere prestazioni stabili e superare i motori di grafo esistenti di un ordine di grandezza.

Autori originali: Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

Pubblicato 2026-07-15

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di esplorare una massiccia, magica città chiamata Graph City. In questa città, ogni persona è un edificio (un nodo) e ogni relazione tra loro è una strada (un arco) con un segnale specifico sopra, come "segue", "vive" o "lavora".

Per anni, le sue guide turistiche (i vecchi motori di database) hanno avuto una regola strana: se chiedevi, "Mostrami tutti i modi in cui posso andare da Joe alla Torre Eiffel prendendo solo strade 'segue'", la guida si limitava a indicare e dire: "Ok, puoi arrivarci!", e si fermava. Ti davano la destinazione, ma non ti mostravano la mappa del viaggio.

Questo è un problema per i detective. Se stai cercando di risolvere un mistero (come individuare il riciclaggio di denaro o tracciare un rumor), non vuoi solo sapere chi è connesso; hai bisogno di vedere l'intero percorso che hanno fatto. Ci sono andati direttamente? Ci hanno girato intorno tre volte? Hanno preso una scorciatoia?

Entra in scena PathFinder, una nuova guida super intelligente costruita da Benjamín, Wim, Carlos e Domagoj. Questo articolo presenta PathFinder, la prima guida che non solo può dirti chi è connesso, ma può anche consegnarti la mappa esatta di ogni possibile percorso, non importa quanto complicate siano le regole.

La magia del "Grafo Prodotto"

Come fa PathFinder a non perdersi in un labirinto? Immagina di avere una mappa regolare della città e di avere anche una piccola, magica lista di controllo (un automa) che dice: "Devi prendere una strada 'segue', poi un'altra strada 'segue', poi una strada 'lavora'".

PathFinder non si limita a camminare per la città; costruisce una città ombra (chiamata Grafo Prodotto) dove ogni edificio è una combinazione di un edificio della città reale e un passaggio della lista di controllo.

Se sei a "Joe" e hai compiuto zero passi, sei a (Joe, Passo 0).
Se prendi una strada "segue" verso "Paul", ti sposti a (Paul, Passo 1).

Camminando attraverso questa città ombra, PathFinder può vedere istantaneamente quali percorsi corrispondono alla tua lista di controllo. È come avere un GPS che illumina solo le strade su cui ti è permesso guidare, ignorando il resto.

I 27 modi per camminare

L'articolo spiega che ci sono 27 regole diverse (chiamate "modi") per come puoi camminare attraverso Graph City. PathFinder è il primo motore in grado di gestire tutte le 27. Ecco alcuni dei gusti:

WALK (Camminata): Puoi andare ovunque, anche se cammini in cerchio o visiti la stessa casa due volte. (Questo è il più facile, ma può portare a loop infiniti!).
TRAIL (Sentiero): Puoi visitare la stessa casa due volte, ma non puoi percorrere la stessa strada due volte.
SIMPLE (Semplice): Non puoi visitare la stessa casa due volte (a meno che tu non parta e finisca nello stesso posto). Questa è la regola più difficile da seguire perché il numero di percorsi possibili può esplodere.
ANY SHORTEST (Qualsiasi il più breve): Dammi solo uno dei percorsi più veloci.
ALL SHORTEST (Tutti i più brevi): Dammi ogni singolo percorso che sia il più veloce.
SHORTEST k GROUPS (Gruppi k più brevi): Dammi i percorsi più veloci, poi il secondo gruppo di percorsi più veloci, e così via fino a $k$ gruppi.

Gli autori dimostrano che, sebbene alcune di queste regole (come trovare un percorso "Semplice") siano teoricamente molto difficili — così difficili che i computer di solito si arrendono su mappe enormi — PathFinder le gestisce sorprendentemente bene nel mondo reale.

Il problema dell' "Infinite Loop" (Ciclo Infinito)

Un grande mal di testa in Graph City è che se c'è un ciclo (come Joe segue Paul, e Paul segue Joe), potresti camminare intorno a quel ciclo per sempre. Se chiedi "tutte le camminate", la risposta è infinita!
Per risolvere questo, gli standard GQL e SQL/PGQ (i libri delle regole per questi linguaggi) ti permettono di scegliere una modalità come "Simple" o "Trail" per fermare i loop infiniti. PathFinder rispetta perfettamente queste regole. Sa esattamente quando smettere di esplorare un percorso in modo da non rimanere intrappolato in un cerchio infinito, pur trovando tutti i percorsi validi che hai richiesto.

Il test di velocità: PathFinder contro gli altri

Gli autori non si sono limitati a costruire PathFinder; l'hanno messa alla prova contro i grandi nomi del settore: Neo4j, Nebula, Kuzu, Jena, Blazegraph e Virtuoso.

Hanno eseguito test su tre diversi scenari:

Pokec: Una rete sociale di medie dimensioni con 1,6 milioni di persone e 30 milioni di connessioni.
Wikidata: Un gigantesco grafo di conoscenza del mondo reale con 364 milioni di nodi e 1,257 miliardi di archi.
Diamond: Un grafo matematicamente costruito, complicato, progettato per avere un numero esponenziale di percorsi (specificamente, $2^n$ percorsi).

I Risultati:

Velocità: PathFinder è stato da 10 a 100 volte più veloce degli altri motori in quasi tutti i test.
Stabilità: Mentre gli altri motori iniziavano a crashare o a dare timeout (arrendersi) quando i percorsi diventavano più lunghi o complessi, PathFinder ha continuato a procedere con costanza.
La sorpresa dell' "Intratabile": Per le modalità "Simple" e "Trail", la teoria dice che il computer dovrebbe impiegare un tempo infinito per trovare la risposta. Ma nei test del mondo reale (come su Wikidata), PathFinder ha trovato 100.000 percorsi rapidamente. Gli autori suggeriscono che ciò sia dovuto al fatto che i dati del mondo reale non presentano solitamente la specifica "tempesta perfetta" di connessioni che fa esplodere la matematica.

Cosa NON fa PathFinder (ancora)

È importante sapere cosa questo articolo non afferma:

Non dice che PathFinder sia magico. Se chiedi ogni singolo percorso in un grafo con cicli, la risposta è comunque infinita, e nessun computer può stamparla. PathFinder si limita a fermarsi a un limite che hai impostato (come 100.000 risultati).
Non sostiene di aver risolto il problema del "Simple Path" per tutti i possibili grafi. L'articolo ammette che, negli scenari teorici peggiori, trovare un percorso semplice è ancora NP-completo (un modo elegante per dire "computazionalmente molto difficile"). PathFinder funziona semplicemente meglio di tutti gli altri sui grafi che usiamo realmente nella vita quotidiana.
Non sostiene di aver risolto la modalità "Simple" per RDF (un tipo specifico di formato dati) ancora. Gli autori dicono di non aver implementato la modalità "Trail" per RDF perché non è chiaro come definire un "sentiero" quando gli archi non hanno nomi univoci.

In sintesi

PathFinder è un nuovo motore che agisce come una guida turistica potenziata. Può prendere un insieme complesso di regole (come "Trova tutti i percorsi da Joe a ENS Paris che seguono il pattern 'segue' poi 'lavora'") e restituire le mappe effettive di quei viaggi.

Gli autori hanno misurato questo su dati reali e hanno scoperto che PathFinder è significativamente più veloce e stabile rispetto agli attuali motori di database a grafi di alto livello. Hanno persino dimostrato che può essere aggiunto ai sistemi esistenti (come i motori SPARQL) per dare loro questo nuovo superpotere. Sebbene la matematica dica che alcuni di questi compiti dovrebbero essere impossibili da eseguire rapidamente, nel disordinato mondo reale, PathFinder dimostra che può essere fatto con una velocità straordinaria.

Riepilogo Tecnico: PathFinder: Restituire Percorsi nelle Query su Grafi

Definizione del Problema

I moderni linguaggi di interrogazione per grafi, inclusi SPARQL, Cypher, SQL/PGQ e lo standard emergente GQL, si basano pesantemente sulle query di percorso (path queries). Mentre SPARQL supporta le Regular Path Queries (RPQ) per identificare coppie di nodi connessi da percorsi che corrispondono a un'espressione regolare, esso restituisce solo gli endpoint. Al contrario, Cypher, SQL/PGQ e GQL permettono agli utenti di restituire l'intero percorso (witness) che soddisfa tali query.

Tuttavia, esiste un divario significativo tra le capacità teoriche di questi linguaggi e la loro implementazione pratica. Gli attuali motori di database a grafi mancano di un supporto completo per la restituzione dei percorsi sotto l'intero spettro dei 27 modi di percorso definiti dagli standard GQL e SQL/PGQ. Questi modi includono varie restrizioni (ad es. WALK, TRAIL, SIMPLE, ACYCLIC) e selettori (ad es. ANY, ALL SHORTEST, SHORTEST k, SHORTEST k GROUPS). I motori esistenti:

Supportano tutte le RPQ ma non possono restituire i percorsi (motori SPARQL).
Possono restituire percorsi ma solo per un sottoinsieme limitato di espressioni regolari o modi di percorso (motori di property graph come Neo4j, Kuzu, Nebula).
Soffrono di problemi di scalabilità, spesso fallendo nel gestire efficientemente le query di percorso a causa del potenziale numero esponenziale di percorsi corrispondenti.

Inoltre, sebbene la complessità teorica del trovare percorsi semplici o trail sia nota per essere NP-completa, le implementazioni pratiche spesso faticano a fornire prestazioni stabili anche per query teoricamente intrattabili su dati del mondo reale.

Metodologia

Il documento introduce PATHFINDER, un framework unificato per valutare le RPQ e restituire percorsi sotto tutti i 27 modi di percorso di GQL. Il nucleo dell'approccio si basa sulla costruzione del grafo prodotto, combinando il database di grafi di input $G$ con un automa a stati finiti non deterministico (NFA) $A$ derivato dall'espressione regolare della query.

Principi Algoritmici Fondamentali

Costruzione del Grafo Prodotto: Il framework costruisce un grafo prodotto $G \times A$ dove i nodi sono coppie $(v, q)$ che rappresentano un nodo $v$ nel grafo e uno stato $q$ nell'automa. Gli archi nel grafo prodotto corrispondono alle transizioni nell'automa che corrispondono alle etichette degli archi nel grafo.
Costruzione Lazy (Pigra): Il grafo prodotto è costruito in modo pigro, il che significa che solo le porzioni necessarie vengono generate per valutare la query, consentendo un'esecuzione in pipeline in cui i risultati vengono restituiti non appena vengono rilevati.
Rappresentazione del Multiset di Percorsi (PMR): Gli algoritmi mantengono una rappresentazione compatta di tutti i percorsi corrispondenti utilizzando stati di ricerca. Uno stato di ricerca include tipicamente il nodo corrente, lo stato dell'automa, la profondità e i puntatori agli stati predecessori, consentendo la ricostruzione dei percorsi senza memorizzarli esplicitamente durante la ricerca.

Algoritmi Specifici per i Modi di Percorso

Il documento dettaglia le specifiche adattamenti della ricerca nel grafo prodotto per diversi modi di percorso:

Modi WALK (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS):
- ANY/ANY SHORTEST: Utilizza BFS o DFS standard sul grafo prodotto. Per gestire il non-determinismo e garantire un singolo percorso per coppia di endpoint, l'algoritmo traccia gli stati visitati $(n, q)$ e utilizza un insieme ReachedFinal per evitare duplicati.
- ALL SHORTEST: Estende la BFS per tracciare tutti i percorsi più brevi verso un nodo. Lo stato di ricerca include una lista di puntatori (prevList) a tutti i predecessori che generano un percorso minimo, consentendo l'enumerazione di molteplici percorsi brevi.
- SHORTEST k / ANY k: Traccia percorsi di lunghezze crescenti fino a un limite $k$ . L'algoritmo mantiene i conteggi dei percorsi che raggiungono ogni stato per garantire la terminazione e restituisce i $k$ percorsi più brevi.
- SHORTEST k GROUPS: Simile al precedente ma raggruppa i percorsi per lunghezza, restituendo tutti i percorsi fino alla $k$ -esima distinta lunghezza trovata.
Modi con Restrizioni (TRAIL, SIMPLE, ACYCLIC):
- Questi modi sono noti per essere NP-completi nel caso peggiore. Il framework impiega un'esplorazione brute-force del grafo prodotto con pruning (potatura).
- La funzione isValid controlla se l'estensione di un percorso viola la restrizione specifica (ad es. ripetere un arco per TRAIL o un nodo per SIMPLE).
- Sebbene la complessità nel caso peggiore rimanga esponenziale, l'approccio è progettato per essere efficiente su grafi reali dove il numero di percorsi validi è spesso gestibile.

Implementazione e Integrazione

Property Graphs: Implementato sopra MillenniumDB, un motore di grafi open-source. La sintassi estende i pattern simili a Cypher per includere variabili di percorso e modi (ad es. MATCH (src)=[MODE ?p rgx]=>(tgt)).
Estensione SPARQL: Il framework estende la sintassi SPARQL per supportare la restituzione dei percorsi (ad es. src MODE (path AS ?p) tgt), dimostrando che i motori RDF esistenti possono essere aumentati con queste capacità.
Modello di Esecuzione: Gli algoritmi sono implementati utilizzando iteratori lineari per l'esecuzione in pipeline, garantendo che i percorsi vengano restituiti "on-the-fly" piuttosto che richiedere la costruzione dell'intero insieme di soluzioni prima dell'output.

Contributi Chiave

Primo Framework Unificato: PATHFINDER è il primo sistema a supportare la restituzione dei percorsi per tutti i 27 modi di percorso prescritti dagli standard GQL e SQL/PGQ per tutte le regular path queries.
Novità Algoritmica: Fornisce algoritmi implementabili basati sulla costruzione del grafo prodotto che gestiscono le complessità dei modi di percorso, inclusa la gestione di automi non deterministici e l'enumerazione di molteplici percorsi minimi o gruppi di percorsi.
Estensione SPARQL: Dimostra la fattibilità di estendere SPARQL per restituire i witness dei percorsi, colmando il divario tra le capacità RDF e quelle dei property graph.
Fattibilità Pratica: Attraverso una sperimentazione estesa, il documento mostra che, nonostante la difficoltà teorica per certe modalità (come TRAIL), l'approccio fornisce prestazioni sorprendentemente stabili su dati del mondo reale.

Risultati Sperimentali

Gli autori hanno valutato PATHFINDER utilizzando tre dataset: Pokec (social network), Wikidata (grande grafo di conoscenza) e un grafo sintetico Diamond (progettato per avere un numero esponenziale di percorsi).

Prestazioni: PATHFINDER ha costantemente superato i motori allo stato dell'arte (Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso) di uno o due ordini di grandezza (velocizzazione di 10x–100x).
Scalabilità:
- Su Pokec, PATHFINDER ha mantenuto prestazioni stabili all'aumentare della lunghezza dei percorsi, mentre altri sistemi hanno spesso subito timeout.
- Su Wikidata, PATHFINDER ha elaborato con successo 659 query complesse, mentre i motori SPARQL (che non restituiscono percorsi) erano significativamente più lenti, e i motori di property graph (Neo4j) andavano in timeout sulla stragrande maggioranza delle query.
- Sul grafo Diamond, PATHFINDER ha dimostrato una complessità temporale lineare per i modi WALK, mentre altri motori hanno mostrato una crescita esponenziale. Per i modi TRAIL, la variante DFS di PATHFINDER si è rivelata superiore alla BFS nel gestire un numero massiccio di percorsi.
Robustezza: Il sistema ha gestito query teoricamente intrattabili (ad es. TRAIL su grandi grafi) con prestazioni stabili, suggerendo che le distribuzioni dei dati del mondo reale mitigano la complessità teorica del caso peggiore.

Significato e Rivendicazioni

Il documento afferma che PATHFINDER rappresenta un passo avanti significativo nell'elaborazione delle query sui grafi, unificando le capacità teoriche di GQL/SQL/PGQ con l'implementazione pratica.

Fattibilità della Restituzione dei Percorsi: Il lavoro prova che restituire i witness completi dei percorsi per RPQ complesse non è solo teoricamente possibile, ma anche praticamente efficiente, anche per i modi precedentemente considerati intrattabili.
Conformità agli Standard: È il primo motore a supportare pienamente i 27 modi di percorso dello standard GQL, colmando una lacuna critica nella tecnologia attuale dei database.
Estensibilità: Il successo dell'integrazione in MillenniumDB e l'estensione di SPARQL dimostrano che questi algoritmi possono essere incorporati nei pipeline dei database esistenti senza richiedere una riscrittura completa del motore sottostante.
Prospettive Future: Gli autori notano che, sebbene l'attuale implementazione gestisca le RPQ standard, il lavoro futuro esplorerà query più espressive che coinvolgono proprietà di dati di nodi e archi, e sono necessarie ulteriori indagini su come la semantica di restituzione dei percorsi si integri con la specifica sintassi dei percorsi di proprietà di SPARQL.

In conclusione, PATHFINDER offre una strategia solida e ad alte prestazioni per le query di restituzione dei percorsi, sfidando l'idea che tali funzionalità debbano necessariamente comportare una perdita di scalabilità o richiedere una limitazione della potenza espressiva del linguaggio di interrogazione.