Grafdatabase - Graph database

I databehandling er en grafdatabase ( GDB ) en database som bruker grafstrukturer for semantiske spørringer med noder , kanter og egenskaper for å representere og lagre data. Et sentralt konsept for systemet er grafen (eller kanten eller forholdet ). Grafen relaterer dataelementene i butikken til en samling noder og kanter, kantene representerer forholdet mellom nodene. Forholdene gjør at data i butikken kan kobles direkte sammen og i mange tilfeller hentes med en operasjon. Grafdatabaser holder forholdet mellom data som en prioritet. Det er raskt å spørre relasjoner fordi de alltid lagres i databasen. Forhold kan intuitivt visualiseres ved hjelp av grafdatabaser, noe som gjør dem nyttige for tungt sammenkoblede data.

Grafdatabaser kalles vanligvis en NoSQL -database - noe som betyr at tilnærmingen til lagring, spørring og beskrivelse av disse datastrukturer skiller seg vesentlig fra en tradisjonell relasjonsdatabase . Mens grafmodellen eksplisitt angir avhengighetene mellom datanoder, kobler relasjonsmodellen og andre NoSQL -databasemodeller dataene ved implisitte forbindelser. Med andre ord er relasjoner en førsteklasses innbygger i en grafdatabase og kan merkes, rettes og gis egenskaper. Dette sammenlignes med relasjonelle tilnærminger der disse forholdene er underforstått og må reifiseres ved kjøretid. Grafdatabaser ligner nettverksmodelldatabaser fra 1970-tallet ved at begge representerer generelle grafer, men nettverksmodelldatabaser opererer på et lavere abstraksjonsnivå og mangler enkel krysning over en kjede av kanter.

Den underliggende lagringsmekanismen for grafdatabaser kan variere. Noen er avhengige av en relasjonsmotor og "lagrer" grafdataene i en tabell (selv om en tabell er et logisk element, pålegger derfor denne tilnærmingen et annet abstraksjonsnivå mellom grafdatabasen, grafdatabasestyringssystemet og de fysiske enhetene der dataene er faktisk lagret). Andre bruker en nøkkelverdi-butikk eller dokumentorientert database for lagring, noe som gjør dem til iboende NoSQL-strukturer.

Fra og med 2021 har det ikke blitt tatt i bruk et universelt grafisk spørrespråk på samme måte som SQL var for relasjonsdatabaser, og det finnes en lang rekke systemer, oftest tett knyttet til ett produkt. Noen tidlige standardiseringsarbeider fører til spørrespråk med flere leverandører som Gremlin , SPARQL og Cypher . I september 2019 ble et forslag til et prosjekt for å lage et nytt standardgrafsøksspråk (ISO/IEC 39075 Information Technology - Database Language - GQL) godkjent av medlemmer av ISO/IEC Joint Technical Committee 1 (ISO/IEC JTC 1). GQL er ment å være et deklarativt databasesøksspråk, som SQL. I tillegg til å ha grensesnitt for spørrespråk, får du tilgang til noen grafdatabaser via programmeringsgrensesnitt (API).

Grafdatabaser er forskjellige fra grafberegningsmotorer. Grafdatabaser er teknologier som er oversettelser av de relasjonelle online transaksjonsbehandlingsdatabasene (OLTP). På den annen side brukes grafberegningsmotorer i online analytisk behandling (OLAP) for masseanalyse. Grafdatabaser vakte betydelig oppmerksomhet på 2000-tallet, på grunn av suksessene til store teknologiselskaper med å bruke proprietære grafdatabaser, sammen med introduksjonen av åpen kildekode- grafdatabaser.

En studie konkluderte med at et RDBMS var "sammenlignbart" i ytelse med eksisterende grafanalyse -motorer ved utføring av grafiske forespørsler.

Historie

På midten av 1960-tallet, navigasjons databaser slik som IBM 's IMS understøttet tre -lignende strukturer i sin hierarkiske modell , men den strenge trestrukturen kan omgås med virtuelle poster.

Grafstrukturer kan være representert i nettverksmodelldatabaser fra slutten av 1960 -tallet. CODASYL , som hadde definert COBOL i 1959, definerte Network Database Language i 1969.

