Cypher: Ricerca e Aggregazione

In questa lezione approfondiremo gli strumenti ricerca all’interno del database Neo4j utilizzando il linguaggio Cypher. Nella lezione precedente abbiamo introdotto il concetto di pattern matching, mentre nel seguito vedremo alcuni esempi su come effettuare ricerche su grafo che non potremmo fare (se non con molta difficoltà) utilizzando altri modelli di dati. Gli esempi sono tratti da GraphGist.

Relazioni multiple (catene di relazioni)

Vediamo come primo esempio un social network come Twitter: potremmo voler trovare i tweet che appartengono ad una “conversazione”, ossia che sono legati da catene di relazioni di un certo tipo:

MATCH (tweet:Message {id:'20'})<-[r:REPLY_TO*0..10]-(conversation:Message)
RETURN DISTINCT(conversation) AS Conversation
ORDER BY conversation.date_sent

In questa query, partendo da un Message con id pari a 20, abbiamo selezionato tutti gli altri Message, che abbiamo chiamato conversation, che siano correlati al primo da una catena di al massimo 10 relazioni di tipo REPLY_TO. Quindi otterremo non solo le risposte al messaggio, ma anche le risposte alle risposte e via via fino al decimo livello. Lo zero nella specifica della relazione indica che se non viene trovata nessuna risposta al primo messaggio, esso verrà comunque selezionato senza relazioni. Tutti questi nodi, presi in modo distinto (DISTINCT) vengono restituiti per data di invio (tramite ORDER BY) in una colonna chiamata Conversation.

Lavorare con i percorsi (path)

Alcuni degli algoritmi più utilizzati quando si lavora con i grafi sono quelli relativi ai percorsi minimi. Neo4j implementa e supporta un algoritmo molto efficiente per la ricerca del percorso minimo tra due nodi di un grafo. Con queste funzioni si possono eseguire interrogazioni molto interessanti non realizzabili con altri modelli di dati. Ad esempio, è possibile cercare il percorso minimo che collega due persone nel social network:

MATCH path=shortestpath((sender:User)-[r:FOLLOWS*..15]-(p:User))
WHERE length(path) > 1
RETURN path

In questo caso si cerca la relazione fino ad un massimo di 15 passi, escludendo i percorsi formati da un solo passo (utenti che si seguono direttamente).

Concatenare ricerche con WITH

Se si esegue la query precedente nel database dell’esempio, si possono trovare relazioni interessanti, ad esempio che due utenti del social network, pur non conoscendosi, hanno interessi comuni.

Si noterà però che gli utenti Alice e Bridget, pur conoscendosi direttamente, vengono comunque restituiti, anche se abbiamo aggiunto la condizione WHERE. Questo perché i filtraggi vengono eseguiti a monte della ricerca del cammino minimo per questioni di efficienza (e anche perché Cypher vuole essere un linguaggio dichiarativo). Se vogliamo che la condizione di filtraggio venga applicata dopo la ricerca, e quindi, nell'esempio, escludere gli utenti che già si conoscono direttamente, dobbiamo ricorrere alla parola chiave WITH. Questa serve a concatenare più query in cascata, e permette di specificare quali dati dalla query precedente devono passare alla successiva per ulteriori elaborazioni. Ad esempio:

MATCH path=shortestpath((sender:User)-[r:FOLLOWS*..15]-(p:User))
WITH path AS p
WHERE length(p) > 1
RETURN p

Qui abbiamo utilizzato WITH per suddividere la query in due parti, nella prima abbiamo individuato tutti i percorsi minimi tra due utenti qualsiasi. I percorsi individuati vengono passati nella seconda parte della query con il nome p, dove vengono filtrati per lunghezza e quindi restituiti.

La funzione length è una funzione scalare, ossia una funzione che restituisce un solo valore, in questo caso la lunghezza di un percorso. Applicata su una stringa, ne restituisce la lunghezza come numero di caratteri. Le funzioni scalari possono essere usate in filtraggio, ma anche nelle espressioni di ritorno. Altre funzioni scalari sono:

Funzione/i	Descrizione
type	Restituisce il tipo di una relazione, in forma di stringa
coalesce	Dato un elenco arbitrario di parametri, restituisce il primo non nullo, esattamente come l’analoga funzione SQL
timestamp	Funzione senza parametri molto utile, perché genera il numero di millisecondi trascorsi dal 1 gennaio 1970 al momento in cui viene eseguita. È spesso utilizzata per tracciare le operazioni nel database
head, last, etc.	Funzioni per operare con le liste
toInt, etc.	Funzioni di conversione

Altre funzioni utili sono i predicati (funzioni che restituiscono un valore booleano). Tra questi ci sono:

