Diagramdatabaser i många applikationer-semantiska nät, transporter eller biologiska nätverk bland annat-är inte bara stora, men också ofta modifierade. Att utvärdera graffrågor i detta dynamiska sammanhang är en utmanande uppgift, eftersom dessa frågor ofta kombinerar första ordningen och navigeringsfunktioner. Motiverad av de senaste resultaten om att bibehålla dynamisk tillgänglighet studerar vi den dynamiska utvärderingen av traditionella frågespråk för grafer i den beskrivande komplexitetsramen. Vårt fokus ligger på att upprätthålla regelbundna sökvägar, och förlängningar därav, genom första ordningen formler. I synnerhet är vi intresserade av sökvägar som definieras av icke-regelbundna språk och av utökade konjunktiva regelbundna sökvägar (som gör det möjligt att jämföra etiketter av sökvägar baserade på ordrelationer). Vidare studerar vi de nära relaterade problemen med att hålla avstånden i grafer och nåbarhet i produktgrafer. I denna förstudie får vi övre gränser för dessa problem i begränsade inställningar, såsom oriktade och acykliska grafer, eller endast under införanden, och negativa resultat avseende kvantifierfria uppdateringsformler. Dessutom pekar vi på intressanta riktningar för ytterligare forskning. Nyckelord och fraser Dynamisk beskrivande komplexitet, grafdatabaser, grafprodukter, tillgänglighet, sökvägar Digitala objektidentifierare 10.4230/LIPIcs.xxx.yyy.p Grafdatabaser är viktiga i tillämpningar där datatopologin är lika viktig som själva datan. Intuitivt representerar en grafdatabas objekt (av noder) och samband mellan dessa objekt (ofta modellerad av märkta kanter-se [1] för en undersökning av grafdatabasmodeller). Under de senaste åren har intresset för grafdatabaser ökat, på grund av att tillämpningar som behöver hantera och fråga efter massiva och starkt sammankopplade data, som till exempel den semantiska webben, sociala nätverk eller biologiska nätverk. I de flesta av dessa tillämpningar är databaserna inte bara stora, utan också mycket dynamiska. Data är ofta * Delar av detta arbete ingår också i den tredje författarens avhandling [23]. Dynamiska grafer infogas och tas bort, och därmed också dess nätverksstruktur. Målet med detta arbete är att undersöka hur frågespråk för grafdatabaser kan utvärderas i detta dynamiska sammanhang. Många frågespråk för grafdatabaser kombinerar traditionella första ordningens funktioner med navigeringsfunktioner. Redan grundläggande språk (t.ex. vanliga sökvägar, se t.ex. [21, 2] ) gör det möjligt att testa förekomsten av stigar som uppfyller kraven på deras etiketter (t.ex. följsamhet till ett reguljärt uttryck i reguljära sökvägar frågor). Att beräkna svaren på denna typ av frågor på stora, mycket dynamiska grafer är en stor utmaning. Det är emellertid tänkbart att svar på en fråga före och efter små ändringar är nära besläktade. Således ett rimligt hopp är att kunna uppdatera svaret på en fråga på ett mer effektivt sätt än att recomputing det från grunden efter varje ändring. Ännu mer så om vi tillåter att lagra extra extra extra data som kan underlätta uppdateringsuppgiften. I vilken utsträckning detta är möjligt, och under vilka exakta villkor, är föremål för dynamisk beräknings komplexitet. Här är vi intresserade av att studera den dynamiska komplexiteten i frågespråk för grafdatabaser från ett beskrivande tillvägagångssätt. I den dynamiska beskrivande komplexiteten, som föreslås självständigt av Dong, Su och Topor [9, 8] och av Patnaik och Immerman [16], upprätthåller ett dynamiskt program hjälprelationer med avsikten att hjälpa till att besvara en fråga över en (relations) databas som är föremål för små ändringar (insättningar eller raderingar av tuples). När en ändring sker, uppdateras frågesvaren och varje kompletterande relation med hjälp av första ordningens formler (eller, motsvarande, med kärn-SQL-frågor) som utvärderas över den aktuella databasen och tillgängliga tilläggsdata. Sådana program drar därför nytta av att vara både mycket parallelliserbara (på grund av nära anslutning av första ordningen logik och små djup booleska kretsar) och lätt genomförbar i standard relationella databasmotorer. Klassen av frågor som kan underhållas av första ordningens uppdateringsformler kallas DynFO. Frågespråk för grafer har hittills inte studerats systematiskt i den dynamiska beskrivande komplexiteten. Mycket troligt är att det tills nyligen var inte ens känt om nåbarhet i riktade grafer kunde upprätthållas genom första ordningens uppdatering formler. Att detta verkligen är möjligt visades i [6], Med den omedelbara konsekvensen att alla fasta (konjunktioner av) regelbundna sökvägar frågor kan också upprätthållas. Därför kan regelbundna sökvägar utvärderas på ett mycket parallellt sätt i dynamiska grafdatabaser. Motiverade av detta resultat studerar vi det dynamiska underhållet av mer uttrycksfulla frågespråk. Vårt fokus är på regelbundna sökvägar och förlängningar därav-icke-regelbundna sökvägar frågor och utökade konjunktiva regelbundna sökvägar frågor (kort: ECRPQs). Några tidigare arbeten på icke-regelbundna sökvägar frågor har gjorts. Weber och Schwentick ställde en kontextfri sökväg (Dyck-språket D 2) som kan underhållas i DynFO på acykliska grafer [20]. För den enkla klassen av sökväg-formade grafdatabaser kan också formella språkresultat överföras. Patnaik och Immerman påpekade redan att vanliga språk kan upprätthållas i DynFO [16]. Senare, Gelade et al. systematiskt studerat de formella språkens dynamiska komplexitet [11]. De visade bland annat att vanliga språk kan underhållas med kvantifierfria uppdateringsformler och att alla sammanhangsfria språk kan underhållas i DynFO. Den andra förlängningen av regelbundna sökvägar frågor som ska studeras här är utökade konjunktiva regelbundna sökvägar frågor. I tidigare arbete har det märkts att samband av regelbundna sökvägar (CRPQs) faller kort i expressiv kraft för moderna tillämpningar av grafdatabaser [4]. En funktion som ofta krävs av dessa applikationer är jämförelsen av P. Muñoz, N. Vortmeier, T. Zeume 3 etiketter av vägar definieras av CRPQs baserat på relationer mellan ord (t.ex. prefix, längdbegränsningar, fasta redigeringsavstånd). ECRPQs har införts för att uppfylla detta krav [4], dvs. de generaliserar CRPQs genom att göra det möjligt att testa om flera etiketter av vägar följer givna regelbundna relationer. Två grundläggande egenskaper som uttrycks av ECRPQs är om två par noder är anslutna av banor av samma längd och i så fall, om även banor med samma etikettsekvens finns. I allmänhet förefaller det vara en svår uppgift att upprätthålla resultatet av ECRPQ. I den här artikeln undersöker vi därför underhållet av ECRPQs i begränsade inställningar. Slutligen finns det också ett nära samband mellan utvärderingen av graffrågor och problemet med nåbarhet i omärkta och märkta produktdiagram. Vi diskuterar detta samband (se avsnitt 2) och utnyttjar det i flera av våra resultat. Bidrag Först studerar vi sökväg frågor och visar att alla vanliga sökväg frågor kan upprätthållas med kvantifier-fria formler när endast ingångar är tillåtna, alla sammanhangsfria sökväg frågor kan upprätthållas med första ordningen formler på acykliska grafer, och det finns icke-kontext-fria sökväg frågor underhålls genom första ordningen formler på oriktade och acykliska grafer, liksom på allmänna grafer under ingångar endast. Som ett första steg mot att upprätthålla ECRPQ-värden undersöker vi för vilka grafer längden på sökvägar mellan noder kan bibehållas. Vi ställer ut dynamiska program för att upprätthålla alla avstånd för oriktade och acykliska grafer, samt för riktade grafer när endast ingångar är tillåtna. Det är fortfarande öppet, om avstånd kan upprätthållas i DynFO för allmänna riktade grafer, men vi visar att kvantifierfria uppdateringsformler inte räcker. De tekniker som används för att upprätthålla alla avstånd kan användas för att upprätthålla varianter av ECRPQs i begränsade inställningar. Betrakta utvidgningen av en klass av frågor genom linjära begränsningar av antalet förekomster av symboler på sökvägar med +LC. Denna förlängning infördes och studerades [4]. Vi visar att alla CRPQ+LC kan upprätthållas med första ordningens formler när endast tillägg är tillåtna, och alla ECRPQ+LC kan upprätthållas med första ordningens formler på acykliska grafer. En omedelbar konsekvens av våra resultat för avstånd är att tillgängligheten kan upprätthållas i produkter av (omärkta) grafer för dessa begränsningar. Genom att använda det dynamiska programmet för att upprätthålla matrisernas rang från [6], utökar vi detta resultat till mer allmänna grafprodukter. Dessutom visar vi att par av noder som är sammankopplade med sökvägar med samma etikettsekvens kan bibehållas i acykliska grafer med hjälp av första ordningens uppdateringsformler. Upprätthållandet av problem har också studerats ur algoritmisk synvinkel. En bra utgångspunkt för läsare intresserade av övre gränser för dynamiska algoritmer är [18, 7]; en bra utgångspunkt för lägre bundna tekniker är Miltersens undersökning om cellprob komplexitet [14]. De övre gränserna för nåbarhet som erhålls i [18, 7] omedelbart överföra till dynamisk algoritmisk utvärdering av regelbundna sökvägar frågor (med hjälp av minskningen visas i [6] ). Sammanställning Den dynamiska inställningen och de grundläggande grafen frågespråk införs i Avsnitt 2. Där diskuterar vi också sambandet mellan frågeutvärdering och nåbarhet i produktgrafer. Avsnitt 3 innehåller resultaten om att upprätthålla grafen frågor. Våra resultat för att upprätthålla avstånd och ECRPQ presenteras i Avsnitt 4. I Avsnitt 5 överförs några av resultaten för att upprätthålla graffrågor till nåbarhet i grafprodukter, och vi ger också resultat för nåbarhet i generaliserade grafprodukter. Vi avslutar i avsnitt 6. Detta är en fullständig version av [15]. Tack Vi tackar Pablo Barceló, Samir Datta och Thomas Schwentick för stimulerande och upplysande diskussioner.
Detta är en fullständig version av REF.
Dynamic Graph Queries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}