public void m(){
n(this);
}
public static n(Object obj){
if(obj==null){
doSomething();
}
}
czyli jak zostać bohaterem swoich danych w Neo4j
public void m(){
n(this);
}
public static n(Object obj){
if(obj==null){
doSomething();
}
}
public void m(){
if(this==null){
doSomething();
}
}
public void m(){
if(false){
doSomething();
}
}
public void m(){
}
-XX:+UseFastEmptyMethods
czyli jak zostać bohaterem swoich danych w Neo4j
Jarek Pałka
Allegro.tech, obecnie tajny projekt o którym nie mogę mówić
JDD/4Developers, naczelny sprawca zamieszania czyli człowiek od kłopotów,
a tak poza tym jeśli cokolwiek ma związek z JVM i HotSpot, bytecode’em, parserami, językami programowania na JVM oraz technikami JIT, wcześniej czy później się tym zainteresuje :)
były architekt, manager, sysadmin i człowiek od wydajności,
Neo4j, obecnie modelowanie rzeczywistości w grafach, w przyszłości rozbudowa parsera Cypher, lepsze narzędzia do importu danych
OpenJDK kontrybutor, może w przyszłym życiu
Python3 na JVM, ale to już na emeryturze :)
graf G składa się z dwóch zbiorów – V oraz E, przy czym V jest niepustym zbiorem, którego elementy nazywane są wierzchołkami, a E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami
graf prosty
graf skierowany
graf mieszany
graf z wagami
hipergraf
gęstość grafu - stosunek ilości wierzchołków do krawędzi
droga/ścieżka - kolekcja wierzchołków lub krawędzi
cykl - kolekcja połączonych wierzchołków, gdzie pierwszy element jest taki sam jak ostatni
klika - podzbiór wierzchołków, gdzie istnieje połączenie pomiędzy każdym z każdym
stopień wierzchołka - ilość krawędzi wychodzących z wierzchołka
algorytmy A*, Dijkstra, Bellman-Ford, Floyd-Warshall,
przeszukiwania grafu wgłąb i wszerz,
"clusters"
"connected components"
"small worlds"
“A Graph — records data in › Nodes — which have › Properties”
“Nodes — are organized by › Relationships — which also have › Properties”
“Nodes — are grouped by › Labels — into › Sets”
Neo4j to baza danych a nie nakładka na inną bazę danych
Własny mechanizm przechowywania danych, zooptymalizowany pod strukturę grafów
Dostępne wsparcie dla następujących modeli:
embedded
serwer (REST)
serwer (binary protocol, prace ciągle trwają)
HA (edycja "enterprise")
węzły ("node")
identyfikator
etykiety ("labels")
własności
relacje ("relationship")
typ relacji ("relationship type")
kierunek ("direction")
własności
schemat ("schema")
indeksy ("index")
ograniczenia ("constraints")
własności ("properties")
prymitywy Java (long, int, float, etc.)
łańcuchy znakowe
tablice powyższych
*Looks like SQL, feels like pattern-matching*
MATCH (n:Label) RETURN n;
MATCH (n)-[:LIKES]->m return m;
MATCH (n)-[r:LIKES]->m return r;
(a)-->(b)
(a)-->(b)<--(c)
(a:User)-->(b)
(a:User:Admin)-->(b)
(a)-[r:REL_TYPE]->(b)
(a)-[*2]->(b)
(a)-[*3..5]->(b)
Wzorce dopasowania, są wyrażeniami, które zwracają kolekcję węzłów i relacji (ścieżek). Wszędzie tam gdzie możesz użyć wyrażenia (klauzula 'WHERE', 'RETURN', 'WITH', etc.), możesz też użyć wzorców dopasowań.
MATCH a-[:REL]-b WHERE NOT b-[:REL]-c RETURN b;
MATCH a-[:REL]-b RETURN a,b-[:REL]-c;
MATCH a-[:REL]-b WITH a, b-[:REL]-c RETURN a, count(distinct c);
RETURN [0,1,2,3,4,5,6,7,8,9] AS collection
RETURN range(0,10)[3]
RETURN length(range(0,10)[0..3])
RETURN [x IN range(0,10) WHERE x % 2 = 0 | x^3] AS result
RETURN [x IN range(0,10) WHERE x % 2 = 0 | x^3] AS result;
WHERE a.name='Alice' AND b.name='Daniel' AND
ALL (x IN nodes(p) WHERE x.age > 30);
WHERE a.name='Eskil' AND ANY (x IN a.array WHERE x = "one");
WHERE n.name='Alice' AND NONE (x IN nodes(p) WHERE x.age = 25);
WHERE n.name='Alice' AND
SINGLE (var IN nodes(p) WHERE var.eyes = "blue");
MATCH (n)
WHERE EXISTS(n.name)
RETURN n.name AS name, EXISTS((n)-[:MARRIED]->()) AS is_married
MATCH p = ((a)--(b)) RETURN nodes(p)
MATCH p = ((a)--(b)) RETURN relationships(p)
MATCH p = ((a)-[:RAILS]-(b)) UNWIND nodes(p) AS n return DISTINCT n;
Klauzula 'WITH' umożliwia przetwarzanie zapytań z w potokach, gdzie wynik poprzedniego zapytania jest przekazywany do następnego, myślmy o tym jak o '|' w *NIX.
MATCH (david { name: "David" })-(otherPerson)->()
WITH otherPerson, count(*) AS foaf
WHERE foaf > 1
RETURN otherPerson
Ponieważ Cypher jest składniowo, młodszym bratem SQL, wpadniesz w pułapkę pisania zapytań relacyjnych, które będą wykorzystywać iloczyn kartezjański.
To nie jest błogosławiona droga grafu.
Na nośniku USB lub też dla tych połączeniem:
prezentacja
dane do 3 modeli z którymi będziemy pracować
dokumentacja neo4j
neo4j-community-2.2.3
konsola neo4j-shell
konsola interaktywna
Zacznijmy od prostego modelu szkoleń, trenerów i umiejętności.
CREATE
(t0:Training {title : "Archeologia kodu a architektura" }),
(n0:Trainer { name : "Jarosław Pałka"}),
(s0:Skill { name : "Git" }),
(s1:Skill { name : "SonarQube"}),
t0-[:AUTHORED_BY]->n0,
t0-[:REQUIRES]->s0,
t0-[:INTRODUCES]->s1;
Znajdź wszystkie szkolenia przygotowane przez danego trenera.
Znajdź najszybszą ścieżkę szkoleń o danej umiejętności do innej docelowej umiejętności.
Podpowiedź: Cypher oferuje funkcję 'shortestPath', która zwraca najkrótszą ścieżkę.
reduce
na ratunekMATCH (a:Skill {name:"Java"})<-[:REQUIRES]-(b:Training)
MATCH (c:Training)-[:INTRODUCES]->(d:Skill {name:"REST"})
MATCH p=allShortestPaths(b-[rels:REQUIRES|INTRODUCES*]-c)
WHERE length(p)%2=0 AND ALL(idx in range(0, length(p)-2,2) WHERE type(rels[idx])="INTRODUCES" AND type(rels[idx+1]) = "REQUIRES")
RETURN p
W tym modelu, naszym grafem będzie skrzynka pocztowa. Poszukamy węzłów i krawędzi pośród:
wiadomości email
osób wysyłających i odbierających
Aby pracować z tym modelem, należy skopiować zawartość katalogu datasets/mails.workshop. Zawiera on zanimizowane maile z mojej skrzynki mailowej, celem nadanie ćwiczeniu więcej realizmu.
A poniżej model grafu po zaimportowaniu zawartości skrzynki pocztowej.
Wyszukajmy wszystkie maile które są odpowiedzią na innego maila.
Podpowiedź: węzły z etykietą `Message` posiadają pola `Message-Id` oraz `In-Reply-To`.
Znajdźmy najdłuższy wątek mailowy.
Podpowiedź: na początek spróbuj zidentyfikować te wiadomości, które są początkiem i końcem wątku
Cypher umożliwia analizę planu zapytań, w celu ich optymalizacji.
EXPLAIN
MATCH (p:Person { name:"Tom Hanks" })
RETURN p
PROFILE
MATCH (p:Person { name:"Tom Hanks" })
RETURN p
Sugestia: Bądź jak najbardziej specyficzny w swych zapytaniach, wykorzystuj etykiety i typy relacji.
Prawdopodobnie napisaliście to zapytanie myśląc SQLem i to jak najbardziej w porządku. Zobaczymy teraz co tak naprawdę potrafi Neo4j i Cypher, czyli czas na utworzenie nowych relacji.
CREATE INDEX ON :Message(`In-Reply-To`);
CREATE INDEX ON :Message(`Message-Id`);
Sprawdźmy teraz status indeksu
neo4j-sh (?)$ schema
Indexes
ON :Message(In-Reply-To) ONLINE
ON :Message(Message-Id) ONLINE
No constraints
Tym razem wyszukajmy najdłuższego wątku, korzystając z nowych krawędzi.
Podpowiedź: Wzorce w Cypher mogą być traktowane jak wyrażenia, nie pasujący wzorzec zwraca pusty rezultat
Spróbujmy odnaleźć znajomych w naszej skrzynce, czyli "let’s go social".
Poszukajmy grup znajomych w naszym grafie.
Podpowiedź: Uwaga na węzeł, który jest znajomym wszystkich, czyli właściciel skrzynki pocztowej, węzeł o id=2. Możemy go usunąc, lub dla zachowania struktury grafu, nadać mu inną etykietę.
Definicja: clusters - tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes
Dwie podstawowe techniki wyznaczania klastrów to "Global clustering coefficient" oraz "Local clustering coefficient" (https://en.wikipedia.org/wiki/Clustering_coefficient).
Spróbujmy policzyć współczynnik techniką "local clustering coefficient".
Współczynnik ten jest liczony jako prawdopodobieństwo że dwa sąsiadujące losowe wybrane węzły także są ze sobą połączone.
\$C_i=(|{e_(jk) : v_j,v_k in N_i,e_(jk) in E}|)/(k_i(k_i-1))\$
gdzie sąsiedztwo \$N_i\$ określamy jako:
\$N_i={v_j : e_(ij) in E vv e_(ji) in E}\$
i \$k_i\$ to liczba sąsiadów danego węzła.
Wystarczy policzyć ilość bezpośrednich sąsiadów, i ilość relacji pomiędzy nimi.
Definicja: strongly connected components - a graph is said to be strongly connected if every vertex is reachable from every other vertex
Dwa podstawowe algorytmy to algorytm Kosaraju oraz algorytm Tarjan. Ciągle kombinuję jak zapisać to w Cypher :), dla wytrwałych nagroda :)
algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := 0
S := empty
for each v in V do
if (v.index is undefined) then
strongconnect(v)
end if
end for
function strongconnect(v)
// Set the depth index for v to the smallest unused index
v.index := index
v.lowlink := index
index := index + 1
S.push(v)
v.onStack := true
// Consider successors of v
for each (v, w) in E do
if (w.index is undefined) then
// Successor w has not yet been visited; recurse on it
strongconnect(w)
v.lowlink := min(v.lowlink, w.lowlink)
else if (w.onStack) then
// Successor w is in stack S and hence in the current SCC
v.lowlink := min(v.lowlink, w.index)
end if
end for
// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
start a new strongly connected component
repeat
w := S.pop()
w.onStack := false
add w to current strongly connected component
until (w = v)
output the current strongly connected component
end if
end function
W tym celu wykorzystamy bazę MovieLens, tworzoną w ramach projektu GroupLens Research, przy Uniwersytecie Stanu Minnesota. Baza zawiera dane o filmach i rekomendacjach, wykorzystując system ocen punktowych w skali od 1-5.
LOAD CSV FROM 'file:data.csv' AS line FIELDTERMINATOR '|'
WITH line[0] AS firstname, line[0] AS lastname
CREATE (:Person {firstname : firstname, lastname : lastname});
LOAD CSV WITH HEADERS FROM 'file:data.csv' AS line
CREATE (:Person {firstname : line.firstname, lastname : line.lastname});
Rekomendacje z wykorzystaniem algorytmu "skip jump", jest to technika oparta o prostą obserwację. Jeśli dwie osoby mają przynajmniej jedną relację do tego samego węzła, w tym przypadku filmu, to oznacza że istnieje wysokie prawdopodobieństwo, że osoba ta polubi także pozostałe filmy polubione przez te drugą osobę.
Rekomendacje z wykorzystaniem techniki "hammock", to rozszerzenie techniki "skip jump", która bazuje na więcej niż jednym elemencie wspólnym dla dwóch wybranych węzłów.
Kolejnym rozwinięciem tej techniki, jest szukanie rekomendacji, gdy dwa lub więcej elementów są tego samego typy/kategorii, np. gatunek filmowy.
Podpowiedź: W pliku u.item zawarte są informacje o gatunku filmowym, spróbujmy je zaimportować do naszej bazy danych.
A teraz coś bardziej zakręconego, czyli collaborative filtering, k-nearest neighbors i cosine similarity.
\$cos(theta)=(A*B)/(|\ |A|\ |*|\ |B|\ |)=(sum_(i=1)^n A_i xx B_i)/(sqrt(sum_(i=1)^n (A_i)^2) * sqrt(sum_(i=1)^n (B_i)^2))\$
różnej maści rozszerzenia, geo, rekomendacje czy modelowanie czasu, znajdziecie je na GraphAware extensions
teoria grafów, czyli od zera do bohatera, jedno z lepszych i bardziej dostępnych opracowań to Graph Theory by Keijo Ruohonen
algorytmy rekomendacji z wykorzystaniem grafów, zostały opisane w Studying Recommendation Algorithms by Graph Analysis
czytać, testować, sprawdzać co inni wyczyniają z grafami, czyli GraphGist Project
raptem 857 strony "Social Network Analysis: Methods and Applications" autorstwa Stanley Wasserman (nie przebrnąłem)