Merkede grafer kan være representert i grafdatabaser fra midten av 1980-tallet, for eksempel den logiske datamodellen.

Kommersielle objektdatabase (ODBMSs) dukket opp i begynnelsen av 1990. I 2000 publiserte Object Data Management Group et standardspråk for å definere objekt- og relasjons (graf) strukturer i sin ODMG'93 -publikasjon.

Flere forbedringer av grafdatabaser dukket opp på begynnelsen av 1990 -tallet, og akselererte på slutten av 1990 -tallet med bestrebelser på å indeksere websider.

På midten til slutten av 2000-tallet ble kommersielle grafdatabaser med ACID- garantier som Neo4j og Oracle Spatial and Graph tilgjengelig.

På 2010 -tallet ble kommersielle ACID -grafdatabaser som kan skaleres horisontalt tilgjengelige. Videre brakte SAP HANA in-memory og kolonneteknologier til å tegne databaser. Også i 2010-tallet, multi-modell databaser som støttes graf modeller (og andre modeller som relasjonsdatabase eller dokument orientert database ) ble tilgjengelig, slik som OrientDB , ArangoDB , og Marklogic (ved å starte med sin 7.0-versjon). I løpet av denne tiden har grafdatabaser av forskjellige typer blitt spesielt populære med analyser av sosiale nettverk med bruk av sosiale medier.

Bakgrunn

Grafdatabaser bruker noder, egenskaper og kanter.

Grafdatabaser skildrer dataene slik de blir sett på konseptuelt. Dette oppnås ved å overføre dataene til noder og dets relasjoner til kanter.

En grafdatabase er en database som er basert på grafteori . Den består av et sett med objekter, som kan være en node eller en kant.

• Noder representerer enheter eller forekomster som mennesker, virksomheter, kontoer eller andre elementer som skal spores. De tilsvarer omtrent en post, relasjon eller rad i en relasjonsdatabase eller et dokument i en dokumentlagringsdatabase.
• Kanter , også kalt grafer eller relasjoner , er linjene som kobler noder til andre noder; representerer forholdet mellom dem. Meningsfulle mønstre dukker opp når man undersøker forbindelser og sammenkoblinger mellom noder, egenskaper og kanter. Kantene kan enten være rettet eller ikke -rettet. I en ikke -styrt graf har en kant som forbinder to noder en enkelt betydning. I en rettet graf har kantene som forbinder to forskjellige noder forskjellige betydninger, avhengig av retningen. Kanter er nøkkelbegrepet i grafdatabaser, som representerer en abstraksjon som ikke er implementert direkte i en relasjonsmodell eller en dokumentlagermodell .
• Egenskaper er informasjon knyttet til noder. For eksempel, hvis Wikipedia var en av nodene, kan det være knyttet til egenskaper som nettsted , referansemateriale eller ord som starter med bokstaven w , avhengig av hvilke aspekter av Wikipedia som er relevante for en gitt database.

Grafmodeller

Merket eiendom-graf

En grafisk modell med merket egenskap representeres av et sett med noder, relasjoner, egenskaper og etiketter. Begge datanoder og deres relasjoner er navngitt og kan lagre egenskaper representert av nøkkel -verdi -par . Noder kan merkes for å være gruppert. Kantene som representerer relasjonene har to kvaliteter: de har alltid en startnode og en sluttnode, og er rettet; gjøre grafen til en rettet graf . Forhold kan også ha egenskaper. Dette er nyttig for å gi ytterligere metadata og semantikk til relasjoner mellom nodene. Direkte lagring av relasjoner gir en konstant-tid traversering .

Ressursbeskrivelsesramme (RDF)

Et eksempel på RDF -graf

I en RDF -grafmodell representeres tillegg av informasjon hver med en egen node. Tenk deg for eksempel et scenario der en bruker må legge til et navnegenskap for en person representert som en distinkt node i grafen. I en merket-egenskap graf-modell, ville dette bli gjort med et tillegg av en navnegenskap i noden til personen. I en RDF må brukeren imidlertid legge til en egen node som kalles å hasNamekoble den til den opprinnelige personnoden. Spesielt består en RDF -grafmodell av noder og buer. En RDF -grafnotasjon eller en setning representeres av: en node for motivet, en node for objektet og en bue for predikatet. En node kan stå tom, bokstavelig og/eller identifiseres av en URI . En bue kan også identifiseres av en URI. En bokstav for en node kan være av to typer: vanlig (uskrevet) og skrevet. En vanlig bokstav har en leksikalsk form og eventuelt en språkmerke. En skrevet bokstav består av en streng med en URI som identifiserer en bestemt datatype. En tom node kan brukes til å nøyaktig illustrere dataenes tilstand når dataene ikke har en URI .

