Blog Instituta za Matematiku i Informatiku

Studenti informatike PMF-a u Kragujevcu pišu o aktuelnim IT temama

Big Data 

Grafovske baze podataka – Neo4j

Jovica Andric 0 Komentara , , , ,

Iako su relacione baze podataka i dalje najpopularnija vrsta baza podataka, poslednjih godina se pojavilo nekoliko „alternativnih“, takozvanih NoSQL baza podataka. To su baze podataka koje nisu bazirane na relacinom modelu podataka. NoSQL sistemi nastali su iz novih zahteva za većom fleksibilnošću i boljim performansama za smeštanje velike količine podataka. Razlog tome je uglavnom zbog popularnost Interneta i informacionih tehnologija i sve veće količine podataka koja se generiše. Jedna od popularnih vrsta NoSQL baza podataka su grafovske baze podataka, koje će biti tema nastavka ovog teksta.

Šta su grafovske baze podataka?

Graf baze podataka umesto relacionog koriste koncept grafa kao model podataka. Graf je struktura podataka koja se sastoji od čvorova i grana između njih. Sami čvorovi služe sa čuvanje podataka organizovanih kao skup ključ/vrednost parova, dok grane predstavljaju veze odnosno relacije između podataka.

Slika 1 Graf koji predstavlja grupu ljudi
Izvršavanje upita kod ovakvih sistema sastoji se od praćenja putanja, odnosno veza među čvorovima. Na primer, ako nas zanima koga vole Zoranovi prijatelji, možemo jednostavno krenuti od Zorana i tražiti sve veze Prijatelj. U našem slučaju to je samo Žika. Onda od Žike trazimo sve čvorove sa vezom Voli. Na taj način dolazimo do rezultujućeg čvora Ana. Graf baze podataka su vrlo efikasne za ovakve probleme, jer rade sa direktnim vezama među čvorovima.

Neo4j – Zašto i kada ga koristiti?

Neo4j je jedna od vodećih svetskih graf baza podataka otvorenog koda razvijena upotrebom Java tehnologije. Neo4j omogućava:

  • Fleksiblina šema – Nema potrebe za fiksnim modelom podataka. Atributi se mogu dodavati i uklanjati po potrebi.
  • Skalabilnost – Omogućava povećanje broja upisa/čitanja kao i veličine samo baze bez uticaja na brzinu izvršavanja upita.
  • Replikacija – Omogućava replikaciju podataka obezbeđujući time maksimalnu sigurnost i pouzdanost.
  • ACID (Atomicity, Consistency, Isolation, Durability) model transakcija
  • Ugrađena web aplikacija – Upite za kreiranje i pretragu baze možete kreirati kroz jednostavan web interfejs.
  • Jednostavno modeliranje (Whiteboard Friendly) – Za Neo4j se kaže da je whiteboard friendly jer omogućava da model baze napravite jednostavnim crtanjem čvorova i veza.
  • Podržava indekse

Neki od slučajeva kada je najpogodnije koristiti Neo4j bazu podataka:

  • Otkrivanje i prevencija prevara – Velike kompanije gube milijarde dolara godišnje zbog prevaranata koji se služe raznim sofisticiranim trikovima i prevarama kao što su, krađa identiteta, lažno predstavljanje, prevare sa kreditnim karticama i pranje novca. Neo4j pomaže u njihovom otkrivanju. U nastavku teksta demonstiraćemo jedan primer suzbijanja prevare.
  • Praćenje mrežne infrastrukture
  • Sistem za preporuke u realnom vremenu – Posedujete online prodavnicu. Uz pomoć Neo4j baze podataka lako možete korisnicima preporučiti dodatne artikle iz ponude na osnovu onoga što pretražuju.
  • Društvene mreže – Omogućava ubrzavanje kako razvoja tako i same aplikacije.
  • Prava pristupa i kontrola identiteta

Klikom ovde možete pogledati primer za kreiranje sistema za obaveštavanje klijenata putem emaila upotrebom Neo4j baze podataka.

Cypher – Upitni jezik

Cypher je deklarativni upitni jezik inspirisan SQL-om. Omogućava nam da navedemo šta želimo da selektujemo, dodamo, izmenimo ili obrišemo iz grafa bez eksplicitnog navođenja načina na koji če to biti učinjeno.

MATCH (node1:Label1)-[:relation]->(node2:Label2)
WHERE node1.propertyA = {value}
RETURN node2.propertyA, node2.propertyB

Slika 2 – Sličnost cypher upita sa vizuelnom repreentacijom veze između dva podatka

Kreiranje čvorova

CREATE (you:Person {name:"Jovica"}) RETURN you

Ovaj upit kreira novi čvor označen kao you tipa Person i sadrži podatak sa ključem name čija je vrednost „Jovica“.

Kreiranje relacija

MATCH (you:Person {name:"Jovica"})
CREATE (you)-[like:LIKE]->(neo:Database
{name:"Neo4j" })
RETURN you,like,neo

