Abstrakt. Navigationsfunktioner har till stor del erkänts som grundläggande för graf databas frågespråk. Detta faktum har motiverat flera författare att föreslå RDF frågespråk med navigeringsförmåga. I synnerhet har vi i ett tidigare dokument argumenterat för att inbäddade reguljära uttryck är lämpliga för att navigera RDF-data, och vi har föreslagit nSPARQL frågespråk för RDF, som använder inbäddade reguljära uttryck som byggstenar. I detta dokument studerar vi några av NSPARQL:s grundläggande egenskaper när det gäller uttrycklighet och komplexitet i utvärderingen. När det gäller uttrycksfullhet, visar vi att nSPARQL är tillräckligt uttrycksfullt för att svara på frågor med tanke på semantiken i RDFS ordförråd genom att direkt traversera inmatningskurvan. Vi visar också att häckning är nödvändigt för att uppnå detta sista resultat, och vi studerar expressiviteten i kombinationen av nästlade reguljära uttryck och SPARQL operatörer. När det gäller utvärderingens komplexitet, visar vi att utvärderingen av ett inhägnat reguljärt uttryck E över en RDF-graf G kan beräknas i tid O(-) (-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
NSPARQL språk REF utökar SPARQL med inbäddade reguljära uttryck och visar att dessa tillåter frågesvar som omfattar semantiken i RDFS ordförråd genom direkt graf traversal, utan att materialisera stängningen av grafen.
nSPARQL: A navigational language for RDF
{'venue': 'J. WEB SEM', 'journal': None, 'mag_field_of_study': ['Computer Science']}