On the efficiency of joining group patterns in SPARQL queries
MetadataShow full item record
This item's downloads: 402 (view details)
María-Esther Vidal, Edna Ruckhaus, Tomas Lampo, Amadís Marínez, Javier Sierra, Axel Polleres "On the efficiency of joining group patterns in SPARQL queries", Proceedings of the 7th Extended Semantic Web Conference (ESWC2010), 2010.
In SPARQL, conjunctive queries are expressed by using shared variables across sets of triple patterns, also called basic graph patterns. Based on this characterization, basic graph patterns in a SPARQL query can be partitioned into groups of acyclic patterns that share exactly one variable, or star-shaped groups. We observe that the number of triples in a group is proportional to the number of individuals that play the role of the subject or the object; however, depending on the degree of participation of the subject individuals in the properties, a group could be not much larger than a class or type to which the subject or object be- longs. Thus, it may be significantly more efficient to independently evaluate each of the groups, and then merge the resulting sets, than linearly joining all triples in a basic graph pattern. Based on this observation, we have developed query optimization and evaluation techniques on star-shaped groups. We have conducted an empirical analysis on the benefits of the optimization and evaluation techniques in several SPARQL query engines. We observe that our proposed techniques are able to speed up query evaluation time for join queries with star-shaped patterns by at least one order of magnitude.