Egenskaper

Grafdatabaser er et kraftig verktøy for graflignende spørringer. For eksempel, beregne den korteste banen mellom to noder i grafen. Andre graflignende forespørsler kan utføres over en grafdatabase på en naturlig måte (for eksempel grafdiameterberegninger eller samfunnsdeteksjon).

Grafer er fleksible, noe som betyr at det lar brukeren sette inn nye data i den eksisterende grafen uten tap av applikasjonsfunksjonalitet. Det er ikke nødvendig for designeren av databasen å planlegge omfattende detaljer om databasens fremtidige brukstilfeller.

Oppbevaring

Den underliggende lagringsmekanismen for grafdatabaser kan variere. Noen er avhengige av en relasjonsmotor og "lagrer" grafdataene i en tabell (selv om en tabell er et logisk element, pålegger derfor denne tilnærmingen et annet abstraksjonsnivå mellom grafdatabasen, grafdatabasestyringssystemet og de fysiske enhetene der dataene er faktisk lagret). Andre bruker en nøkkelverdi-butikk eller dokumentorientert database for lagring, noe som gjør dem til iboende NoSQL- strukturer. En node vil bli representert som alle andre dokumentlagre, men kanter som forbinder to forskjellige noder har spesielle attributter inne i dokumentet; a _fra og _til attributter.

Indeksfri tilknytning

Datasøkingsytelse er avhengig av tilgangshastigheten fra en bestemt node til en annen. Fordi indeks -fri tilstøter håndhever nodene for å ha direkte fysisk RAM- adresser og fysisk peke på andre nabonoder, resulterer det i en rask gjenfinning. Et innfødt grafsystem med indeksfri tilknytning trenger ikke å bevege seg gjennom noen annen type datastrukturer for å finne koblinger mellom nodene. Direkte relaterte noder i en graf lagres i hurtigbufferen når en av nodene er hentet, noe som gjør dataoppslag enda raskere enn første gang en bruker henter en node. Imidlertid koster en slik fordel en pris. Indeksfri tilknytning ofrer effektiviteten til spørringer som ikke bruker grafoverganger . Innfødte grafdatabaser bruker indeksfri tilknytning til å behandle CRUD- operasjoner på lagrede data.

Graftyper

Det er flere typer grafer som kan kategoriseres. Gartner foreslår de fem brede kategoriene av grafer:

• Sosial graf : dette handler om forbindelsene mellom mennesker; eksempler inkluderer Facebook , Twitter og ideen om seks grader av separasjon
• Intensjonsgraf: dette omhandler resonnement og motivasjon.
• Forbruksgraf: også kjent som "betalingsgrafen", forbruksgrafen er sterkt brukt i detaljhandelen. Netthandelsselskaper som Amazon, eBay og Walmart bruker forbruksgrafer for å spore forbruket til enkeltkunder.
• Interestgraf : dette kartlegger en persons interesser og blir ofte supplert med en sosial graf. Den har potensial til å følge den forrige revolusjonen av weborganisasjon ved å kartlegge nettet etter interesse i stedet for å indeksere websider.
• Mobildiagram: dette er bygget på mobildata. Mobildata i fremtiden kan inkludere data fra Internett, applikasjoner, digitale lommebøker, GPS og Internet of Things (IoT) -enheter.

Sammenligning med relasjonsdatabaser

Siden Edgar F. Codds oppgave fra 1970 om relasjonsmodellen , har relasjonsdatabaser vært de facto industristandarden for store datalagringssystemer. Relasjonsmodeller krever et strengt skjema og datanormalisering som skiller data i mange tabeller og fjerner dupliserte data i databasen. Data er normalisert for å bevare datakonsistensen. Og støtte ACID -transaksjoner . Dette pålegger imidlertid begrensninger for hvordan forhold kan spørres.

