English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Graph database query languages feature expressive, yet computationallyexpensive pattern matching capabilities. Answering optional query clauses inSPARQL for instance renders the query evaluation problem immediatelyPspace-complete. Therefore, light-weight graph pattern matching relations, suchas simulation, have recently been investigated as promising alternatives tomore expensive query mechanisms like, e.g., computing subgraph isomorphism.Still, graph pattern matching alone lacks expressive query capabilities: allpatterns are combined by usual join constructs, where more sophisticatedcapabilities would be inevitable for making solutions useful to emergingapplications. In this paper we bridge this gap by introducing a new dualsimulation process operating on SPARQL queries. In addition to supporting thefull syntactic structure of SPARQL queries, it features polynomial-time patternmatching 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 patternmatching, based on a system of inequalities that allows for severaloptimization heuristics. Finally, we achieve soundness of our process forSPARQL queries including UNION, AND and OPTIONAL operators not restricted towell-designed patterns. Our experiments on synthetic and real-world graph datapromise a clear gain for graph database systems when incorporating the new dualsimulation techniques. In this supplement paper we present in detail allproofs, discussions of experimental results, and complexity analysis for theoriginal paper "Fast Dual Simulation Processing of Graph Database Queries"included in the Proceedings of the 35th IEEE International Conference on DataEngineering (ICDE 2019), Macau, China.

Fast Dual Simulation Processing of Graph Database Queries (Supplement)