Well-Designed Query Optimization Based on Pattern Tree

OPTIONAL, one of the most distinctive features of SPARQL, allows partial answers when complete answers are not available due to lack of information. Optional matching is computationally expensive and the query answering is PSPACE-complete. In this paper, we focus on well-designed queries. On the one hand, well-designed queries account for more than 70% of all queries in real queries. Well-designed queries, on the other hand, achieve much better computational properties since restricting optional matching in query answering makes the problem coNP-complete. The pattern tree represents the OPT nested hierarchical relationships between well-designed query patterns in a tree structure. We optimize well-designed queries based on the pattern tree. In our methods, we propose characteristic sets(CSs) merge-based algorithms to optimize queries within pattern tree nodes. We merge CSs based on predicate correlation while reducing null values in the data table. In addition, we propose to pass parent-to-child constraints on pattern trees to filter invalid data and reduce intermediate results to optimize inter-node queries. The extensive experiments on synthetic and real-world datasets show that our method outperforms the S2RDF and Prost by order of magnitude.