Federated query optimization on linked data

SPARQL is the standard query language of the semantic Web and it is used to query linked data sources which are big semantic Web data sources. SPARQL can also be used to query "distributed" linked data sources by writing federated SPARQL queries in which case query or its sub queries are executed in separate sites and the results are combined and returned as the result of the query. In this thesis, we propose a new algorithm called "unique predicate source pruning" (UPSP) that reduces the federated SPARQL query execution time. The idea behind the algorithm is to find all relevant distributed linked data sources before executing federated SPARQL queries. This way the query is not sent to all data sources but only to the linked data sources that have data relevant to the query and therefore might return results. UPSP algorithm checks the sub query patterns in the query being processed first, looks for "star", "path", "hybrid", "sink" patterns. For each node UPSS algorithm checks appropriate unique predicate types which are subject-subject, subject-object, object-subject and object-object. If UPSP algorithm finds appropriate unique predicate type for query pattern it prunes all external sources. UPSP algorithm uses an index structure that is built offline before the algorithm executes. UPSP algorithm index structure is designed to be compatible with Hibiscus index that was proposed in the literature before. UPSP algorithm index has four more optional fields which are for each unique predicate types. We implemented UPSP algorithm on Hibiscus federated query engine which is an open source federated SPARQL query engine. UPSS algorithm executes just before Hibiscus pruning algorithm. We evaluated UPSP using FedBench benchmark. We compared the performance of the algorithm against standard Hibiscus source selection. The results show that algorithm improves source pruning up to 20% in some cases.