Showing results for

Back to all research
Lecture Notes in Computer Science Nov 4, 2019

Evaluating Generalized Path Queries by Integrating Algebraic Path Problem Solving with Graph Pattern Matching

Abhisha Bhattacharyya, Ilya Baldin, Yufeng Xin, Kemafor Anyanwu


Path querying on Semantic Networks is gaining increased focus because of its broad applicability. Some graph databases offer support for variants of path queries e.g. shortest path.

However, many applications have the need for the set version of various path problem i.e. finding paths between multiple source and multiple destination nodes (subject to different kinds of constraints). Further, the sets of source and destination nodes may be described declaratively as patterns, rather than given explicitly. Such queries lead to the requirement of integrating graph pattern matching with path problem solving. There are currently existing limitations in support of such queries (either inability to express some classes, incomplete results, inability to complete query evaluation unless graph patterns are extremely selective, etc).

In this paper, we propose a framework for evaluating generalized path queries - gpqs that integrate an algebraic technique for solving path problems with SPARQL graph pattern matching. The integrated algebraic querying technique enables more scalable and efficient processing of gpqs, including the possibility of support for a broader range of path constraints. We present the approach and implementation strategy and compare performance and query expressiveness with a popular graph engine.

Join the Stardog Community

Need help? Join our Community to find answers to your questions! You’ll find our Support team, engineers, and friendly Stardog users ready to help. While you’re there, share your feedback on our platform or latest release - we’re all ears.

Join the community