En av relasjonsmodellens designmotivasjoner var å oppnå en rask rad-for-rad-tilgang. Problemer oppstår når det er behov for å danne komplekse forhold mellom de lagrede dataene. Selv om relasjoner kan analyseres med relasjonsmodellen, kreves komplekse spørringer som utfører mange joinoperasjoner på mange forskjellige attributter over flere tabeller. Når du arbeider med relasjonsmodeller, bør også fremmede nøkkelbegrensninger tas i betraktning når du henter relasjoner, noe som forårsaker ekstra omkostninger.

Sammenlignet med relasjonsdatabaser er grafdatabaser ofte raskere for assosiative datasett og kartlegger mer direkte til strukturen i objektorienterte applikasjoner. De kan skalere mer naturlig til store datasett ettersom de vanligvis ikke trenger sammenføyningsoperasjoner , noe som ofte kan være dyrt. Siden de er mindre avhengige av et stivt skjema, blir de markedsført som mer egnet for å administrere ad hoc og endrede data med utviklende skjemaer.

Motsatt er relasjonsdatabasehåndteringssystemer vanligvis raskere til å utføre den samme operasjonen på et stort antall dataelementer, noe som tillater manipulering av dataene i dens naturlige struktur. Til tross for grafdatabasernes fordeler og nylige popularitet i forhold til relasjonsdatabaser, anbefales det at selve grafmodellen ikke skal være den eneste grunnen til å erstatte en eksisterende relasjonsdatabase. En grafdatabase kan bli relevant hvis det er bevis for ytelsesforbedring etter størrelsesordener og lavere latens.

Eksempler

Den relasjonsmodellen samler data sammen ved hjelp av informasjon i dataene. For eksempel kan man se etter alle "brukerne" hvis telefonnummer inneholder retningsnummeret "311". Dette vil bli gjort ved å søke i utvalgte datalagre eller tabeller , se i de valgte telefonnummerfeltene etter strengen "311". Dette kan være en tidkrevende prosess i store tabeller, så relasjonsdatabaser tilbyr indekser , som gjør at data kan lagres i en mindre undertabell, som bare inneholder de valgte dataene og en unik nøkkel (eller primærnøkkel) for posten. Hvis telefonnumrene er indeksert, vil det samme søket skje i den mindre indekstabellen, samle nøklene til matchende poster og deretter se i hoveddatatabellen for postene med disse tastene. Vanligvis lagres et bord på en måte som gjør at et oppslag via en nøkkel kan være veldig raskt.

Relasjonsdatabaser ikke iboende inneholder ideen om faste relasjoner mellom poster. I stedet er relaterte data knyttet til hverandre ved å lagre en rekords unike nøkkel i en annen rekords data. For eksempel kan en tabell som inneholder e -postadresser for brukere inneholde et dataelement kalt userpk, som inneholder hovednøkkelen til brukerposten den er knyttet til. For å koble brukere og deres e -postadresser, søker systemet først opp de valgte brukerregistreringens hovednøkler, ser etter disse nøklene i userpkkolonnen i e -posttabellen (eller, mer sannsynlig, en indeks over dem), trekker ut e -postdataene, og kobler deretter bruker- og e -postoppføringene til å lage sammensatte poster som inneholder alle de valgte dataene. Denne operasjonen, kalt en join , kan være beregningsmessig dyr. Avhengig av kompleksiteten i spørringen, antall sammenføyninger og indeksering av forskjellige nøkler, kan det hende at systemet må søke gjennom flere tabeller og indekser og deretter sortere alt for å matche det sammen.

I kontrast lagrer grafdatabaser forholdene mellom poster direkte. I stedet for at en e -postadresse blir funnet ved å slå opp brukerens nøkkel i userpkkolonnen, inneholder brukerposten en peker som direkte refererer til e -postadresseposten. Det vil si at etter å ha valgt en bruker, kan pekeren følges direkte til e -postoppføringene, det er ikke nødvendig å søke i e -posttabellen for å finne de matchende postene. Dette kan eliminere de dyre sammenføyningsoperasjonene. For eksempel, hvis man søker etter alle e -postadressene for brukere i retningsnummeret "311", vil motoren først utføre et konvensjonelt søk for å finne brukerne i "311", men deretter hente e -postadressene ved å følge koblingene i disse postene. En relasjonsdatabase vil først finne alle brukerne i "311", trekke ut en liste over hovednøklene, utføre et nytt søk etter poster i e -posttabellen med de primære nøklene og koble de matchende postene sammen. For denne typen vanlige operasjoner ville grafdatabaser teoretisk sett vært raskere.

