IEEE国际数据工程会议(TCDE)关心数据在信息系统的设计、开发、管理和利用中的作用。国际数据工程大会(ICDE)的目标是通过以下方式促进数据和信息工程的研究和开发:(a)提供一个论坛,以介绍和讨论新的研究成果、概念和技术;(b)为从业工程师提供对不断发展的研究工具和了解和评估实践;(c)使研究界接触到数据工程实际应用中的问题;(d)鼓励交流数据工程技术和经验。 官网地址:


Graph database query languages feature expressive, yet computationally expensive pattern matching capabilities. Answering optional query clauses in SPARQL for instance renders the query evaluation problem immediately Pspace-complete. Therefore, light-weight graph pattern matching relations, such as simulation, have recently been investigated as promising alternatives to more expensive query mechanisms like, e.g., computing subgraph isomorphism. Still, graph pattern matching alone lacks expressive query capabilities: all patterns are combined by usual join constructs, where more sophisticated capabilities would be inevitable for making solutions useful to emerging applications. In this paper we bridge this gap by introducing a new dual simulation process operating on SPARQL queries. In addition to supporting the full syntactic structure of SPARQL queries, it features polynomial-time pattern matching to compute an overapproximation of query results from the database. Moreover, to achieve runtimes competing with state-of-the-art database systems, we develop a novel algorithmic solution to dual simulation graph pattern matching, based on a system of inequalities that allows for several optimization heuristics. Finally, we achieve soundness of our process for SPARQL queries including UNION, AND and OPTIONAL operators not restricted to well-designed patterns. Our experiments on synthetic and real-world graph data promise a clear gain for graph database systems when incorporating the new dual simulation techniques. In this supplement paper we present in detail all proofs, discussions of experimental results, and complexity analysis for the original paper "Fast Dual Simulation Processing of Graph Database Queries" included in the Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE 2019), Macau, China.