Manzi Wang
ABSTRACT
In the current trend of rapid development of big data, there are frequent application scenarios of high concurrent query processing on RDF data sets. The multi-query optimization scheme for solving concurrent queries needs to provide a global approximate optimal solution for the query set composed of a set of queries, so as to minimize the overall time cost of the query set. Under the premise of accelerating statistics by RDF storage index and narrowing the scope of semantic pruning, firstly, simplified multiple queries are converted into connection graphs, and then all queries are clustered and grouped. In each group, all common subgraphs of connection graphs are iteratively searched and mapping tables are established. Then, the common subgraph is arranged in descending order by the number of vertices to construct the query rewriting scheme. Finally, for all the rewritten queries, the dynamic programming algorithm based on selection rate estimation is used for secondary optimization. On the one hand, the common subgraph is used to rewrite the query to reduce the number of queries, so as to reduce the cost through the reusable common result set. On the other hand, because of the establishment of RDF storage index, the selection rate can be estimated quickly, and the rewritten queries can be optimized again to improve the overall query efficiency. The experimental results show that the proposed algorithm has better query performance than the existing query schemes, especially when the RDF dataset is large, the number of queries in the query set is large, and the query statements are complex, the multi-query optimization method in this paper works better.
- Berners-Lee T, Hendler J, Lassila O (2001). The semantic web. Scientific american, 284(5), 28--37.Google Scholar
- Ahmetaj S, Fischl W, Kroll M, et al (2016). The Challenge of Optional Matching in SPARQL[C]// Intemational Symposium on Foundations of Information and Knowledge Systems. Springer International Publishing, 169--190.Google Scholar
- Schatzle A, Przyjaciel-Zablocki M,Neu A.et al (2014). Sempala: interactive SPARQL query processing on Hadoop[C]// Intemational Semantic Web Conference. Springer International Publishing, 164--179.Google Scholar
- Abadi DJ, Marcus A, Madden SR, Hollenbach K (2007). Scalable semantic Web data management using vertical partitioning. In: Koch C,ed. Proc. of the 33rd Int'l Conf. on Very Large Data Bases (VLDB 2007), Austria: ACM Press, 411--422.Google ScholarDigital Library
- Weiss C, Karras P, Bernstein A. Hexastore (2008): Sextuple indexing for semantic Web data management. Proc. of the VLDB Endowments, 1(1), 1008--1019.Google ScholarDigital Library
- Papailiou N, Tsoumakos D, Karras P, et al (2015). Graph-aware,workload-adaptive sparql query caching[C]// Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 1777--1792.Google Scholar
- Anyanwu K (2013). A vision for SPARQL multi-query optimization on MapReduce //Data Engineering Workshops(ICDEW), 2013 IEEE 29th International Conference on IEEE, 25--26.Google Scholar
- W. Le, A. Kementsietsidis, S. Duan et al. "Scalable multi-query optimization for sparql" in ICDE, 2012, pp. 666--677.Google Scholar
- Li Yan (2016). Research on sub-row query algorithm based on single neighborhood [D]. Qinhuangdao City: Yanshan University.Google Scholar
- X. Ren and J. Wang (2015). Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. PVLDB, 8(5), 617--628.Google ScholarDigital Library
- Zhang Chunying, Zhang Xue (2013). Subgraph Isomorphism of Uncertain Attribute Graphs and Its Decision Algorithm[J]. Computer Science, 40(6), 242--246.Google Scholar
- Kalayci T E, Birant D (2015). An ant colony optimization approach for optimizing SPARQL queries by reordering triple patterns[J]. Information Systems, 50, 51--68.Google ScholarDigital Library
Index Terms
- RDF Multi-query Optimization Algorithm for Query Rewriting Using Common Subgraphs
Recommendations
Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting
CASCON '03: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative researchUser queries have been becoming increasingly complex (e.g., involving a large number of joins) as database technology is applied to some application domains such as data warehouses and life sciences. Query optimizers in existing database management ...
An Algorithm for Query Rewriting with Refined Criteria for Query Materialization in Deep Web
WISA '13: Proceedings of the 2013 10th Web Information System and Application ConferenceIn deep web, the properties and constraint on different interfaces are various. The heterogeneity and autonomy make the query between interfaces can not be translated equally. Zhang et al. build up the query translation on three level: property, ...
Query Rewriting and Optimization for Ontological Databases
Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints that derive new intensional knowledge from the extensional database), rather than ...
Comments