Aiming at the problem that only some types of SPARQL （ simple protocal and resource description framework query language） queries can be answered by using the current resource description framework link traversal ba...Aiming at the problem that only some types of SPARQL （ simple protocal and resource description framework query language） queries can be answered by using the current resource description framework link traversal based query execution （RDF-LTE） approach, this paper discusses how the execution order of the triple pattern affects the query results and cost based on concrete SPARQL queries, and analyzes two properties of the web of linked data, missing backward links and missing contingency solution. Then three heuristic principles for logic query plan optimization, namely, the filtered basic graph pattern （FBGP） principle, the triple pattern chain principle and the seed URIs principle, are proposed. The three principles contribute to decrease the intermediate solutions and increase the types of queries that can be answered. The effectiveness and feasibility of the proposed approach is evaluated. The experimental results show that more query results can be returned with less cost, thus enabling users to develop the full potential of the web of linked data.展开更多
Efficient support for querying large-scale resource description framework （RDF） triples plays an important role in semantic web data management. This paper presents an efficient RDF query engine to evaluate SPARQL q...Efficient support for querying large-scale resource description framework （RDF） triples plays an important role in semantic web data management. This paper presents an efficient RDF query engine to evaluate SPARQL queries, where the inverted index structure is employed for indexing the RDF triples. A set of operators on the inverted index was developed for query optimization and evaluation. Then a main-tree-shaped optimization algorithm was developed that transforms a SPARQL query graph into the op-timal query plan by effectively reducing the search space to determine the optimal joining order. The opti-mization collects a set of RDF statistics for estimating the execution cost of the query plan. Finally the opti-mal query plan is evaluated using the defined operators for answering the given SPARQL query. Extensive tests were conducted on both synthetic and real datasets containing up to 100 million triples to evaluate this approach with the results showing that this approach can answer most queries within 1 s and is extremely efficient and scalable in comparison with previous best state-of-the-art RDF stores.展开更多
基金The National Natural Science Foundation of China(No.61070170)the Natural Science Foundation of Higher Education Institutions of Jiangsu Province(No.11KJB520017)Suzhou Application Foundation Research Project(No.SYG201238)
文摘Aiming at the problem that only some types of SPARQL （ simple protocal and resource description framework query language） queries can be answered by using the current resource description framework link traversal based query execution （RDF-LTE） approach, this paper discusses how the execution order of the triple pattern affects the query results and cost based on concrete SPARQL queries, and analyzes two properties of the web of linked data, missing backward links and missing contingency solution. Then three heuristic principles for logic query plan optimization, namely, the filtered basic graph pattern （FBGP） principle, the triple pattern chain principle and the seed URIs principle, are proposed. The three principles contribute to decrease the intermediate solutions and increase the types of queries that can be answered. The effectiveness and feasibility of the proposed approach is evaluated. The experimental results show that more query results can be returned with less cost, thus enabling users to develop the full potential of the web of linked data.
基金Supported by the Shanghai Jiao Tong University and IBM CRL Joint Project
文摘Efficient support for querying large-scale resource description framework （RDF） triples plays an important role in semantic web data management. This paper presents an efficient RDF query engine to evaluate SPARQL queries, where the inverted index structure is employed for indexing the RDF triples. A set of operators on the inverted index was developed for query optimization and evaluation. Then a main-tree-shaped optimization algorithm was developed that transforms a SPARQL query graph into the op-timal query plan by effectively reducing the search space to determine the optimal joining order. The opti-mization collects a set of RDF statistics for estimating the execution cost of the query plan. Finally the opti-mal query plan is evaluated using the defined operators for answering the given SPARQL query. Extensive tests were conducted on both synthetic and real datasets containing up to 100 million triples to evaluate this approach with the results showing that this approach can answer most queries within 1 s and is extremely efficient and scalable in comparison with previous best state-of-the-art RDF stores.
