Abstrakt. Vi anser följande problem: med tanke på en märkt riktad graf G och ett reguljärt uttryck R, hitta alla par av noder som är anslutna genom en enkel väg så att konkatering av etiketter längs vägen uppfyller R. Problemet motiveras av observationen att många rekursiva frågor i relationella databaser kan uttryckas i denna form, och genom genomförandet av ett frågespråk, G +, baserat på denna observation. Vi visar att problemet i allmänhet är intractable, men presentera en algoritm än körs i polynomial tid i storleken på grafen när det reguljära uttrycket och grafen är fria från konflikter. Vi presenterar också en klass av språk vars uttryck alltid kan utvärderas i tid polynom i storleken på både grafen och uttrycket, och karakterisera syntaktiskt uttrycken för sådana språk. Nyckelord. Etiketterade riktade grafer, NP-fullständighet, polynom-tidsalgoritmer, reguljära uttryck, enkla sökvägar AMS(MOS) ämnesklassificeringar. 68P, 68Q, 68R 1. Inledning. Mycket av framgången med relationsmodellen av data kan tillskrivas dess enkelhet, vilket gör det både amenable till matematisk analys och lätt för användare att förstå. I detta senare avseende har tillgången till icke-processuella frågespråk varit en stor tillgång. Men det faktum att frågor som är särskilt användbara i nya tillämpningsområden inte är uttryckliga i traditionella frågespråk har lett till förslag på mer kraftfulla frågespråk, såsom logik-baserat språk Datalog [23] och vårt frågespråk G + [9, 10]. I det ursprungliga förslaget till relationsmodellen ingick två frågespråk med motsvarande uttryckskraft: relationskalkylen och relationsal algebra [7]. Dessa språk har använts som måttstock genom vilken andra frågespråk klassificeras; ett frågespråk sägs vara relationsfullt komplett om det har (åtminstone) den uttryckskraft relationskalkylen har. Detta begrepp om fullständighet har dock ifrågasatts eftersom det har visat sig att vissa rimliga frågor, såsom att finna en transitiv stängning av ett binärt förhållande, inte kan uttryckas i analysen [3, 4]. Denna speciella begränsning övervinns på språken G + och Datalog genom deras förmåga att uttrycka rekursiva frågor. Utformningen av G + bygger på observationen att många av de rekursiva frågor som uppstår i praktiken-och i litteraturen-lika med graf traversals (till exempel, [1, 12, 19] ). I G +, Vi ser databasen som en riktad, märkt graf, och posera frågor som är graf mönster; svaret på en fråga är uppsättningen av subgrafer i databasen som matchar det givna mönstret. Användbara tillämpningar för ett sådant språk kan hittas i system som representerar transportnät, kommunikationsnät, hypertextdokument och så vidare. I vår prototypimplementering ritas frågor på en arbetsstationsskärm och databas- och frågeresultat visas också bildligt.
Mendelson och Wood visar att hitta alla enkla vägar i en (deterministisk) graf som matchar ett reguljärt uttryck är NP-hård REF.
Finding Regular Simple Paths In Graph Databases
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}