Query containment is one of the building block of query optimization techniques. In the relational world, query containment is a wellstudied problem. At the same time it is well-understood that relational queries are not enough to cope with graph-structured data, where one is interested in expressing queries that capture navigation in the graph. This paper contributes a study on the problem of query containment for an expressive class of navigational queries called Extended Property Paths (EPPs). EPPs are more expressive than previous navigational extension of SPARQL (e.g., nested regular expressions) as they allow to express path conjunction and path negation, among others. We attack the problem of EPPs containment and provide complexity bounds.
Containment of expressive SPARQL navigational queries / Chekol, Melisachew Wudage; Pirrò, Giuseppe. - (2016), pp. 86-101. (Intervento presentato al convegno 5th International Semantic Web Conference tenutosi a Kobe) [10.1007/978-3-319-46523-4_6].
Containment of expressive SPARQL navigational queries
Pirrò, Giuseppe
2016
Abstract
Query containment is one of the building block of query optimization techniques. In the relational world, query containment is a wellstudied problem. At the same time it is well-understood that relational queries are not enough to cope with graph-structured data, where one is interested in expressing queries that capture navigation in the graph. This paper contributes a study on the problem of query containment for an expressive class of navigational queries called Extended Property Paths (EPPs). EPPs are more expressive than previous navigational extension of SPARQL (e.g., nested regular expressions) as they allow to express path conjunction and path negation, among others. We attack the problem of EPPs containment and provide complexity bounds.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