Den sanne verdien av graftilnærmingen blir tydelig når man utfører søk som er mer enn ett nivå dype. Vurder for eksempel et søk etter brukere som har "abonnenter" (en tabell som knytter brukere til andre brukere) i "311" -nummeret. I dette tilfellet må en relasjonsdatabase først søke etter alle brukerne med retningsnummeret i "311", deretter søke i abonnenttabellen etter noen av disse brukerne og deretter til slutt søke i tabellen for å hente de matchende brukerne. I kontrast ville en grafdatabase søke etter alle brukerne i "311", og deretter følge tilbakekoblingene gjennom abonnentforholdet for å finne abonnentbrukerne. Dette unngår flere søk, oppslag og minnebruk som er involvert i å lagre alle midlertidige data fra flere poster som trengs for å konstruere utdataene. Når det gjelder stor O -notasjon , ville denne spørringen være tid - dvs. proporsjonal med logaritmen til størrelsen på dataene. I kontrast vil den relasjonelle versjonen være flere oppslag, pluss tiden det tar å bli med i alle datapostene. ${\ displaystyle O (\ log n)+O (1)}$${\ displaystyle O (\ log n)}$

Den relative fordelen med grafinnhenting vokser med kompleksiteten til et søk. For eksempel vil man kanskje vite "den filmen om ubåter med skuespilleren som var i den filmen med den andre skuespilleren som spilte hovedrollen i Gone With the Wind ". Dette krever først at systemet finner skuespillerne i Gone With the Wind , finner alle filmene de var i, finner alle skuespillerne i alle filmene som ikke var hovedrollen i Gone With the Wind , og deretter fant alle filmene de var inne og filtrerte til slutt listen til de med beskrivelser som inneholder "ubåt". I en relasjonsdatabase vil dette kreve flere separate søk gjennom film- og skuespillertabellene, gjøre et nytt søk på ubåtfilmer, finne alle skuespillerne i disse filmene og deretter sammenligne (store) innsamlede resultater. I kontrast vil grafdatabasen gå fra Gone With the Wind til Clark Gable , samle lenker til filmene han har vært i, samle lenker ut av disse filmene til andre skuespillere og deretter følge koblingene ut av disse skuespillerne tilbake til listen over filmer. Den resulterende listen over filmer kan deretter søkes etter "ubåt". Alt dette kan gjøres via ett søk.

Egenskaper legger til et annet abstraksjonslag til denne strukturen som også forbedrer mange vanlige spørsmål. Egenskaper er i hovedsak etiketter som kan brukes på alle poster, eller i noen tilfeller, kanter også. For eksempel kan man merke Clark Gable som "skuespiller", noe som vil tillate systemet å raskt finne alle postene som er skuespillere, i motsetning til regissør eller kameraoperatør. Hvis etiketter på kantene er tillatt, kan man også merke forholdet mellom Gone With the Wind og Clark Gable som "bly", og ved å utføre et søk på personer som er "hoved" "skuespiller" i filmen Gone With the Wind , the databasen ville produsere Vivien Leigh , Olivia de Havilland og Clark Gable. Den tilsvarende SQL -spørringen må stole på tilleggsdata i tabellen som forbinder mennesker og filmer, og legger til mer kompleksitet i spørresyntaksen. Denne typen etiketter kan forbedre søkeytelsen under visse omstendigheter, men er generelt mer nyttig når det gjelder å legge til semantiske data for sluttbrukere.

Relasjonsdatabaser er veldig godt egnet for flate dataoppsett, der forholdet mellom data er ett eller to nivåer dypt. For eksempel kan det hende at en regnskapsdatabase må slå opp alle ordrelinjene for alle fakturaene for en gitt kunde, en spørring med tre ledd. Grafdatabaser er rettet mot datasett som inneholder mange flere lenker. De er spesielt godt egnet for sosiale nettverkssystemer , der "venner" -forholdet i hovedsak er ubegrenset. Disse egenskapene gjør grafdatabaser naturlig egnet for typer søk som blir stadig mer vanlige i online systemer og i store datamiljøer. Av denne grunn blir grafdatabaser veldig populære for store online systemer som Facebook , Google , Twitter og lignende systemer med dype koblinger mellom poster.