Naredbom MATCH pronalazimo podatak tipa Person kome se vrednost ključa poklapa sa zadatom vrednosti „Jovica“ i dodeljuje mu oznaku you preko koje će se referincirati na taj podatak. Naredbom CREATE kreira se relacija LIKE ka drugom podatku tipa Database sa podatkom koji za ključ name ima vrednost „Neo4j“.

MATCH (you:Person {name:"Jovica"})
FOREACH (name in ["Pera","Zika","Ana","Laza","Dragan"] |
CREATE (you)-[:FRIEND]->(:Person {name:name}))

Ova komanda kreira nove podatke tipa Person sa imenima navedenim u FOREACH delu i prema svima kreira vezu tipa FRIEND.

Pretraga prijatelja

MATCH (you {name:"Jovica"})-[:FRIEND]->(yourFriends)
RETURN you, yourFriends

Ovaj upit kao rezultat vraća sve podatke prema kojima postoji veza tipa FRIEND od podatka kome za ključ name odgovara zadata vrednost „Jovica“.

Kreiranje prijatelja našeg prijatelja

MATCH (neo:Database {name:"Neo4j"})
MATCH (ana:Person {name:"Ana"})
CREATE (ana)-[:FRIEND]->(:Person:Expert
{name:"Dragana"})-[:WORKED_WITH]->(neo)

Nalaženje najkraćeg puta

MATCH (you {name:"Jovica"})
MATCH (expert)-[:WORKED_WITH]->(db:Database
{name:"Neo4j"})
MATCH path = shortestPath( (you)-[:FRIEND*..5]- (expert) )
RETURN db,expert,path

Ovaj upit prolazi rekurzivno kroz sve naše prijatelje maksimalno do dubine 5 zaključno sa osobom koja je expert.

Kao što možemo videti Neo4j ima ugradjenu funkciju shortestPath koja u pozadini koristi Dijkstra algoritam za pronalaženje najkraćeg puta između čvorova. U poređenju sa relacionim bazama podataka, ovakva pretraga kod graf baza podataka traje neuporedivo kraće.

Brisanje čvora

MATCH (n:Useless)
DELETE n

Brisanje relacija

MATCH (n { name: 'Andrew' })-[r:FRIEND]->()
DELETE r

Brisanje čvora i svih njegovih relacija

MATCH (n { name: 'Andrew' }) 
DETACH DELETE n

Izmena i dodavanje atributa

MATCH (n { name: 'Jovica' })
SET n.surname = 'Andrić' RETURN n

Uklanjanje atributa

MATCH (andres { name: 'Andres' })
REMOVE andres.age
RETURN andres

Kreiranje indeksa

CREATE INDEX ON :Person(firstname)

Kreiranje kompozitnog indeksa

CREATE INDEX ON :Person(firstname,
surname)

Brisanje indeksa

DROP INDEX ON :Person(firstname)

Izlistavanje svih indeksa

CALL db.indexes

Primer upotrebe Neo4j baze podataka za otkrivanje prevaranata

Jedan od načina na koji se problem sa prevarantima manifestuje prati sledeći scenario. Grupa prevaranata kreira u nekoj banci veliki broj bankovnih računa. Sve račune otvaraju koristeći kombinacije imena, prezimena, brojeva telefona, adresa, brojeva socijalnog osiguranja itd. Nakon otvaranja, račune koriste normalno kako niko ne bi posumnjao na prevaru, što podrazumeva redovne prilive i odlive novca sa računa, javljanje na pozive bankarskih službenika, dostavljanje potrebne dokumentacije, primanje pošte koju banka šalje, itd. Nakon nekog vremena, svi računi odlaze u dozvoljeni minus i nestaju. Više se ne javljaju i banka ne može da stupi u kontakt sa njima. Dug se otpisuje i banka gubi ogromnu količinu novca.

Kako bismo demonstrirali način na koji Neo4j pomaže u suzbijanju ovakvog problema potrebno je pripremiti radno okruženje.

To je moguće odraditi preko online alata ili instalacijom Neo4j paketa na lokalnu mašinu. Uputstvo za instalaciju možete pronaći ovde

Nakon što je radno okruženje podešeno, potrebno je učitati testni set podataka.

To možete uraditi sledećom komandom:

// Create account holders
CREATE (accountHolder1:AccountHolder {
 FirstName: "John",
 LastName: "Doe",
 UniqueId: "JohnDoe" })

CREATE (accountHolder2:AccountHolder {
 FirstName: "Jane",
 LastName: "Appleseed",
 UniqueId: "JaneAppleseed" })

CREATE (accountHolder3:AccountHolder {
 FirstName: "Matt",
 LastName: "Smith",
 UniqueId: "MattSmith" })

// Create Address
CREATE (address1:Address {
 Street: "123 NW 1st Street",
 City: "San Francisco",
 State: "California",
 ZipCode: "94101" })

// Connect 3 account holders to 1 address
CREATE (accountHolder1)-[:HAS_ADDRESS]->(address1),
 (accountHolder2)-[:HAS_ADDRESS]->(address1),
 (accountHolder3)-[:HAS_ADDRESS]->(address1)

// Create Phone Number
CREATE (phoneNumber1:PhoneNumber { PhoneNumber: "555-555-5555" })

