Vi undersöker grundläggande funktioner bakom moderna graf frågespråk. Vi diskuterar först två populära grafdatamodeller: kantmärkta grafer, där noder är sammankopplade med riktade, märkta kanter och egenskapsgrafer, där noder och kanter kan ha ytterligare attribut. Därefter diskuterar vi de två mest grundläggande graf frågefunktionerna: grafmönster och navigeringsuttryck. Vi börjar med grafmönster, där en grafstrukturerad fråga matchas mot data. Därefter diskuterar vi navigeringsuttryck, där mönster kan matchas rekursivt mot grafen för att navigera stigar av godtycklig längd; vi ger en översikt över vilka typer av uttryck som har föreslagits och hur de kan kombineras med grafmönster. Vi diskuterar också flera semantik under vilka frågor med hjälp av tidigare funktioner kan utvärderas, vilka effekter urvalet av funktioner och semantik har på komplexitet, och erbjuder exempel på sådana funktioner i tre moderna språk som används för att fråga grafer: SPARQL, Cypher och Greml. Vi avslutar med att diskutera betydelsen av formalisering för grafförfrågan språk; en sammanfattning av vad som är känt om SPARQL, Cypher och Greml i termer av expressivitet och komplexitet; och en översikt över möjliga framtida riktningar för området. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org.  Under det senaste årtiondet har intresset för grafdatabaser ökat, där enheter från intresseområdet representeras av noder och relationer mellan dem med kanter. En del av denna uppgång beror på den växande insikten att det finns en mängd olika domäner för vilka grafdatabaser erbjuder en mer intuitiv konceptualisering än deras mer väletablerade relationskusiner. Man kan till exempel se ett socialt nätverk som en graf över människor som känner varandra. Man kan också betrakta transportnät, biologiska vägar, citeringsnätverk osv. som en graf. Även om grafer fortfarande kan lagras (och ibland fortfarande är) i relationsdatabaser, valet att använda en graf databas för vissa domäner har betydande fördelar när det gäller att fråga, där betoningen skiftar från att gå olika tabeller till att specificera grafmönster och navigeringsmönster mellan noder som kan spänna godtyckliga längd banor. Räckvidd. Vårt mål i denna undersökning är att ge en fördjupad diskussion om de viktigaste begreppsdrag som finns i moderna grafförfrågan språk, som både stöds av graf databas motorer och studeras i den teoretiska litteraturen. Genom att organisera vår undersökning på nivån för frågefunktioner, snarare än språk, ger vi en grundläggande introduktion till området, vilket hjälper till att förstå, och även definiera, individuella frågespråk som sammansättningen av funktioner. Vi betraktar två kategorier av frågetecken på hög nivå: grafmönster och sökvägar. Dessa funktioner utgör tillsammans kärnan i en mängd moderna graf frågespråk ( Efter att ha infört och definiera grafen frågefunktioner i varje kategori, listar vi olika semantik under vilka sådana funktioner kan utvärderas, ge exempel på hur sådana funktioner tillämpas i ett urval av moderna frågespråk, diskutera den beräknings komplexiteten av nyckelproblem som ligger till grund för sådana funktioner, och presentera några av deras viktigaste förlängningar som genomförs i moderna graf databas motorer. Vi avslutar med att sammanställa hela den grundläggande diskussionen till en sammanfattning av de typer av funktioner som vi har behandlat, hur dessa funktioner kan användas för att förstå komplexiteten och expressiviteten hos moderna frågespråk, betydelsen av formalisering för sådana språk, de viktigaste utmaningar som ligger till grund för deras genomförande och optimering i praktiska motorer, och möjliga sätt på vilka de kan utvecklas. Enkätstruktur. Undersökningen är strukturerad enligt följande: -Vi diskuterar först två grafdatamodeller i Avsnitt 2: kantmärkta grafer, som är den grundmodell som behandlas i grafdatabaslitteraturen, och egenskapsgrafer, som är en modell som vanligen används i praktiken, där noder och kanter i märkta grafer kan kommenteras med ytterligare metainformation. -I Avsnitt 3 diskuterar vi grafmönster, där en grafstrukturerad fråga matchas mot grafdatabasen. Vi diskuterar också utbyggnaden av sådana grafmönster med ytterligare operatörer, såsom projektion, skillnad, union och så vidare. -Avsnitt 4 introducerar sedan navigeringsuttryck, som, till skillnad från grafmönster, kan matcha stigar av godtycklig längd. -I avsnitt 5 presenterar vi våra sista kommentarer. Tillägg på nätet. En nätbilaga för denna artikel innehåller flera aspekter av grafförfrågan språk som, även om inte mainstream, har haft viss täckning i forskningslitteraturen och i praktiska system. Dessa inkluderar en alternativ semantik för att matcha mönster till grafer;
Nyligen, Angles et al. REF presenterade en studie om grundläggande graf frågefunktioner (huvudsakligen grafmönster och navigeringsfrågor) och deras genomförande i moderna graf frågespråk.
Foundations of Modern Query Languages for Graph Databases
{'venue': 'CSUR', 'journal': None, 'mag_field_of_study': ['Computer Science']}