For å illustrere ytterligere, tenk deg en relasjonsmodell med to tabeller: en peopletabell (som har en person_idog person_namekolonne) og en friendtabell (med friend_idog person_id, som er en fremmed nøkkel fra peopletabellen). I dette tilfellet vil det å søke etter alle Jacks venner resultere i følgende SQL -spørring.

SELECT p2.person_name 
FROM people p1 
JOIN friend ON (p1.person_id = friend.person_id)
JOIN people p2 ON (p2.person_id = friend.friend_id)
WHERE p1.person_name = 'Jack';

Den samme spørringen kan oversettes til -

• Cypher , et spørrespråk for en grafdatabase

  MATCH (p1:person {name: 'Jack'})-[:FRIEND_WITH]-(p2:person)
  RETURN p2.name
  

• SPARQL , et spørrespråk for RDF -grafdatabaser standardisert av W3C og brukt i flere RDF Triple- og Quad -butikker
  • Lang form

    PREFIX foaf: <http://xmlns.com/foaf/0.1/>
    
    SELECT ?name
    WHERE { ?s a          foaf:Person . 
            ?s foaf:name  "Jack" . 
            ?s foaf:knows ?o . 
            ?o foaf:name  ?name . 
          }
    

  • Kortform

    PREFIX foaf: <http://xmlns.com/foaf/0.1/>
    
    SELECT ?name
    WHERE { ?s foaf:name     "Jack" ;
               foaf:knows    ?o .
               ?o foaf:name  ?name .
          }
    

• SPASQL, et hybrid databasesøksspråk, som utvider SQL med SPARQL

  SELECT people.name
  FROM (
         SPARQL PREFIX foaf: <http://xmlns.com/foaf/0.1/>
                SELECT ?name
                WHERE { ?s foaf:name  "Jack" ; 
                           foaf:knows ?o .
                        ?o foaf:name  ?name .
                      }
      ) AS people ;
  

Eksemplene ovenfor er en enkel illustrasjon av et grunnleggende forholdsspørsmål. De kondenserer ideen om relasjonelle modellers spørrekompleksitet som øker med den totale datamengden. Til sammenligning er en grafdatabaseforespørsel lett i stand til å sortere gjennom relasjonsgrafen for å presentere resultatene.

Det er også resultater som indikerer enkle, kondenserte og deklarative spørsmål til grafdatabasene, ikke nødvendigvis gir god ytelse i forhold til de relasjonsdatabasene. Mens grafdatabaser tilbyr en intuitiv representasjon av data, gir relasjonsdatabaser bedre resultater når det er nødvendig med settoperasjoner.

Liste over grafdatabaser

Følgende er en liste over bemerkelsesverdige grafdatabaser:

Graf spørringsprogrammeringsspråk

• AQL (ArangoDB Query Language) : et SQL-lignende spørrespråk som brukes i ArangoDB for både dokumenter og grafer
• Cypher Query Language (Cypher): en graf spørring deklarative språket for Neo4j som gjør at ad hoc og programma (SQL-lignende) tilgang til grafen.
• GQL : foreslått ISO standard grafisk spørrespråk
• GSQL : et SQL-lignende Turing-komplett grafisk spørrespråk designet og tilbudt av TigerGraph
• GraphQL : en åpen kildekode- dataforespørsel og manipulasjonsspråk for APIer. Dgraph implementerer modifisert GraphQL-språk kalt DQL (tidligere GraphQL+-)
• Gremlin : et grafisk programmeringsspråk som er en del av Apache TinkerPop åpen kildekode-prosjekt
• SPARQL : et spørrespråk for RDF -databaser som kan hente og manipulere data lagret i RDF -format

Se også

• Graf transformasjon
• Hierarkisk databasemodell
• Datalog
• Objektdatabase
• RDF -database
• Strukturert lagring
• Tekstgraf

Referanser