• all, che verifica se una certa condizione è valida per tutti gli elementi di un insieme;
• any, che verifica se una certa condizione è valida per almeno un elemento di un insieme;
• exists, che verifica se esiste una proprietà oppure un pattern.

Vediamo un esempio:

MATCH path=(:User {id:"Charles"})-[:FOLLOWS*1..3]-(other:User)
WHERE  ALL(x IN NODES(path) WHERE x.id <> "Alice")
WITH DISTINCT(other) as other
RETURN other, EXISTS( (other)-[:FOLLOWS]-(:User{ id:"Alice" }) ) as friendOfAlice

Questa query potrebbe essere usata per mostrare all’utente Alice le persone che stanno nelle cerchie dell’utente Charles. Essa infatti cerca gli amici di Charles fino al terzo livello (prima riga), scartando quei percorsi che passano per Alice (seconda riga), prendendo gli utenti distinti, e restituisce l’utente trovato e un valore booleano che indica se è anche un amico di Alice (quarta riga). È degna di nota la sintassi che si usa in ALL e ANY: variabile IN lista WHERE condizione. La funzione nodes usata nella seconda riga restituisce i nodi trovati in un percorso. Si tratta di un’altra funzione che lavora sui percorsi. La sua controparte è relationships, che restiuisce la lista delle relazioni trovate in un percorso.

Per lavorare con le liste esistono anche funzioni comuni nei linguaggi funzionali, come:

• extract, analoga alla funzione map di Haskell o Scala;
• filter;
• reduce.

Per la lista di tutte le funzioni utilizzabili rimandiamo alla guida ufficiale.

Pattern opzionali

Un’astrazione del LEFT JOIN o RIGHT JOIN di SQL nel grafo sarebbe l’idea di avere una corrispondenza opzionale ad un pattern. A questo scopo si utilizza l’istruzione OPTIONAL MATCH. Ad esempio, supponiamo di volere tutti i messaggi inviati da un utente, e per ognuno eventualmente verificare se il messaggio è una risposta ad un altro messaggio:

MATCH (:User {id:"Charles"})-[:SENT]-(m:Message)
OPTIONAL MATCH (m)-[:REPLY_TO]->(x)
RETURN m, x

Questa query rappresenta proprio in Cypher la frase appena detta: tutti i messaggi inviati da Charles, ed eventualmente per ognuno (seconda riga) il messaggio x a cui si sta rispondendo. Per ottenere questo risultato è necessario l’utilizzo di OPTIONAL MATCH invece del semplice MATCH, perché altrimenti verrebbero selezionate soltanto le risposte: in pratica avremmo solamente risultati con la colonna x valorizzata.

Aggregazioni

Con Cypher, aggregare un insieme di dati è semplice come e forse più che in SQL. Dallo stesso esempio precedente, consideriamo di voler ottenere un elenco dei maggiori “influencer” del social network, ossia gli utenti che hanno avuto più retweet.

MATCH (retweet:Message)-[r:FORWARD]->(tweet:Message)<-[:SENT]-(p:User)
RETURN p.id AS User, COUNT(r) AS `Messages Retweeted`
ORDER BY COUNT(r) DESC LIMIT 5

La query praticamente è autoesplicativa: qui vogliamo tutti i retweet fatti a seguito di un messaggio inviato da un certo utente (prima riga), dopo di che vogliamo ogni utente con il relativo conteggio dei retweet (seconda riga), ordinando gli utenti per numero di retweet in modo decrescente (terza riga) prendendo solo i primi cinque (parola chiave LIMIT). Poiché abbiamo specificato una funzione di aggregazione (COUNT), Cypher effettua automaticamente un raggruppamento per ID dell’utente: qui il linguaggio è più semplice ed espressivo rispetto a SQL, dove invece dobbiamo specificare prima ciò che vogliamo che la query restituisca e poi su quali valori dobbiamo aggregare.

Altre funzioni di aggregazione supportate in Cypher sono:

• SUM, per calcolare la somma;
• MAX e MIN, per il massimo o il minimo valore nel ragguppamento;
• AVG, per la media;
• STDEV, per la deviazione standard;
• COLLECT, per trasformare una lista di valori in un array.

Quest’ultima funzione è molto interessante perché permette di aggregare più righe in una, cosa non fattibile in SQL (sebbene alcuni RDBMS hanno delle funzioni non standard per raggiungere lo stesso risultato). Ad esempio, per ottenere tutti i follower di un utente:

MATCH (p:User)-[f:FOLLOWS]->(p1:User)
RETURN p.id AS User, COLLECT(p1.id) AS Following

Questa query cerca tutti gli utenti p che seguono tramite la relazione FOLLOWS altri utenti, e restituisce, per ogni utente seguito, la lista dei followers.