// Connect 2 account holders to 1 phone number
CREATE (accountHolder1)-[:HAS_PHONENUMBER]->(phoneNumber1),
 (accountHolder2)-[:HAS_PHONENUMBER]->(phoneNumber1)

// Create SSN
CREATE (ssn1:SSN { SSN: "241-23-1234" })

// Connect 2 account holders to 1 SSN
CREATE (accountHolder2)-[:HAS_SSN]->(ssn1),
 (accountHolder3)-[:HAS_SSN]->(ssn1)

// Create SSN and connect 1 account holder
CREATE (ssn2:SSN { SSN: "241-23-4567" })<-[:HAS_SSN]-(accountHolder1)

// Create Credit Card and connect 1 account holder
CREATE (creditCard1:CreditCard {
 AccountNumber: "1234567890123456",
 Limit: 5000, Balance: 1442.23,
 ExpirationDate: "01-20",
 SecurityCode: "123" })<-[:HAS_CREDITCARD]-(accountHolder1)

// Create Bank Account and connect 1 account holder
CREATE (bankAccount1:BankAccount {
 AccountNumber: "2345678901234567",
 Balance: 7054.43 })<-[:HAS_BANKACCOUNT]-(accountHolder1)

// Create Credit Card and connect 1 account holder
CREATE (creditCard2:CreditCard {
 AccountNumber: "1234567890123456",
 Limit: 4000, Balance: 2345.56,
 ExpirationDate: "02-20",
 SecurityCode: "456" })<-[:HAS_CREDITCARD]-(accountHolder2)

// Create Bank Account and connect 1 account holder
CREATE (bankAccount2:BankAccount {
 AccountNumber: "3456789012345678",
 Balance: 4231.12 })<-[:HAS_BANKACCOUNT]-(accountHolder2)

// Create Unsecured Loan and connect 1 account holder
CREATE (unsecuredLoan2:UnsecuredLoan {
 AccountNumber: "4567890123456789-0",
 Balance: 9045.53,
 APR: .0541,
 LoanAmount: 12000.00 })<-[:HAS_UNSECUREDLOAN]-(accountHolder2)

// Create Bank Account and connect 1 account holder
CREATE (bankAccount3:BankAccount {
 AccountNumber: "4567890123456789",
 Balance: 12345.45 })<-[:HAS_BANKACCOUNT]-(accountHolder3)

// Create Unsecured Loan and connect 1 account holder
CREATE (unsecuredLoan3:UnsecuredLoan {
 AccountNumber: "5678901234567890-0",
 Balance: 16341.95, APR: .0341,
 LoanAmount: 22000.00 })<-[:HAS_UNSECUREDLOAN]-(accountHolder3)

// Create Phone Number and connect 1 account holder
CREATE (phoneNumber2:PhoneNumber {
 PhoneNumber: "555-555-1234" })<-[:HAS_PHONENUMBER]-(accountHolder3)

RETURN *

Rezultat izvršavanja ovog upita prikazan je na Slici 3.

Slika 3 – Testni podaci

Nakon što smo učitali testne podatke, treba da nađemo sve vlasnike računa kojima se neki podaci poklapaju.

To ćemo učiniti sledećim upitom:

MATCH (accountHolder:AccountHolder)- []->(contactInformation)
WITH contactInformation, count(accountHolder) AS RingSize
   MATCH (contactInformation) 1
   RETURN AccountHolders AS FraudRing,
   labels(contactInformation) AS
   ContactType,
   RingSize
   ORDER BY RingSize DESC

Sada kada smo našli sve vlasnike računa koji su potencijalni prevaranti, treba da otkrijemo koliki maksimalan gubitak svaki od njih donosi ukoliko načini prevaru.

To ćemo saznati čim izvršimo sledeći upit.

MATCH (accountHolder:AccountHolder)-[]->(contactInformation)
WITH contactInformation,
count(accountHolder) AS RingSize
MATCH (contactInformation)(unsecuredAccount)
WITH collect(DISTINCT accountHolder.UniqueId) AS AccountHolders,
    contactInformation, RingSize,
    SUM(CASE type(r)
    WHEN 'HAS_CREDITCARD' THEN unsecuredAccount.LIMIT
    WHEN 'HAS_UNSECUREDLOAN' THEN
    unsecuredAccount.Balance
    ELSE 0
    END) AS FinancialRisk
    WHERE RingSize > 1
    RETURN AccountHolders AS FraudRing,
    labels(contactInformation) AS ContactType,
    RingSize,
    round(FinancialRisk) AS FinancialRisk
    ORDER BY FinancialRisk DESC

Krajnji rezultat ovog našeg primera može se prikazati u obliku sledeće tabele

Slika 4 – Tabelarni prikaz svih potencijalnih prevaranata i najvećih mogućih gubitaka.

Literatura

Autor: Jovica Andric

Možda Vam se svidi i

Elasticsearch

Tijana Ristovic 0

Apache CouchDB – Deo II

Andreja Vulovic 0

MultiValue Databases na primeru ArrayDB Deo II

Djordje Mitrovic 0