Med tanke på den varaktiga tillväxt som vi upplever i antalet tillgängliga SPARQL-slutpunkter har behovet av att kunna skicka federerade SPARQL-frågor över dessa också ökat. För att ta itu med detta användningsfall definierar arbetsgruppen W3C SPARQL en federationsförlängning för SPARQL 1.1 som gör det möjligt att kombinera grafmönster som kan utvärderas över flera endpoints inom en enda fråga. I den här artikeln beskriver vi syntaxen för denna förlängning och formaliserar dess semantik. Dessutom beskriver vi hur ett frågeutvärderingssystem kan implementeras för denna federationsförlängning, beskriver några statiska optimeringstekniker och återanvänder en frågemotor som används för dataintensiv vetenskap, för att hantera stora mängder mellan- och slutresultat. Slutligen utför vi en serie experiment som visar att våra optimeringar påskyndar den federerade frågeutvärderingsprocessen. De senaste åren har en stor och konstant ökning av mängden RDF-data på webben, exponerad med hjälp av länkade data-aktiverade avrefererbara URIs i olika format (såsom RDF/XML, Turtle, RDFa, etc.) och -av särskilt intresse för det aktuella dokumentet - genom SPARQL-slutpunkter. Flera icke uttömmande, och ibland föråldrade eller inte kontinuerligt underhållna, listor över SPARQL endpoints eller datakataloger finns i olika format som CKAN 1, Data Hub 2, W3C wiki 3, etc. De flesta av dessa datauppsättningar är sammankopplade, vilket beskrivs grafiskt i det välkända länkade Open Data Cloud diagram 4, som gör det möjligt att navigera genom dem och underlättar uppbyggnadDetta arbete har utförts inom ramen för ADMIRE-projektet (EU FP7 ICT-215024), och fick stöd av Science Foundation Ireland-projektet Lion-2 (Grant No. SFI/08/CE/I1380) samt Net2-projektet (FP7 Marie Curie IRSES 247601). Vi vill, bland många andra, tacka OGSA-DAI-teamet, speciellt till Ally Hume, för deras råd i utvecklingen av dataflödena. Marc-Alexandre Nolin för sin hjälp med bio2rdf frågor och Jorge Pe ́rez för hans råd i theorem bevisar. Komplexa frågor genom att kombinera data från olika, ibland heterogena och ofta fysiskt distribuerade dataset. SPARQL-slutpunkter är RESTful services som accepterar frågor över HTTP skrivna på SPARQL-frågespråket [1, 2] som följer SPARQL-protokollet [3], enligt definitionen i respektive W3C-rekommendationsdokument. Den nuvarande SPARQL-rekommendationen har dock en viktig begränsning när det gäller att definiera och genomföra frågor som spänner över distribuerade datamängder, eftersom den döljer den fysiska fördelningen av data över endpoints, och har normalt använts för att ifrågasätta isolerade endpoints. Därför har användare som är villiga att federera frågor över ett antal SPARQL-slutpunkter tvingats att skapa ad-hoc-tillägg till frågespråket och protokollet, att inkludera ytterligare information om datakällor i konfigurationen av sina SPARQL-slutpunkter [4, 5, 6] eller att utforma tekniska lösningar där data från avlägsna slutpunkter kopieras till det mål som ställs. Med tanke på behovet av att ta itu med dessa typer av frågor har SPARQL-arbetsgruppen föreslagit en förlängning av frågeförbundet för det kommande SPARQL 1.1-språket [7] som nu diskuteras för att skapa en ny W3C-rekommendation under de kommande månaderna. Den federerade frågeutbyggnaden av SPARQL 1.1 omfattar den nya SERVICE-operatören som också kan användas tillsammans med en annan ny operatör i det viktigaste SPARQL 1.1 frågedokumentet: BINDINGS. För det första gör SERVICE-operatören det möjligt att i en SPARQL-förfrågan ange ett mål för SPARQL-förfrågan till vilket en del av frågan kommer att delegeras. Detta frågemått kan vara känt vid tidpunkten för att bygga frågan, och därför kommer SERVICE-operatören redan att ange IRI för SPARQL-slutpunkten där det kommer att utföras, eller kan vara en variabel som blir bunden vid tiden för frågeutförandet efter att ha utfört ett initialt SPARQL-frågefragment i en av de ovannämnda RDF-aktiverade datakatalogerna, så att potentiella SPARQL-slutpunkter som kan svara på resten av frågan kan erhållas och användas. För det andra tillåter BINDINGS-operatören överföring av resultat som används för att begränsa en fråga, och som till exempel kan komma från begränsningar som anges i användargränssnitt som sedan omvandlar dessa till SPARQL-frågor eller -särskilt, detta kan användas vid genomförande av federerade frågor genom skriptning - från tidigare utföranden av andra frågor. I detta dokument föreslår vi en syntax och en formalisering av semantiken i dessa förbundsförlängningar av SPARQL 1.1 och definierar de begränsningar som måste beaktas i deras användning för att kunna tillhandahålla pragmatiska genomföranden av frågeutvärderare. I detta syfte definierar vi begreppen tjänstegräns och servicesäkerhet, som säkerställer att SERVICE-operatören kan utvärderas på ett säkert sätt. Vi implementerar de statiska optimeringar som föreslås i [8], med hjälp av begreppet väl utformade mönster, som visar sig vara effektiva i optimeringen av frågor som innehåller OPTIONAL operatör, den dyraste operatören i SPARQL [8, 9]. Detta har också viktiga konsekvenser för antalet tuples som överförs och förenas i federerade frågor, och därför drar vårt genomförande nytta av detta. Andra verk har analyserat adaptiv frågebehandling [10, 11] som optimerar SPARQL-frågor genom att anpassa dem beroende på de specifika villkoren i fråge-/utförandemiljön. Som ett resultat av vårt arbete har vi inte bara formaliserat semantiken i SPARQL 1.1 federerad frågeförlängning, utan vi har också implementerat ett system som stöder dessa förlängningar och använder sig av de diskuterade optimeringarna. Detta system, SPARQL-DQP (som står för SPARQL Distributed Query Processing), är byggt ovanpå OGSA-DAI- och OGSA-DQP-infrastrukturerna [12, 13] som gör det möjligt att hantera stora mängder data i distribuerade inställningar, till exempel genom att stödja ett indirekt åtkomstläge som normalt används vid utveckling av data-in tensiva arbetsflöden. Sammanfattningsvis är de viktigaste bidragen i detta dokument: • En formalisering av semantiken i federationens utvidgning av SPARQL 1.1, baserad på den nuvarande SPARQL semantiken. • En definition av tjänste- och trygghetsvillkor för att säkerställa en pragmatisk utvärdering av dessa frågor. • En uppsättning statiska optimeringar för dessa frågor, i närvaro av OPTIONAL operatörer. • Ett genomförande som lämpar sig för att hantera storskaliga RDF-datauppsättningar fördelade över federerade frågeslutpunkter. Tidningens organisation. I Avsnitt 1 beskriver vi syntaxen och semantiken i förlängningen av SPARQL 1.1. I avsnitt 2 introducerar vi begreppen tjänstebegränsning och servicesäkerhet, vilket säkerställer att SERVICE-operatören kan utvärderas på ett säkert sätt. I Avsnitt 3 presenterar vi några optimeringstekniker för utvärdering av SPARQL 1.1 federerad frågeförlängning. Slutligen, i avsnitt 4 och 5, presenterar vi vårt genomförande samt en experimentell utvärdering av det. 1. Vad är det för fel på dig? Syntax och semantik av SPARQL inklusive SPARQL 1.1 Federated Query I detta avsnitt ger vi en algebraisk formalisering av SPARQL 1.1 inklusive SPARQL 1.1 Federated Query. Vi begränsar oss till SPARQL över enkla RDF, d.v.s. vi bortser från högre implementationssystem (se [14] ) såsom RDFS eller OWL. Vår utgångspunkt är den befintliga formaliseringen av SPARQL som beskrivs i [8], till vilken vi lägger de operatörer SERVICE föreslås i [7] och BINDINGs föreslås i [2]. Vi introducerar först de nödvändiga begreppen om RDF (tar främst från [8] Dessutom, anta förekomsten av en oändlig uppsättning V av variabler som separeras från ovanstående uppsättningar, och lämna UNBOUND att vara en reserverad symbol som inte tillhör någon av de tidigare nämnda uppsättningar. Den officiella syntaxen för SPARQL [1] behandlar operatörer OPERATIVA, UNION, FILTER, GRAPH, SELECT och konkatering via en punktsymbol (.), för att konstruera diagram mönsteruttryck. Operatörer SERVICE introduceras i SPARQL 1.1 Federated Query extension och BINDINGs införs i det viktigaste SPARQL 1.1 frågedokumentet, det förstnämnda för att tillåta användare att rikta en del av en fråga till en viss SPARQL endpoint, och det senare för överföring av resultat som används för att begränsa en fråga. Syntaxen av språket anser också { } att gruppera mönster och några implicita regler för företräde och association. För att undvika tvetydigheter i tolkningen följer vi det tillvägagångssätt som föreslås i [8], och vi presenterar först syntaxen för SPARQL grafmönster i en mer traditionell algebraisk formalism, med hjälp av operatörer OCH (.), UNION (UNION), OPT (OPTIONAL), FILTER (FILTER), GRAPH (GRAPH) och SERVICE (SERVICE), sedan introducerar vi syntaxen för BINDINGS-frågor, som använder BINDINGS-operatören (BINDINGS), och vi avslutar med att definiera syntaxen för SELECT-frågor, som använder SELECT-operatören (SELECT). Mer exakt definieras ett uttryck för SPARQL-grafmönster rekursivt enligt följande: (1) En tupel från (/ULUV)x(/UV)x(/ULUF) är ett diagrammönster (ett trippelmönster). (2) Om P1 och P2 är grafmönster är uttryck (P1 OCH P2), (P1 OPT P2) och (P1 UNION P2) grafmönster. (3) Om P är ett grafmönster och R är ett STARQL-inbyggt tillstånd är uttrycket (P FILTER R) ett grafmönster. (4) Om P är ett diagrammönster och en e (/UV), då (GRAPH a P) är ett diagrammönster. (5) Om P är ett diagrammönster och en e (/UV), då (SERVICE a P) är ett diagrammönster. Som vi kommer att se nedan beter de sig semantiskt på ett helt annat sätt, trots likheterna mellan GRAPH:s och SERVICE:s syntaxer. För utställningen av detta papper, vi utelämnar ytterligare mer komplexa grafmönster från SPARQL 1.1 inklusive aggregat, fastighetsvägar och delväljer, men bara nämna en annan funktion som är särskilt relevant för federerade frågor, nämligen, BINDINGS frågor. En SPARQL BINDINGS fråga definieras enligt följande: (6) Om P är en graf mönster, Vi V är en icke-tom sekvens av parvis distinkta variabler av längd n > 0 och {A 1,.....,Ak\ är en nontomy uppsättning sekvenser Ai e (ZULU {UNBOUND})", sedan (P BINDINGS W {A 1,..., A#}) är en BINDINGS fråga. Slutligen definieras en SPARQL SELECT fråga som: (7) Om P är antingen en graf mönster eller en BINDINGs fråga, och W är en uppsättning variabler, då (SELECT W P) är en SELECT fråga. Det är viktigt att notera att reglerna (1)-4 ovan infördes [8], medan vi formaliserar i reglerna (5)- (7) den förlängning av SPARQL som föreslås [7]. Vi använde begreppet inbyggda förhållanden för FILTER-operatören ovan. Ett inbyggt SPARQL- tillstånd är konstruerat med hjälp av element av setet (/ U L U V) och konstanter, logiska bindväv (¬, A, V), den binära likheten predikat (=) samt unary predikat som bundna, isBlank, isIRI, och isLiteral. 6 Det vill säga: (1) Y är inbyggda förhållanden, och (2) om P 1 och P2 är inbyggda förhållanden, då (¬R1), (P 1 V P2) och (P 1 A P2) är inbyggda förhållanden. Låt P vara antingen en graf mönster eller en BINDINGs fråga eller en SELECT fråga. I vad som följer, använder vi var(P) för att beteckna uppsättningen av variabler som förekommer i P. I synnerhet, om t är en trippel mönster, då var(t) betecknar den uppsättning variabler som förekommer i komponenterna i t. På samma sätt, för en inbyggd tillstånd P, använder vi var(R) för att beteckna uppsättningen variabler som förekommer i P. För att definiera semantiken i SPARQL-frågor, måste vi införa några extra terminologi från [8]. Absusing notation, för en trippel mönster t, betecknar vi med y(t) mönstret som erhålls genom att ersätta variablerna i t enligt y. Y-domänen, som betecknas med dom(y), är den delmängd av V där y definieras. Ibland skriver vi ner betongkartor inom hakparenteser, till exempel y = [?X -> a, Y -> b] är kartläggningen med dom(y) = {?X,?Y\ sådan att y(?X) = a och y(?Y) = b. Två kartläggningar y 1 och y2 är kompatibla, betecknade av För enkelhetens skull utelämnar vi här andra funktioner såsom jämförelseoperatörer (' <', '>',' <','>), konvertering av datatyp och strängfunktioner, se [1, Avsnitt 11.3] för detaljer. Det bör noteras att resultaten av papperet lätt kan utvidgas till de andra inbyggda predikaten i SPARQL μ\ ~ μ2, när det gäller alla IX e dom(μi) n dom(μ2), är det fallet att μ\(!X) = μ2(7X), dvs. när μ\ U μ2 också är en kartläggning. Intuitivt är μi och μ2 kompatibla om μi kan utökas med μ2 för att få en ny kartläggning, och vice versa [8]. Vi kommer att använda symbolen μ@ för att representera mappningen med tom domän (som är kompatibel med någon annan mappning). Låt Oi och O2 vara uppsättningar av kartor. 7 Därefter förening av, skillnaden mellan och vänster ytterjoin mellan Oi och O2 definieras enligt följande [8]: Qi M Q 2 =\μ\ Uμ 2 I μ\ eQi, μ2 e ^2 ochμi ~ μq\, Qi UQ 2 = {μ I μ e Q. y ox μ e Q. 2 \, Qi \ Q 2 = {μ e Qi I Vμ € Q 2 : μ *-μ% Nästa vi använder dessa operatörer för att ge semantik till diagram mönster uttryck, BINDINGS frågor och SELECT frågor. Mer specifikt definierar vi denna semantik i termer av en utvärderingsfunktion [ • }® s, som tar som inmatning någon av dessa typer av frågor och returnerar en uppsättning kartläggningar, beroende på den aktiva datauppsättningen DS och den aktiva grafen G inom DS. Här använder vi begreppet dataset från SPARQL, dvs. en datauppsättning DS = {(def, G), (gi, Gi),... (gk, Gk)}, med k > 0 är en uppsättning symboler och grafer som hör ihop med dessa symboler, där standardgrafen G identifieras med specialsymbolen def i I och de återstående så kallade "namngivna" graferna (Gi) identifieras av IRI (gi e I). Utan förlust av allmängiltighet (det finns andra sätt att definiera datauppsättningen såsom via explicita FRAN-klausuler och FRAN NAMD-klausuler), antar vi att en förfrågan utvärderas över en fast datauppsättning DS och att alla SPARQL-variabler som identifieras av en IRI-ål utvärderar sina frågor mot sin egen fasta datauppsättning DS c = {(def,G c ), (g C, i, G C, i),...(gc,k c Det är, vi antar att ges en partiell funktion ep från uppsättningen / av IRIs sådan att för varje c I, om ep(c) definieras, sedan ep{c) = DS C är datauppsättningen associerad med den endpoint som är tillgänglig via IRI c. Dessutom antar vi (i) en funktionsgraf (g,DS) som - gav en datauppsättning DS = {def, G), (gi, G\),... (gk, Gk)} och en graf som heter g {def, g) - returnerar grafen som motsvarar g i DS, och (gii) tidigare namn som DS. Utvärderingen av en graf mönster P över en datauppsättning DS med aktiv graf G, betecknad av [Pjg, definieras rekursivt som visas i figur 1. I denna siffra grundar sig definitionen av FILTER-operatörens semantik på definitionen av begreppet tillfredsställelse av ett inbyggt tillstånd genom en kartläggning. Mer exakt, med tanke på en kartläggning μ och ett inbyggt tillstånd R, säger vi att μ uppfyller R, betecknar med μ  på = R, om: -R är (¬^1), och det är inte fallet att μ  till = R\; Dessutom är semantik av BINDINGS frågor definieras enligt följande. 7 Som i [8], För utställningen i detta papper, Vi anser en semantik, medan semantik [1] anser dubbletter lösningar, dvs multiset av kartläggningar. 8 För presentationens skull använder vi här de tvåvärderade semantiken för inbyggda förhållanden från [8], istället för de trevärderade semantikerna inklusive fel som används i [1]. Det bör noteras att resultaten av papperet lätt kan utvidgas till denna trevärderade semantik. (1) Om P är ett trippelmönster t, då [P]g S = {p. \ dom( jj) = var(t) och/i(f) e G\. (2) Om P är (P1 OCH P2), och u c Det är viktigt att notera att reglerna (1)- (5) och (7) i figur 1 och den tidigare regeln (9) infördes [8], medan vi föreslår i reglerna (6) och (8) Målet med reglerna (6) och (8) är att på ett otvetydigt sätt definiera vad resultatet av utvärderingen av ett uttryck som innehåller operatörerna SERVICE och BINDINGS bör vara. Dessa regler bör därför inte betraktas som en okomplicerad grund för ett genomförande av språket. I själva verket skulle ett direkt genomförande av regeln (6), som definierar semantiken i ett mönster av formen (SERVICE?X P 1 ), innebära att utvärdera en särskild fråga i varje möjlig SPARQL endpoint, som uppenbarligen är ogenomförbar i praktiken. I nästa avsnitt står vi inför denna fråga och i synnerhet inför vi ett syntaktiskt villkor för SPARQL-frågor som säkerställer att ett mönster av formuläret (SERVICE?X P 1 ) kan utvärderas endast med tanke på en begränsad uppsättning SPARQL-slutpunkter, vars IRI faktiskt tas från RDF-grafen där frågan utvärderas. Som vi påpekade i föregående avsnitt, utvärderingen av ett mönster av formen (SERVICE?X P) är ogenomförbar om inte variabeln?X är bunden till en ändlig uppsättning av IRIs. Detta begrepp om begränsning är ett av de mest betydelsefulla och oklara begreppen i SPARQL-federationens förlängning. Eftersom man ännu inte kunde enas om ett sådant begrepp om begränsning, innehåller den nuvarande versionen av specifikationen för denna utvidgning [7] inte någon formalisering av formens semantik (SERVICE?X P). Här ger vi en formalisering av detta koncept, och vi studerar de komplexitetsfrågor som är förknippade med det. Antag att G är en RDF-graf som använder tredubblar av blanketten (a, service_adress, b) för att indikera att en SPARQL-slutpunkt med namn a finns på IRI b. Dessutom låter P vara följande SPARQL fråga: Query P används för att beräkna listan över namn och e-postadresser som kan hämtas från SPARQL endpoints som lagras i en RDF graf. I själva verket, om y e \ P} G, så y(?X) är namnet på en SPARQL endpoint som lagras i G, y(?N) är namnet på en person som lagras i SPARQL endpoint och y(?E) är den personens e-postadress. Det är viktigt att notera att det finns en enkel strategi som säkerställer att fråga P kan utvärderas i praktiken: första beräkna \(?X, service_adress,?Y)J G S, och sedan för varje y i denna uppsättning, beräkna [(SERVICE a (?N, e-post,?E) I definitionen av detta begrepp, Dom(G) hänvisar till domänen för en graf G, det vill säga den uppsättning element från (IUBUL) som nämns i G; dom(DS) hänvisar till föreningen av domäner för alla grafer i datauppsättningen DS; och slutligen, Dom(P) hänvisar till uppsättningen element från (I U L) som nämns i P. • P är en SELECT fråga (SELECT W P1) och?X är bunden i P1. I utvärderingen av ett grafmönster (GRAPH?X P) över en datauppsättning DS, tar variabeln?X nödvändigtvis ett värde från namn (DS). GRAPH-operatören gör därför att en sådan variabel?X blir bunden. Med tanke på att värdena i namn (DS) inte nödvändigtvis nämns i datauppsättningen DS, ställer den tidigare definitionen först villkoret att?X e dom(y), och sedan inte bara anser att fallet y(?X) e dom(DS) utan också fallet På samma sätt kan BINDINGS operatör göra en variabel?X i en fråga P vara bunden genom att tilldela den en fast uppsättning värden. Med tanke på att dessa värden inte nödvändigtvis nämns i datauppsättningen DS där P utvärderas, anser den tidigare definitionen också att fallet y(?X) e dom(P Ett naturligt sätt att säkerställa att en SPARQL-fråga P kan utvärderas i praktiken är genom att införa begränsningen att för varje sub-mönster (SERVICE?X P1) av P, den innehar att?X är bunden i P. Men i följande teorem visar vi att ett sådant villkor är oavgjort och därmed skulle en SPARQL-fråga motor inte kunna kontrollera det för att säkerställa att en fråga kan utvärderas. Bevis: Tillfredsställande problem för relationell algebra är problemet med att verifiera, ge ett relationsuttryck <p, om det finns en (finita) databas instans Jag sådan att uppsättningen svar av tp över jag inte är tom. Med tanke på att detta problem är obeslutbart [16], är det möjligt att bevisa från resultaten i [17] följande resultat om komplexiteten i tillfredsställande problem för SPARQL. En graf mönster P sägs vara tillfredsställande om det finns en datauppsättning DS och RDF graf G i DS sådan att [Pj G + 0. Därefter visar vi att komplementet till det tidigare problemet kan reduceras till problemet att verifiera, med tanke på ett diagrammönster P och en variabel?X e var(P), om?X är bunden i P, som vi drar slutsatsen att theorem håller. Låt P vara en graf mönster och?X, Y,?Z vara variabler som inte nämns i P. Sedan definiera en graf mönster Q som: Det är lätt att se att variabeln?X är bunden i Q om och endast om graf mönster P inte är tillfredsställande, som skulle visas. • Det faktum att begreppet begränsning är obeslutbart hindrar en från att använda det som en begränsning över variablerna i SPARQL-frågor. För att övervinna denna begränsning inför vi här ett syntaktiskt tillstånd som säkerställer att en variabel är bunden i ett mönster och som kan verifieras effektivt. Definition 2 (Stark begränsning). Låt P vara en SPARQL fråga. Då är mängden starkt bundna variabler i P, betecknad som SB(P), rekursivt definierad enligt följande: • om P = (Pi OCH P2), sedan SB(P) = SB(Pi) U SB(P2), • ifP = (Pi OPT P2), sedan SB(P) = SB(Pi); • ifP = (Pi FILTERR), sedan SB(P) = SB(Pi); SB(P) = 0, (?X I?X ingår i W och för varje i {1,...,n\ : IX e dom(μ W^) }; den tidigare definitionen rekursivt samlar från en SPARQL-fråga P en uppsättning variabler som garanterat är bundna i P. Till exempel, om P är ett trippelmönster t, sedan SB(P) = var(t) som man vet att för varje variabel IX var(t), varje data inställt DS och varje På samma sätt, om P(P) (P(P) är bundet e^B) och P(P2) som anges i P. I detta fall vet man att IX är bunden i P eftersom domänen för var och en av kartläggningarna μ WMA j>, vilket innebär att μ(?X) e dom(P) för varje μ e [Pj G S. I följande förslag visar vi formellt att vår intuition om SB(P) är korrekt, i den meningen att varje variabel i denna uppsättning är bunden i P (beviset för detta förslag finns i bilaga A). Med tanke på en SPARQL-fråga P och en variabel IX e var(P), kan det effektivt verifieras om IX är starkt bunden i P. Således, ett naturligt och effektivt kontrollerbart sätt att säkerställa att en SPARQL-fråga P kan utvärderas i praktiken är genom att införa begränsningen att för varje sub-mönster (SERVICE IX Pi) av P, hävdar den att IX är starkt bunden i P. Men detta begrepp behöver fortfarande ändras för att vara användbart i praktiken, som framgår av följande exempel. • I följande avsnitt använder vi begreppet starkt avgränsadhet för att definiera ett begrepp som säkerställer att en SPARQL-fråga som innehåller SERVICE-operatören kan utvärderas i praktiken och som tar hänsyn till de idéer som presenteras i ovanstående exempel. Målet med detta avsnitt är att tillhandahålla ett villkor som säkerställer att en SPARQL-fråga som innehåller SERVICE-operatören kan utvärderas på ett säkert sätt i praktiken. Därför måste vi först införa en viss terminologi. Eftersom en SPARQL fråga P, definiera T(P) som parse träd av P. I detta träd, varje nod motsvarar en sub-mönster av P. Ett exempel på en parse träd av ett mönster Q visas i Figur 2. I denna siffra, u 1, u 2, u 3, u 4, u 5, u 6 är identifierare av noderna i trädet, som är märkta med sub-mönster av Q. Det är viktigt att lägga märke till att vi i detta träd inte gör någon skillnad mellan de olika operatörerna i SPARQL, vi använder bara barnets relation för att lagra strukturen av undermönster i en SPARQL fråga. Träd T(P) används för att definiera begreppet tjänsteplikt, som utvidgar begreppet begränsadhet, som infördes i föregående avsnitt, för att ta hänsyn till variabler som är bundna inuti undermönster och bosatta SERVICE-operatörer. Det bör noteras att dessa två egenskaper identifierades i föregående avsnitt som viktiga för definitionen av begreppet avgränsadhet (se exempel 1). med etikett (SERVICE?X P 1 ), det håller att: (1) det finns en nod v av T (P) med etikett P 2 sådan att v är en förfader till u i T (P) och?X är bunden i P 2 ; (2) P 1 är service-bundet. Fråga Q i figur 2 är t.ex. tjänstebunden. I själva verket är villkor (1) i definition 3 uppfyllda eftersom u 5 är den enda noden i T(Q) som har som etikett en SERVICE graf mönster, i detta fall (SERVICE?X (?Y, a,?Z)), och för noden u 3, den innehar att: u 3 är en förfader till u 5 i T(P), etiketten u 3 är P = ((?X, b, c) OCH (SERVICE?X (?Y, a,?Z))) och?X är bunden i P. Dessutom är villkor (2) av definition 3 nöjda som sub-mönster (?Y, a,?Z) av etiketten u 5 är också tjänstebundet. Begreppet tjänstebundenhet fångar vår intuition om villkoret att en SPARQL-fråga som innehåller SERVICE-operatören ska uppfylla. Tyvärr visar följande teorem att ett sådant villkor är obeslutbart och därför skulle en SPARQL frågemotor inte kunna kontrollera det för att säkerställa att en fråga kan utvärderas. Andra teoretikern. Problemet med att kontrollera, med tanke på en SPARQL-fråga P, om P är tjänstebundet är obeslutbart. Bevis: Som i beviset för Theorem 1, använder vi obeslutbarheten av tillfredsställande problem för SPARQL för att visa att theorem håller. Låt P vara en SPARQL graf mönster och?X,?Y,?Z,?U,?V,?W vara variabler som inte nämns i P, och anta att P inte nämner operatören SERVICE (återkalla att tillfredsställande problem är redan obeslutbara för fragmentet Nästa vi visar att Q är service-bundna om och endast om P inte är tillfredsställande. Om P inte är tillfredsställande motsvarar Q mönstret: (=>) Antag att P är tillfredsställande. Med tanke på att variabeln?X inte nämns i P, har vi att?X inte är bunden i grafmönstret ((?X,?Y?Z) UNION P). Således, med tanke på att X är varken bunden i (SERVICE?X (?U,?V,?W)), drar vi slutsatsen att fråga Q inte är service-bundna eftersom X är inte en bunden variabel i Q. Därför har vi visat att komplementet av tillfredsställandet problem för SPARQL kan reduceras till problemet att kontrollera, med tanke på en SPARQL fråga P, om P är service-bundna. Av detta drar vi slutsatsen att theorem håller. • När det gäller begreppet begränsadhet hindrar det faktum att begreppet "tjänsteplikt" är obeslutbart en person från att använda det som en begränsning av de variabler som används i TJÄNSTE-samtal. För att övervinna denna begränsning, i definitionen av service-boundedness, ersätter vi begränsningen att variablerna som används i SERVICE samtal är bundna av den decedable restriktion som de är starkt bundna. På så sätt får vi ett syntaktiskt tillstånd över SPARQL-mönster som säkerställer att de är servicebundna och som effektivt kan verifieras. Som en följd av Proposition 1 får vi följande förslag. Förslag 2. Om en SPARQL fråga P är service-säker, då P är service-bunden. Innan vi börjar med den mest tekniska delen av denna artikel, beskriver vi för läsaren en algoritm för SER-VICE säkerhetskontroll. Vårt system använder en bottomup-algoritm över parseträdet T(Q) i en SPARQL-fråga Q för validering av servicesäkerhet. Detta förfarande passerar parseträdet T(Q) två gånger för att säkerställa att Q kan utvärderas korrekt. I den första traversal, för varje nodidentifierare u av T(Q), beräknar algoritmen uppsättningen starkt bundna variabler för beteckningen P av u. Till exempel, i parsträdet som visas i figur 2, variabeln?X identifieras som den enda starkt bundna variabeln för etiketten av noden med identifieraren u3. I den andra traversalen använder bottom-up algoritmen dessa uppsättningar starkt bundna variabler för att kontrollera två villkor för varje nodidentifierare u av T(Q) med etikett av formuläret (SERVICE?X P): om det finns en nod v av T(Q) med etikett P' sådan att v är en förfader till u i T(Q) och?X är starkt bunden i P', och om P är själv service-safe. Om dessa två villkor är uppfyllda återgår algoritmen till att visa att Q är servicesäkert. I annat fall är förfarandet felaktigt. Om en SPARQL-fråga Q inklusive SERVICE-operatören måste utvärderas i en SPARQL-slutpunkt A, kan en del av underkvitton för Q behöva utvärderas i vissa externa SPARQL-slutpunkter. Problemet med att optimera utvärderingen av Q i A, och i synnerhet problemet med att omordna Q i A för att optimera denna utvärdering, blir därför särskilt relevant i detta scenario, eftersom man i vissa fall inte kan förlita sig på optimeringarna av de externa SPARQL-slutpunkterna. Motiverade av detta presenterar vi i detta avsnitt några optimeringstekniker som utvidgar de tekniker som presenteras i [8] till fallet med SPARQL frågor med hjälp av SERVICE-operatören, och som kan tillämpas på ett stort antal SPARQL federerade frågor. I [8, 9], författarna studerar komplexiteten i att utvärdera ett mönster i fragmentet av SPARQL som består av operatörer OCH, UNION, OPT och FILTER. En av slutsatserna i dessa dokument är att den främsta orsaken till komplexiteten i SPARQL är användningen av OPT-operatören. Det bevisas faktiskt [8] att komplexiteten i problemet med att kontrollera, med tanke på en kartläggning μ, ett SPARQL-mönster P, en datauppsättning DS och en RDF-graf G i DS, huruvida μ e [P]G S är PSPACE-komplett, och det bevisas i [9] att denna gräns förblir densamma om endast OPT-operatören tillåts i SPARQL-mönster. Mot bakgrund av dessa resultat infördes [8] ett fragment av SPARQL som förbjuder en särskild form av interaktion mellan variabler som förekommer i valfria delar, vilket sällan förekommer i praktiken. Mönstren i detta fragment, som kallas väl utformade mönster [8], kan utvärderas mer effektivt och är lämpliga för omordning och optimering. I detta avsnitt utvidgar vi definitionen av begreppet att vara väl utformad till fallet med SPARQL-mönster med hjälp av SERVICE-operatören, och visar att de omordningsregler som föreslås i [8], för att optimera utvärderingen av väl utformade mönster, också hålla i denna förlängning. Användningen av dessa regler gör det möjligt att minska antalet tuples som överförs och förenas i federerade frågor, och därmed vårt genomförande drar nytta av detta som visas i avsnitt 4. Låt P vara ett diagrammönster konstruerat genom att använda operatörerna AND, OPT, FILTER och SERVICE, och anta att P uppfyller säkerhetskravet att för varje delmönster (P1 FILTER R) av P, innehar den var(R) c var(P1). Sedan, genom att följa den terminologi som infördes [8], säger vi att P är väl utformad om för varje subpattern P' = (P1 OPT P2) av P och för varje variabel?X som förekommer i P: Om?X förekommer både inuti P2 och utanför P', då förekommer det också i P1. Alla diagrammönster som ges i föregående avsnitt är väl utformade. Å andra sidan är följande mönster inte väl utformade: I följande förslag visar vi att väldesignade mönster inklusive SERVICE-operatören är lämpliga för ombeställning och därmed för optimering. Förslag 3. Låt P vara ett väl utformat mönster och P' ett mönster som erhålls från P genom att använda en av följande omordningsregler: (((P1 OPT P2) FILTER R) -> ((P1 FILTER R) OPT P2), (P1 OCH (P2 OPT P3)) -> ((P1 OCH P2) OPT P3), ((P1 OPT P2) OCH P3) -> ((P1 OCH P3) OPT P2). Beviset för detta förslag är en enkel förlängning av beviset för Proposition 4.10 i [8]. I vår federerade SPARQL frågemotor (SPARQL-DQP) har vi implementerat de omskrivningsregler som visas i Proposition 3 med en nedifrån-och-upp-algoritm för att kontrollera tillståndet att vara väl utformad. I följande avsnitt beskriver vi detaljerna kring genomförandet av dessa algoritmer och arkitekturen hos SPARQL-DQP. I detta avsnitt beskriver vi implementeringsdetaljerna för SPARQL-DQP-systemet och i synnerhet hur vi implementerade optimeringstekniker för väldesignade SPARQL-grafmönster (som presenteras i avsnitt 3). Vi baserar vårt genomförande på användningen av Web Service-baserad åtkomst till datakällor. WS-baserad åtkomst är en allmänt använd teknik i den dataintensiva vetenskapliga arbetsflödesgemenskapen, och flera system för att få tillgång till stora mängder data använder redan denna metod vid genomförandet. Några av dessa data arbetsflödessystem presenteras i [18, 12, 19]. Dessa system har framgångsrikt använts i en mängd olika data intensiva scenarier som analys av data från södra Kalifornien Jordbävning Center [20], data från biologiska domäner som postgenomisk forskning [21], analys av proteiner och peptider från tandemmasspektrometri data [22], cancerforskning [23], meteorologiska fenomen [24] eller används i den tyska nätplattformen [25]. I dessa scenarier, de system som nås och behandlas petabyte av data, och vi är övertygade om att den strategi de använder är den mest lämpliga för att hantera de stora mängder data som finns i LOD molnet. Vi kommer att ge en viss bakgrund om WS-baserad tillgång till datakällor, innan vi beskriver mer i detalj vårt genomförande. Men först ska vi helt kort introducera läsaren till den senaste tekniken av distribuerade frågesystem. En annan typ av arkitektur för åtkomst till distribuerade data är frågeförbundssystem. Federerade arkitekturer utgör en ram inom vilken flera databaser kan ansluta sig till en federation. Som medlemmar i förbundet utökar varje databas sitt schema till att omfatta undergrupper av de uppgifter som finns i de andra medlemsdatabaserna. I de flesta fall stöds en virtualiserad metod för detta tillvägagångssätt [33]. I [34], en allmän arkitektur 9 presenteras med följande komponenter: frågetolk, fråga rewriter, frågeoptimer, plan förfining komponent och frågeutförande motor. Vi baserar vårt tillvägagångssätt på att utöka ett frågeförbundssystem (OGSA-DQP [13]) som bygger på ett dataarbetsflödessystem (OGSA-DAI [12]) som är inriktat på att hantera stora mängder data i e-vetenskapstillämpningar [35, 36], som vi nämnde tidigare. I nästa underavsnitt beskriver vi arkitekturen i det utvidgade systemet och de specifika egenskaperna för att hantera stora mängder data: dataströmning och processparallalisering. OGSA-DAI och OGSA-DQP 10 är ett ramverk som möjliggör åtkomst, omvandling, integration och leverans av distribuerade dataresurser. De dataresurser som stöds av OGSA-DAI är relationsdatabaser, XML-databaser och filsystem. Dessa funktioner är gemensamt aktiverade genom användning av dataflöden som utförs inom ramen för OGSA-DAI. Komponenterna i dataflödena är aktiviteter: väldefinierade funktionella enheter (data går in, datan drivs på, data kommer ut) och kan ses som likvärdiga med programmeringsspråkmetoder. En viktig egenskap hos arkitekturen är att data strömmar mellan aktiviteter så att dessa data kan konsumeras av nästa aktivitet i arbetsflödet så snart det är utdata. Det andra viktiga inslaget i arbetsflödets exekveringsmotor är att alla 9 I själva verket är denna arkitektur generisk för alla typer av frågebehandlingssystem, inte bara distribuerade frågeprocessorer 10 http://www.ogsadai.org.uk/ aktiviteter inom ett dataflöde utförs parallellt: dataströmmar går igenom aktiviteter på ett rörledningsliknande sätt (så snart en dataenhet behandlas av en aktivitet buffras denna dataenhet eller skickas till nästa aktivitet i rörledningen), och varje aktivitet fungerar på en annan del av en dataström samtidigt. Den distribuerade frågeprocessorn (DQP) [13] är en uppsättning aktiviteter inom ramen för OGSA-DAI som utför SQL-frågor på en uppsättning distribuerade relationsdatabaser som hanteras av OGSA-DAI. OGSA-DQP får som indata en SQL-fråga adresserad till en uppsättning distribuerade databaser. Den tolkar frågan som identifierar till vilken av databaserna i federationen dessa frågor behandlas, och skapar ett dataflöde med hjälp av OGSA-DAI aktiviteter. Detta dataflöde utförs i OGSA-DAI-arbetsflödets exekveringsmotor och resultaten skickas tillbaka till kunden. Installationen av OGSA-DAI/DQP kan göras i flera webbprogramservrar, beroende på hur mycket vi vill distribuera behandlingen och hur många fjärrdata som vi vill komma åt. Standardkonfigurationen är en OGSA-DAI instans som körs i en webbserver för varje datakälla vi vill komma åt, men andra konfigurationer är tillgängliga. Till exempel kan det vara möjligt att konfigurera OGSA-DAI med en enda server som skulle vara ansvarig för att komma åt alla dataset i federationen. Figur 3 visar en möjlig installationskonfiguration för OGSA-DAI. I denna figur finns det en huvudnod (HQResource) som ansvarar för samordningen av sammanslutningen av datakällor. Vid start, denna nod samlar information om de befintliga datakällor som är insvept vid fjärr OGSA-DAI. I figuren finns det två andra OGSA-DAI noder som exponerar fjärrdata. I detta exempel exponerar vi en RDF-databas och två SPARQL-slutpunkter. SPARQL-slutpunkter hanteras på ett något annorlunda sätt än andra dataresurser (SQL- och RDF-databaser): de kan laddas dynamiskt i fjärrdatanoder utan att tidigare konfigurera dem. Behandlingen av en distribuerad SPARQL-fråga presenteras i nästa avsnitt. Ur en hög nivå synvinkel kan SPARQL-DQP definieras som en förlängning av OGSA-DQP som överväger ytterligare ett frågespråk: SPARQL. Designen av SPARQL-DQP följer tanken på att lägga till en ny typ av datakälla (RDF-datakällor) till de standarddatakällor som hanteras av OGSA-DAI, och utöka de tolkar, planerare, operatörer och optimatorer som hanteras av OGSA-DQP för att hantera SPARQL frågespråk. Vi utökar OGSA-DQP för att acceptera, optimera och distribuera SPARQL-frågor över olika datanoder. SPARQL-DQP läser SPARQL-frågan, den skapar en grundläggande logisk frågeplan (LQP), optimerar den, därefter väljer den vilka noder som ska köras den frågeplanen, och slutligen kör den frågeplanen med hjälp av arbetsflödesmotorn. För det behövs en ny koordinator för den distribuerade frågebehandlaren (HQResource i figur 3 ). Denna samordnare utökar den ursprungliga OGSA-DQP-samordnaren på ett sådant sätt att den accepterar SPARQL-frågor. Även andra komponenter utökas eller utvecklas som den nya OGSA-DQP datalexikon som innehåller information om federationsnoder, SPARQL frågetolk och SPARQL LQP builder plus dess optimizer. Vid initieringstid kontrollerar SPARQL-DQP resursen tillgängligheten av datanoder där federationen kommer att utföras, och får sina egenskaper som lagras i ett datalexikon. Dessa egenskaper är information om ad hoc-funktioner som införts av fjärrenheten RDF-resursen, datanodinformation (som säkerhetsinformation, anslutningsinformation och datanodadress) och tabellmetadata (för närvarande endast RDF-förvarets namn, som ska utökas med statistik över data i datauppsättningarna). Denna information används för att bygga SPARQL LQP och konfigurera federationen. SPARQL LQP Builder tar det abstrakta syntaxträdet som genereras av SPARQL-tolken och producerar en logisk frågeplan. Den logiska frågeplanen följer semantiken som definieras av SPARQL-WG 11 i SPARQL 1.1 Federated Query extension specification [7], som också formaliseras i avsnitt 1.2. Den frågeplan som tagits fram representerar SPARQL-frågan med hjälp av en blandning av operatörer och aktiviteter som kommer från de befintliga i OGSA-DQP och de nytillkomna SPARQL-operatörerna (som SPARQL-facket, filter, specifika SPARQL-optimeringar, skanningar osv.). Därefter tillämpas OGSA-DQP-kedjan av optimatorer, och vi lägger till omskrivningsregler baserade på väl utformade mönsterbaserade optimeringar. Dessutom måste säkerhetsregler kontrolleras som vi beskrev i avsnitt 3.1, eftersom vissa SQL-optimatorer endast kan tillämpas på säkra SPARQL-mönster. I det sista skedet av frågebehandling, de genererade fjärrförfrågningar och lokala delarbetsflöden utförs och resultaten samlas in och returneras av aktiviteten.  I detta avsnitt beskriver vi kortfattat liknande system som ger ett visst stöd till SPARQL frågeförbund. Några av de befintliga motorer som stöder SPARQL 1. [40]............................................................... Vi anser dock inte att det är här eftersom det använder frågespråket SeRQL istället för SPARQL. Vi kommer nu att kort beskriva vart och ett av dessa system. ANAPSID implementerar två adaptiva operatörer: agjoin och angränsande operatörer. Agjoin operatören använder en hash gå tillsammans med lagring gå tuples för att påskynda gå med operatörer. Den angränsande operatören döljer förseningar som kommer från datakällorna och utför avreferenser för vissa predikat. Systemet av Ladwig et al. [38] implementerar en anslutning operatör som heter Symmetric Index Hash Join (SIHJoin), som kombinerar frågor till avlägsna SPARQL-slutpunkter med frågor till lokala RDF datalager. När denna situation inträffar lagras data som hämtas från den lokala RDF-datauppsättningen i en indexhashstruktur för snabbare åtkomst när man utför en anslutning med fjärrdata. Författarna FedX utökar också Sesame 15 och baserar sina optimeringar i gruppering ansluter sig som är riktade till samma SPARQL endpoints och regel gå optimizer med hjälp av en heuristik-baserad kostnadsberäkning. FedX minskar också antalet mellanliggande anslutningar genom att gruppera uppsättningar av kartläggningar i en enda subquery (exklusiva grupper) och även bundna ansluter sig, en teknik som använder resultaten från en avlägsen exklusiv grupp för att begränsa nästa grupperade fråga med hjälp av SPARQL UNION. SPLENDID utökar Sesam 16 lägga till en statistikbaserad gå reordering system. SPLENDID baserar sina optimeringar i gå omordningsregler baserade i en kostnadsmodell som beskrivs i [37]. Statistiken samlas in från VoID-beskrivningar och gör det möjligt att gå med i omordning på ett effektivt sätt. SemWIQ är ett medlarbaserat system, där heterogena datakällor (tillgängliga som CSV-filer, RDF-dataset eller relationsdatabaser) nås av en medlare via omslag. Frågor uttrycks i SPARQL och betrakta OWL som ordförrådet för RDF-data. SemWIQ använder Jenas SPARQL-processor ARQ för att generera frågeplaner och använder sina egna optimers. Dessa optimerare består huvudsakligen av regler för att flytta ner filter eller unary operatörer i frågeplanen, tillsammans med gå omordning baserat på statistik. Systemet har en registerkatalog som anger var de källor som ska frågas ut är och vilket ordförråd som ska användas. För närvarande hanterar systemet inte SPARQL-slutpunkter, men detta uppdateras vid tidpunkten för skrivandet av detta papper. 15 En ram för behandling av RDF-data 16 http://www.openrdf.org/ DARQ utökar Jenas SPARQL-processor ARQ. Den här utbyggnaden kräver att en konfigurationsfil bifogas SPARQL-frågan, med information om SPARQL-slutpunkter, ordförråd och statistik. DARQ tillämpar logiska och fysiska optimeringar, fokuserade på att använda regler för att skriva om den ursprungliga frågan innan frågeplanering (för att slå samman grundläggande grafmönster så snart som möjligt) och flytta värdebegränsningar i subqueries för att minska storleken på mellanliggande resultat. Andra viktiga nackdelen med DARQ är att det bara kan utföra frågor med bundna predikat. Tyvärr upprätthålls DARQ inte längre. Nätverkade grafer skapar grafer för att representera vyer, innehåll eller omvandlingar från andra RDF-grafer, och gör det möjligt att ställa frågor om sammansättningen av uppsättningar grafer på ett integrerat sätt. Implementeringen tar hänsyn till optimeringar såsom tillämpning av distribuerade semi-join optimeringsalgoritmer. Syftet med vår utvärdering är att visa att den valda arkitekturen (utvidgningen av ett välkänt databehandlingssystem) är mer lämplig för behandling av de stora mängder RDF-data som finns tillgängliga på webben, särskilt när avlägsna SPARQL-slutpunkter inte innebär någon begränsning över den mängd resultat som returneras. För det bestämde vi oss för att köra experimenten i en okontrollerad miljö som webben. I denna okontrollerade miljö beteendet av endpoints och latenser kan variera till stor del mellan utföranden, vilket leder till utvärderingsresultat som inte är tydligt jämförbara mellan olika system och replikerbara. Trots det, dessa utvärderingsresultat ger några indikationer om beteendet hos dessa system som kommer att vara viktigt för att karakterisera varje verktyg. Vi kör också utvärderingen i en kontrollerad miljö med hjälp av syntetiska data som kommer att distribueras över flera SPARQL-slutpunkter. I denna utvärdering kommer vi att visa beteendet hos de optimeringstekniker som föreslås i avsnitt 3.1, och hur dessa optimeringstekniker minskar mängden mellanliggande resultat av SPARQL-frågor och därmed hur dess användning faktiskt minskar den tid som krävs för att behandla frågor jämfört med icke optimerade metoder. Vi jämförde vårt system med FedX 1.1 och FedX 1.1 med SERVICE, ARQ (2.8.8) och RDF::Query (2.908). Vi valde dessa system eftersom två av dem är en del av den officiella SPARQL-implementationen och FedX är baserad i Sesam med hjälp av en virtualiseringsstrategi. Dessutom lägger FedX 1.1 till statistiska modeller för att ansluta omordning och SERVICE nyckelord till sin normala federerade frågebehandling motor. När FedX inte använder SERVICE, använder det predikaten i frågan för att identifiera rätt datauppsättning som frågorna ska riktas till vilket gör att systemet för att fråga fler SPARQL-slutpunkter än de andra systemen. För att ge en mer rättvis jämförelse när vi frågar syntetiska data, anpassade vi de datauppsättningar som beskrivs i nästa avsnitt så att predikaten i varje SPARQL endpoint inte upprepas över dem. På detta sätt kan FedX unikt identifiera varje datauppsättning genom att titta på trippelmönstret predikat så att en mer rättvis jämförelse kan göras. Således jämför vi två gånger med FedX: först jämför vi med FedX med hjälp av SERVICE-operatören och bredvid FedX med hjälp av virtualiseringen av avlägsna SPARQL-slutpunkter. När det gäller frågan exekvering, ARQ skiljer sig från andra implementationer av SPARQL 1.1, eftersom det genererar binda gå frågor som FedX, vilket också resulterar i generering av många SPARQL-frågor till samma fjärrslutpunkt och ibland många anslutningsfel från dessa servrar. RDF::Query är det sista systemet som utvärderas och det som följer algoritmerna som beskrivs i det officiella SPARQL 1.1-dokumentet. I denna utvärdering valde vi en representativ uppsättning system men utan att helt täcka den senaste tekniken i distribuerade SPARQL frågebehandlingssystem. Syftet med detta avsnitt är att ge en översikt över de vanligaste systemarkitekturerna för att federera SPARQL-frågor, inte att genomföra en uttömmande utvärdering av de befintliga SPARQL-federationssystemen. Vi återanvända många av de frågor som föreslås i Fedbench [41]. Fedbench föreslår tre uppsättningar av frågor: en tvärdomän uppsättning frågor som distribuerar frågor över allmänt använda SPARQL endpoints såsom DBpedia 17 och LinkedMDB endpoint 18; life sciences uppsättning frågor som utvärderar hur system fråga en av de största domänen i LOD molnet; slutligen Fedbench föreslår också användning av SP2Bench [42] utvärderingsriktmärke, fokuserad på att utvärdera robustheten och prestanda RDF datalager. Frågorna i Fedbench-utvärderingsramen tar dock inte hänsyn till SPARQL 1.1 förlängningen av Federated Query. Detta innebär att frågorna 17 http://dbpedia.org/sparql 18 http://data.linkemdb.org/sparql inte innehåller nyckelordet SERVICE, utan att frågemotorerna i stället måste identifiera till vilket mål som styr varje del av dessa frågor. Vi ändrade manuellt frågorna lägga till SERVICE nyckelordet där det behövs. Dessutom innehåller Fedbench inte många SPARQL mönster som är vanliga i de flesta användarfrågor som FILTER eller OPTIONAL [43]. Titta noga, frågorna i den ursprungliga Cross Domain frågeuppsättningen inte innehåller något SPARQL mönster som använde antingen OPTIONAL eller FILTER operatörer. Från det totala antalet frågor som lämnats in till DBpedia i en månad OPTIONAL operatören används i 39% av dessa frågor och FILTER operatören används i en 46% av dem [43]. Således bestämde vi oss för att komplettera frågeuppsättningen med frågor som innehåller kombinationer av dessa saknade mönster (FILTER och OPTIONAL).Life sciences domänfrågor innehåller en mängd olika SPARQL frågor, inklusive OPTIONAL, FILTER och UNION operatörer, därför bestämde vi oss för att inte lägga till någon ny fråga till de befintliga. SP2Bench-frågor hämtas från det ursprungliga riktmärket som syftar till att mäta prestandan hos RDF-databaser, och därför måste vissa anpassningar göras om vi vill använda det inom distribuerade SPARQL frågeprocessorer. I denna uppsättning av frågor också några viktiga frågemönster saknas, och därmed lade vi till några frågor för att lösa detta problem. För att utvärdera de tidigare systemen i en okontrollerad miljö som webben av data, kör vi alla beskrivna frågor fem gånger och vi tillämpar ett aritmetiskt medelvärde för resultaten av dessa fem frågor. På så sätt ger vi en mer homogen uppsättning resultat som bättre återspeglar systemens verkliga prestanda. Vi utför också två uppvärmningsförfrågningar för att undvika initial fördröjning av systemkonfigurationen på deras första körning. Vi lade till tre frågor till korsdomänen frågeuppsättningen och fem fler frågor till SP2Bench uppsättningen av frågor. Den nya korsdomänen är fråga CDQ4b, CDQ8 och CDQ9 i bilaga C. I CDQ4b lade vi till en ny FILTER till den ursprungliga frågan (crossdomän fråga 4 i [41]), frågar nu för de aktörer som visas i någon NY Times nyheter, filtrering för filmen "Tarzan". Frågor, CDQ8 och CDQ9 är helt nya. I CDQ8 frågar vi DBpedia och El Viajero [44] SPARQL endpoint 19 för data om länder och befintliga reseböcker, vi filtrerar för länder med en yta större än 20 000 km 2. I CDQ9 frågar vi DBpedia för länder och valfritt får vi de befintliga reseböckerna för dessa länder från El Viajero endpoint, slutföra denna information med klimatdata på CIA world factbook SPARQL endpoint 20. Därefter visar vi CDQ9 för att ge läsaren en uppfattning om vilken typ av frågor som vi överväger: Vi lade också till fem frågor till SP2Bench uppsättning av frågor i Fedbench, som är en förlängning av SP2Bench frågor 7 och 8, som ber om förfaranden eller tidskrifter och deras författare. Vi lade till en extra grad av komplexitet först genom att lägga till OPTIONAL till dessa frågor. SP2BQ7b ber om tidskrifter, valfritt får den författarnas publikationer i en konferens, och senare får den även författarnas namn. Vi ändrade SP2BQ8 för att be om papper i vissa papperssamlingar istället för att be om tidskriftspapper eftersom SP2BQ7 redan ber om det. SP2BQ8b frågar efter alla människor och får valfritt alla de papper som dessa personer publicerade i en konferens för senare att gå med i resultaten med de människor som publicerade en tidning i en samling. SP2BQ7c frågar efter alla tidskrifter, få sina författare med en valfri och filtrering för antalet sidor. Fråga SP2BQ8c är den mest komplexa frågan eftersom den frågar 4 olika SPARQL endpoints. I denna fråga, vi frågar efter alla papper i en konferens, valfritt få de människor som skrev dem, nästa fråga för de författare som också skrev en tidskrift papper och även papper som är i en papperssamling. Fråga SP2BQ8d ber om alla dokument i konferensförfaranden, valfritt erhålla sina författare och begränsa utdata till dessa förfaranden från och med 1950. Till de tidigare frågorna lägger vi till frågorna i [45]. Dessa frågor följer följande väg: först, fråga GeneId endpoint vi få Pubmed som vi använder för att komma åt Pubmed endpoint (kräver Q1 och Q2). I 19 http://webenemasuno.linkeddata.es/sparql 20 http://www4.wiwiss.fu-berlin.de/factbook/sparql dessa frågor hämtar vi information om gener och deras referenser i Pubmeds dataset. Från Pubmed får vi tillgång till informationen i National Library of Medicines kontrollerade vokabulär thesaurus (kräver Q3 och Q4), lagrad på MeSH endpoint, så vi har mer fullständig information om sådana gener. Slutligen, för att öka de data som hämtas genom våra frågor, har vi också tillgång till HHPID endpoint (kräver Q5, Q6 och Q7), som är kunskapsbasen för HIV-1-proteinet. Dessa frågor finns i [45]. För de korsdomänfrågor som nämns i [41] använde vi de datauppsättningar som finns tillgängliga vid DBpedia, Linked-MDB, Geonames, New York Times och El Viajero SPARQL-slutpunkter. Vi laddade inte ner någon data till en lokal server, istället frågade vi direkt dessa endpoints. Vi gjorde på samma sätt för life science frågor, tillgång till standard SPARQL endpoints (som är Drugbank, Kegg och DBpedia). För SP2Bench-frågor, genererade vi en datauppsättning på 1.000.000 tripletter som vi klustrade in i 5 olika SPARQL-slutpunkter i en lokal server. De lokala SPARQL-slutpunkterna var Journal (410.000 tripletter), Incollections (8.700 triples), InProceedings (400.000 triples), People (170.000 triples) och Masters (5.600 triples). Vår utvärdering gjordes på en Pentium Xeon med 4 kärnor och 8 GB minne som drivs av en Ubuntu 11.04. De uppgifter och frågor som används i denna utvärdering finns på http://www.oeg-upm.net/SparqlDQP/jws. Resultaten av vår utvärdering visas i figurerna 4, 5 och 6 för Fedbench uppsättningar av frågor i bilaga C. Uppgifterna för att generera dessa diagram finns också i bilaga B. I den bilagan tabell B.1, B.2 och B.3 presentera resultaten av frågeutföranden. För life sciences uppsättning frågor hänvisar vi till tabell B.2 och även till det tidigare arbetet som fanns i [45]. Vi representerar som 600 000ms de frågor som behöver mer än 10 minuter för att besvaras av de utvärderade systemen (SPARQL-DQP, SPARQL-DQP optimerad, ARQ, RDF::Query och FedX 1.1 med SERVICE och utan det). Resultaten presenteras i logaritmisk skala. De resultat som presenteras i figur 4 visar hur de utvärderade systemen utförs i Cross-domänen uppsättning av frågor. Dessa frågor visar hur systemen beter sig i en typisk situation, där användare frågar några av de vanligaste SPARQL endpoints. Dessa endpoints, som kommenterats tidigare, har varit DBpedia, NYTimes endpoint, LinkedMDB, Geonames, El Viajero och CIA World Factbook. Dessa avlägsna endpoints brukar återgå mellan 10 000 och 2,00 resultat. Detta gör att alla system svarar på frågor i rimliga tider. Ett av problemen vid fjärrsökning av SPARQL-slutpunkter är uppdateringsfrekvensen för de data som finns i datauppsättningarna. Ibland, när du frågar dessa endpoints data kan ha uppdaterats och de frågor som använts tidigare kan inte returnera samma resultat (eller några) igen. Detta är situationen i frågorna 5, 6 och 7, där det inte finns några resultat tillbaka. I utvärderingen av dessa frågor, FedX 1.1 utan att använda SERVICE sökord är det snabbaste eftersom det använder först en fråga fråga för att veta att det kommer att bli något resultat eller inte. När det gäller genomförandet av resten av frågorna, alla system utförs på samma sätt, särskilt i de fyra första frågorna och i fråga 4b. För samma fråga 4b, alla system returnerade samma mängd resultat, utom för båda FedX-versioner: FedX 1.1 med hjälp av SERVICE returnerar 84 resultat medan FedX-versionen som virtualiserar en lista över SPARQL-slutpunkter om de var en enda ger inga resultat. I fråga 8, FedX använder SERVICE ger en utvärdering fel på grund av användningen av statistisk-baserade mönster omordning ("det stöds inte filter omordning utan statistik") och FedX utan SERVICE returnerar inga resultat. Skillnaden i mängden resultat mellan båda FedX-smakerna är att de använder ett annat tillvägagångssätt för att fråga ut de avlägsna SPARQL-slutpunkterna. Medan FedX-smaken som implementerar SERVICE-operatören endast frågar de angivna RDF-datauppsättningarna, virtualiserar den andra versionen av FedX alla RDF-datauppsättningar i sin lista och använder därmed en annan strategi för frågeutvärdering (FedX utan SERVICE frågar alla SPARQL-slutpunkter i sin lista som hämtar så mycket data som möjligt). De andra systemen utfördes på samma sätt, men ARQ behövde mer tid än de andra, nästan en storleksordning. ARQ infogade också FILTER-uttrycket i SERVICE-anropet, vilket gav en annan mängd resultat som de andra systemen som implementerar SPARQL 1.1 Fed. I den sista frågan, SPARQL-DQP presterar bättre än de andra som antingen inte stannar (RDF::Query och ARQ inte avsluta sin behandling) eller ge ett fel i frågeutförandet (FedX med SERVICE: "vänster gå med eller stöds för kostnadsoptimering"). Vi tycker att SPARQL-DQP presterade bättre på grund av den valda arkitekturen. Några av de endpoints som ställdes i CDQ9 returnerade 10 000 resultat, vilket är en signifikant ökning jämfört med de andra endpoints som ställdes (normalt gav de 2 000 resultat). När mängden data ökade, vårt system presterade bättre, som fråga CDQ9 visade. Den mängd resultat som returnerades för dessa frågor var av 8.604 forclically när den bundna gå frågeteknik användes. När det gäller SPARQL-DQP och de andra systemen fungerade de på samma sätt, men när uppgifterna ökade i fråga LS7. I den situationen fungerade SPARQL-DQP bättre än andra system. De genomförda optimeringarna (särskilt genomförandet av de mönsteromordningsregler som beskrivs i avsnitt 3.1) är mindre märkbara när mängden överförda data (och antalet mellanliggande resultat) är lägre, men det finns ingen förlust av prestanda i tillämpningen av reglerna. Resultaten i figur 6 visar hur de utvärderade systemen uppförde sig med större datamängder. I denna utvärdering har SPARQL-slutpunkterna inga resultatbegränsningar, vilket är av avgörande betydelse för utvärderingen. Konfigureringen av endpoints är följande: Människor endpoint innehåller 82.685 personer med namn, InProceedings endpoint innehåller 65.863 i förfaranden med författare, InCollections innehåller 615 papper i tillhör en samling av papper med författare, och Journal endpoint innehåller 83.706 tidskrifter med författare. Totalt använde vi 1.000.000 tripletter fördelade i tidigare endpoints. Ur ett resultatperspektiv, alla system som genomför SPARQL 1.1 Federated Query förlängning returnerade samma mängd resultat i den första uppsättningen frågor (SP2BQ1 till SP2BQ5). I resten av frågorna, återigen de system som genomför SPARQL federation förlängning returnerade samma mängd resultat, medan FedX (som inte använder SERVICE) returnerade (om möjligt) olika belopp på grund av FedX har tillgång till SPARQL endpoints virtualisera dem alla i stället för att peka varje del av frågan till den datauppsättning användaren anger. När det gäller de tider som krävs för att utföra utvärderingsfrågorna, alla system som utförs på samma sätt i de fem första frågorna, är SPARQL-DQP lite värre än de andra men bättre än RDF::Query som var det sämre systemet i frågor SP2BQ3, SP2BQ4 och SP2BQ5. I dessa frågor, båda versionerna av FedX utförde bet- de system som följer SPARQL 1.1 Federation dokument. De optimeringar som presenteras i Avsnitt 3.1 tillämpades i frågor CDQ4b, CDQ8 och CDQ9 men de minskade inte slutresultatet tider. Detta beror på att mängden uppgifter som överfördes mellan frågeoperatörerna inte var tillräckligt betydande. Figur 5 visar de tider som behövs för att utvärdera frågor Life Science domän. Vi lade inte till någon extra fråga till utvärderingen, eftersom frågeuppsättningen redan innehåller de vanligaste mönster som används i SPARQL-frågor, och en mer fullständig utvärdering inom life science-domänen finns i [45]. Liksom i den tidigare uppsättningen av frågor, RDF dataset uppdaterades och vissa frågor (LSQ4 och LSQ5) inte returnerade något resultat. I allmänhet uppförde sig alla system på samma sätt i denna uppsättning av frågor. ARQ utförde lite värre, främst på grund av hur den hanterar anslutningarna med de avlägsna SPARQL endpoints (ARQ genererar en uppsättning bindande frågor som begränsar några av de fjärr SPARQL frågor som genererar en överbelastning över de avlägsna endpoints, vilket var ett vanligt problem för alla system). Life Science-domänen SPARQL-slutpunkter avvisar vanligtvis frågor från en värd när alltför många anslutningar tillfrågas, vilket vid en intensiv utvärdering kan vara ett vanligt problem. Life sciences servrar betedde sig värre i vår utvärdering återvändande server fel, spe- ter än de andra systemen. Vi tror att detta beror på användningen av dess arkitektur design som parallelliserar utförandet av frågorna och användningen av BIND GÅ teknik. I SP2BQ6 återsändes inget av systemen i rimliga tider, inte på grund av mängden överförda uppgifter utan på grund av den tid som behövs för behandlingen av dessa uppgifter. I resten av frågorna (SP2BQ7, SP2BQ7b, SP2BQ7c, SP2BQ8, SP2BQ8b, SP2BQ8c, SP2BQ8d) endast SPARQL-DQP och SPARQL-DQP utan optimeringar avkastning resultat i tid. Anledningen till SPARQL-DQP avkastning resultat i rimliga tider är valet av dess basarkitektur. Vi utökar en arkitektur utformad för att arbeta i dataintensiva scenarier (t.ex. [24]), som bygger på ett dataarbetsflödessystem med hjälp av en strömmande modell för överföring av data. I den arkitekturen utförs varje fråge-/databehandlingsaktivitet samtidigt, antingen i en fjärrnod i federationen eller i huvudnoden i konfigurationen [13] och uppgifterna förbrukas också så snart de genereras. När det gäller de optimeringar som beskrivs i avsnitt 3.1 är det möjligt att märka deras effekt speciellt i frågor SP2BQ7b, SP2BQ8b, SP2BQ8c där regel 2 tillämpas. Regel 1 tillämpas också i frågor SP2BQ7c och SP2BQ8d, där det också kan noteras en mindre minskning av verkställighetstiderna. När man tittar på utvärderingen som helhet är det möjligt att observera tre olika uppsättningar resultat från denna utvärdering (notera att i figurerna 4, 5 och 6 finns resultaten representerade i logaritmisk skala och därmed för mer exakta resultat hänvisar vi läsaren till bilaga B). Den första uppsättningen (standard Fedbench Life Sciences domän, Cross domain och SP2-frågor) är de som inte är optimerade eftersom omordningsreglerna i avsnitt 3.1 inte är tillämpliga. Den andra frågegruppen representerar den klass av frågor som kan optimeras med vårt tillvägagångssätt, men där skillnaden inte är alltför relevant, eftersom mindre mängd överförda data (meddelande om att reglerna tillämpas men deras genomförandetid är försumbar). I denna frågegrupp identifierar vi fråga 7 i Life Sciences domänen (LSQ7), Q4 i [45], frågar CDQ4b, CDQ8 och CDQ9 i korsdomänen frågeuppsättning och frågor SP2BQ7c och SP2BQ8d i SP2Bench utvärderingen. Den sista gruppen frågor (kräver SP2BQ7b, SP2BQ8c och SP2BQ8d av SP2bench frågor) visar en tydlig optimering när man använder väl utformade mönster omskrivningsregler. Dessa optimeringar märks bättre när man tittar på resultattabellerna i bilaga B. I det frågar exekveringstider av frågor SP2B8b och SP2B8c minskas i en 50% av sin icke optimerade tid. Detta är ännu mer märkbart när man normaliserar tidsresultaten och använder ett geometriskt medelvärde för att representera dessa resultat, som beskrivs i [46]. I vårt tidigare arbete som presenterades i [45] liknande resultat märktes, speciellt när alltid fråga avlägsna SPARQL endpoints, eftersom mängden tid för överföring av data från flera noder till en annan kommer att vara mycket högre. I fråga SP2BQ8b görs minskningen av mellanliggande resultat genom att först ansluta SER-VICE-anropet till den endpoint som innehåller insamling av vetenskapliga artiklar med den första lösningen kartläggningar från SERVICE-anropet till den endpoint som innehåller data om människor. Mängden mellanliggande resultat minskas avsevärt, vilket särskilt noteras vid genomförandet av den OPTIONAL delen av frågan, när valfritt lägga till lösningskartläggningar från en SERVICE-anrop till den endpoint som innehåller konferenspapper. Utvärderingen kompletterar utvärderingsresultaten från [45] där vi utvärderade systemet (SPARQL-DQP) och omskrivningsreglerna på ett liknande sätt men fokuserar endast på ett life science-område. I denna utvärdering observeras samma resultatmönster, där tre uppsättningar resultat observeras, alla liknande dem som observerats i detta arbete. Från det dokumentet belyser vi nyttan av att tillämpa de omskrivningsregler som beskrivs i avsnitt 3.1: i fråga 6 i [45] varierar mängden överförda data från en sammanfogning av 150, 000 × 10 000 tuples till en sammanfogning av 10, 000 × 23, 841 tuples (med hjälp av Entrez, Pubmed och MeSH endpoints), vilket kraftigt minskade den globala behandlingstiden för frågan. När det gäller de andra systemen uppförde de sig alla på samma sätt. ARQ och RDF::Query Question utvärderingstider var liknande ger samma resultat som SPARQL-DQP eftersom de tillämpar samma SPARQL specifikation. De returnerade inte resultat i samma frågor i SP2B utvärdering och utfördes på samma sätt i Life Science utvärdering, märker samma problem med fjärrservern överbelastningar. FedX och FedX med SER-VICE utfördes också på samma sätt som de andra systemen, men i allmänhet var FedX snabbare än de andra systemen. I detta dokument föreslog vi först en formell syntax för SPARQL 1.1 Federated Query förlängning, tillsammans med en formalisering av dess semantik. I denna studie identifierade vi problemen vid utvärdering av mönstret SERVICE?X, vilket kräver att variabeln?X är bunden innan utvärderingen av hela mönstret. Därför föreslog vi syntaktiska restriktioner för att säkerställa begränsningen av SERVICE?X, vilket gör att vi på ett säkert sätt kan utföra sådana mönster. Vi utökade också den väldesignade mönsterdefinitionen [8] med SERVICE-operatören, som gör det möjligt att ombeställa SPARQL-frågor. Detta sista resultat är av avgörande betydelse eftersom det gör det möjligt att minska mängden mellanliggande resultat i frågeutförandet. Vi implementerade alla dessa begrepp i SPARQL-DQP-systemet och utvärderade det med hjälp av en befintlig utvärderingsram, som vi utvidgade för att täcka ett bredare spektrum av gemensamma SPARQL-frågor. Den första slutsatsen som vi vill lyfta fram är vikten av att använda en särskild arkitektur för att hantera stora mängder data. Som vi har sett i utvärderingsavsnittet har alla system inte kunnat bearbeta från fråga 5 i SP2B-frågan och framåt. Alla system behövde mer än 10 minuter för att svara på dem medan vårt system, SPARQL-DQP avslutade i rimliga tider. Detta beror på den arkitektur som valts, där dataöverföringen görs genom att använda strömmar av data mellan OGSA-DAI noder (data förbrukas så snart den genereras) och databehandlingen sker samtidigt i var och en av dessa noder. OGSA-DAI- och OGSA-DQP-arkitekturer har i hög grad använts i dataintensiva tillämpningar [13, 36] och utan tvekan är datawebben ett dataintensivt scenario. Metoden att följa bör därför vara en metod som behandlar sådana datamängder. Vi betonar också att denna arkitektur är inriktad på att hantera SPARQL-slutpunkter utan resultatbegränsning, vilket inte är vanligt i de nuvarande slutpunkterna som är tillgängliga för vanliga användare. Men om en mer erfaren användare vill få tillgång till obegränsade SPARQL-slutpunkter, krävs en mer robust strategi än de befintliga. Även om arkitekturen är fokuserad för att hantera stora mängder data, SPARQL-DQP fungerar inte dåligt när det gäller begränsade SPARQL-slutpunkter. Nästa slutsats som vi vill lyfta fram är tillämpligheten av de omskrivningsregler som presenteras i avsnitt 3.1. Som vi har sett i utvärderingsavsnittet minskar tillämpningen av dessa regler verkställighetstiden när ett väl utformat mönster av formuläret ((P 1 OPT P 2 ) OCH P 3 ) eller (P 1 FILTER R) OCH P 2 ) finns i SPARQL-frågan. Denna situation visas i fråga SP2BQ8c.rq, där det finns fyra fjärrsamtal SERVICE tillsammans med en OPTIONAL operatör och två gå med operatörer. Mängden mellanliggande resultat i denna fråga reduceras kraftigt när det första omskrivningsmönstret tillämpas i början av frågeutförandet. Vi betonar också att dessa omskrivningsregler kan tillämpas på alla väl utformade mönster, och kostnaden för att tillämpa dem är försumbar i de flesta scenarier. Dessutom, för att kontrollera om en SPARQL fråga är väl utformad och för att kontrollera safeness villkor som nämnts tidigare kan producera vissa overhead, men det är försumbart också, särskilt när SPARQL frågor skala ut i mängden returnerade resultat. Förutom detta lilla bevis på koncept, hänvisar vi läsaren till [45]. I detta arbete används omskrivningsreglerna mer intensivt, och de resultat som lyfts fram här kan också iakttas i det arbetet. Verktyg för att federera frågor över webben av data släpps ofta. Denna ökning av verktygen för att få tillgång till distribuerade RDF-data är bara det första steget mot ett viktigare mål: att på ett effektivt och ändamålsenligt sätt fråga ut datawebben. För närvarande finns det tusentals dataset, och att välja till vilken punkt SPARQL frågor är en komplicerad uppgift, och en del av forskningen av distribuerade SPARQL frågebehandling bör syfta till att lösa så stora problem. Att fokusera mer på specifika aspekter av SPARQL:s frågeförbund var ett av de vanligaste problemen som vi var tvungna att ta itu med var instabiliteten i nätanslutningarna. Dataöverföring kan avbrytas ofta vilket gör det svårt att fråga LOD molnet. Vi tror att en metod för att lösa dessa problem som vi upplevt är införandet av adaptiva frågebehandlingsmetoder [47] som de som finns i [10]. Dessutom är utforskandet av datasetdynamiken en viktig fråga att ta itu med [48] eftersom data förändrades under våra utvärderingar. Ett intressant bidrag, som fokuserar mer på de teoretiska aspekterna av detta forskningsarbete, skulle vara en analys av de väl utformade mönstrens tillämplighet på SPARQL-subqueries. En del arbete med detta ämne har redan utförts [49, 50] men det finns fortfarande utrymme för förbättringar. Medgivanden
Vårt tillvägagångssätt är baserat på standardiserade federerade frågor på WoD REF.
Federating queries in SPARQL 1.1: Syntax, semantics and evaluation
{'venue': 'J. Web Semant.', 'journal': 'J. Web Semant.', 'mag_field_of_study': ['Computer Science']}