On the Efficiency of Joining Group Patterns in SPARQL Queries. Marı́a-Esther Vidal, Ruckhaus, E., Lampo, T., Amadı́s Marı́nez, Sierra, J., & Polleres, A. In Proceedings of the 7th European Semantic Web Conference (ESWC2010), Heraklion, Greece, May, 2010. Springer. ![On the Efficiency of Joining Group Patterns in SPARQL Queries [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex In SPARQL queries, the combination of triple patterns is expressed by using shared variables across patterns. Based on this characterization, basic graph patterns in a SPARQL query can be partitioned into groups of acyclic pattern combinations 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 belongs. 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 these properties of star-shaped groups, we have developed query optimization and evaluation techniques. 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.
@inproceedings{vida-etal-2010,
Abstract = {In SPARQL queries, the combination of triple patterns is expressed by using shared variables across patterns. Based on this characterization, basic graph patterns in a SPARQL query can be partitioned into groups of acyclic pattern combinations 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 belongs. 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 these properties of star-shaped groups, we have developed query optimization and evaluation techniques. 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.},
Address = {Heraklion, Greece},
Author = {Mar{\'\i}a-Esther Vidal and Edna Ruckhaus and Tomas Lampo and Amad{\'\i}s Mar{\'\i}nez and Javier Sierra and Axel Polleres},
Booktitle = {Proceedings of the 7th European Semantic Web Conference (ESWC2010)},
Day = {30--3},
Month = MAY,
Projects = {lion2},
Publisher = {Springer},
Title = {On the Efficiency of Joining Group Patterns in {SPARQL} Queries},
Type = CONF,
Url = {http://www.polleres.net/publications/vida-etal-2010eswc.pdf},
Year = 2010,
Bdsk-Url-1 = {http://www.polleres.net/publications/vida-etal-2010eswc.pdf}}
Downloads: 0
{"_id":"2wXy2fsBx67HMMmiA","bibbaseid":"maraesthervidal-ruckhaus-lampo-amadsmarnez-sierra-polleres-ontheefficiencyofjoininggrouppatternsinsparqlqueries-2010","author_short":["Marı́a-Esther Vidal","Ruckhaus, E.","Lampo, T.","Amadı́s Marı́nez","Sierra, J.","Polleres, A."],"bibdata":{"bibtype":"inproceedings","type":"Conference paper","abstract":"In SPARQL queries, the combination of triple patterns is expressed by using shared variables across patterns. Based on this characterization, basic graph patterns in a SPARQL query can be partitioned into groups of acyclic pattern combinations 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 belongs. 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 these properties of star-shaped groups, we have developed query optimization and evaluation techniques. 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.","address":"Heraklion, Greece","author":[{"firstnames":[],"propositions":[],"lastnames":["Marı́a-Esther Vidal"],"suffixes":[]},{"firstnames":["Edna"],"propositions":[],"lastnames":["Ruckhaus"],"suffixes":[]},{"firstnames":["Tomas"],"propositions":[],"lastnames":["Lampo"],"suffixes":[]},{"firstnames":[],"propositions":[],"lastnames":["Amadı́s Marı́nez"],"suffixes":[]},{"firstnames":["Javier"],"propositions":[],"lastnames":["Sierra"],"suffixes":[]},{"firstnames":["Axel"],"propositions":[],"lastnames":["Polleres"],"suffixes":[]}],"booktitle":"Proceedings of the 7th European Semantic Web Conference (ESWC2010)","day":"30–3","month":"May","projects":"lion2","publisher":"Springer","title":"On the Efficiency of Joining Group Patterns in SPARQL Queries","url":"http://www.polleres.net/publications/vida-etal-2010eswc.pdf","year":"2010","bdsk-url-1":"http://www.polleres.net/publications/vida-etal-2010eswc.pdf","bibtex":"@inproceedings{vida-etal-2010,\n\tAbstract = {In SPARQL queries, the combination of triple patterns is expressed by using shared variables across patterns. Based on this characterization, basic graph patterns in a SPARQL query can be partitioned into groups of acyclic pattern combinations 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 belongs. 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 these properties of star-shaped groups, we have developed query optimization and evaluation techniques. 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.},\n\tAddress = {Heraklion, Greece},\n\tAuthor = {Mar{\\'\\i}a-Esther Vidal and Edna Ruckhaus and Tomas Lampo and Amad{\\'\\i}s Mar{\\'\\i}nez and Javier Sierra and Axel Polleres},\n\tBooktitle = {Proceedings of the 7th European Semantic Web Conference (ESWC2010)},\n\tDay = {30--3},\n\tMonth = MAY,\n\tProjects = {lion2},\n\tPublisher = {Springer},\n\tTitle = {On the Efficiency of Joining Group Patterns in {SPARQL} Queries},\n\tType = CONF,\n\tUrl = {http://www.polleres.net/publications/vida-etal-2010eswc.pdf},\n\tYear = 2010,\n\tBdsk-Url-1 = {http://www.polleres.net/publications/vida-etal-2010eswc.pdf}}\n\n","author_short":["Marı́a-Esther Vidal","Ruckhaus, E.","Lampo, T.","Amadı́s Marı́nez","Sierra, J.","Polleres, A."],"key":"vida-etal-2010","id":"vida-etal-2010","bibbaseid":"maraesthervidal-ruckhaus-lampo-amadsmarnez-sierra-polleres-ontheefficiencyofjoininggrouppatternsinsparqlqueries-2010","role":"author","urls":{"Paper":"http://www.polleres.net/publications/vida-etal-2010eswc.pdf"},"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"www.polleres.net/mypublications.bib","dataSources":["gixxkiKt6rtWGoKSh","cBfwyqsLFQQMc4Fss"],"keywords":[],"search_terms":["efficiency","joining","group","patterns","sparql","queries","marı́a-esther vidal","ruckhaus","lampo","amadı́s marı́nez","sierra","polleres"],"title":"On the Efficiency of Joining Group Patterns in SPARQL Queries","year":2010}