Article3118: Unterschied zwischen den Versionen
Yt2652 (Diskussion | Beiträge) |
Ne2260 (Diskussion | Beiträge) K (Textersetzung - „Forschungsgruppe=Wissensmanagement“ durch „Forschungsgruppe=Web Science und Wissensmanagement“) |
||
| Zeile 27: | Zeile 27: | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We consider the problem of source selection and query decomposition in federations of SPARQL endpoints, where query decompositions of a SPARQL query should reduce execution time and maximize answer completeness. This problem is in general intractable, and performance and answer completeness of SPARQL queries can be consider- ably affected when the number of SPARQL endpoints in a federation in- creases. We devise a formalization of this problem as the Vertex Coloring Problem and propose an approximate algorithm named Fed-DSATUR. We rely on existing results from graph theory to characterize the family of SPARQL queries for which Fed-DSATUR can produce optimal decompositions in polynomial time on the size of the query, i.e., on the number of SPARQL triple patterns in the query. Fed-DSATUR scales up much better to SPARQL queries with a large number of triple patterns, and may exhibit significant improvements in performance while answer completeness remains close to 100%. More importantly, we put our results in perspective, and provide evidence of SPARQL queries that are hard to decompose and constitute new challenges for data management. | |Abstract=We consider the problem of source selection and query decomposition in federations of SPARQL endpoints, where query decompositions of a SPARQL query should reduce execution time and maximize answer completeness. This problem is in general intractable, and performance and answer completeness of SPARQL queries can be consider- ably affected when the number of SPARQL endpoints in a federation in- creases. We devise a formalization of this problem as the Vertex Coloring Problem and propose an approximate algorithm named Fed-DSATUR. We rely on existing results from graph theory to characterize the family of SPARQL queries for which Fed-DSATUR can produce optimal decompositions in polynomial time on the size of the query, i.e., on the number of SPARQL triple patterns in the query. Fed-DSATUR scales up much better to SPARQL queries with a large number of triple patterns, and may exhibit significant improvements in performance while answer completeness remains close to 100%. More importantly, we put our results in perspective, and provide evidence of SPARQL queries that are hard to decompose and constitute new challenges for data management. | ||
| − | |Forschungsgruppe=Wissensmanagement | + | |Forschungsgruppe=Web Science und Wissensmanagement |
}} | }} | ||
Version vom 11. November 2015, 07:56 Uhr
On the Selection of SPARQL Endpoints to Efficiently Execute Federated SPARQL Queries
On the Selection of SPARQL Endpoints to Efficiently Execute Federated SPARQL Queries
Veröffentlicht: 2015
Journal: TLDKS (Large-scale Data and Knowledge-Centered Systems)
Referierte Veröffentlichung
Kurzfassung
We consider the problem of source selection and query decomposition in federations of SPARQL endpoints, where query decompositions of a SPARQL query should reduce execution time and maximize answer completeness. This problem is in general intractable, and performance and answer completeness of SPARQL queries can be consider- ably affected when the number of SPARQL endpoints in a federation in- creases. We devise a formalization of this problem as the Vertex Coloring Problem and propose an approximate algorithm named Fed-DSATUR. We rely on existing results from graph theory to characterize the family of SPARQL queries for which Fed-DSATUR can produce optimal decompositions in polynomial time on the size of the query, i.e., on the number of SPARQL triple patterns in the query. Fed-DSATUR scales up much better to SPARQL queries with a large number of triple patterns, and may exhibit significant improvements in performance while answer completeness remains close to 100%. More importantly, we put our results in perspective, and provide evidence of SPARQL queries that are hard to decompose and constitute new challenges for data management.
Web Science und Wissensmanagement