Path discovery by Querying the federation of Relational Database and RDF Graph

Xiaowang Zhang, Jiahui Zhang, Muhammad Qasim Yasin, Wenrui Wu, Zhiyong FengarXiv 2016 · OpenReview

Abstract

Path discovery queries are essential for extracting implicit binary relations between nodes in a graph. While standard RDF querying languages like SPARQL 1.1 utilize property paths based on regular expressions, they often lack the expressivity needed for complex conjunctions or integration with external relational data. This paper introduces a federated path querying language that extends regular path queries to support the integration of RDF graphs with relational databases. We demonstrate that this language is strictly more expressive than nested regular expressions and negation-free property paths while maintaining low computational complexity, allowing for efficient evaluation over heterogeneous data sources.

The Challenge of Heterogeneous Data Silos

In contemporary data architectures, information is frequently fragmented across different storage paradigms. For instance, geographical and topological data are often best represented in RDF graphs, while transactional data, such as user profiles or order histories, typically resides in relational databases (SQL).

Bridging these silos for "path discovery"—the process of finding a sequence of connections between two entities—is a significant technical challenge. Existing tools struggle to find paths that satisfy multiple simultaneous conditions (conjunctions) or paths that require jumping between a graph and a relational table. For example, a query might need to find a route from a passenger's location to a destination by checking a taxi's status in a SQL database and then navigating a map stored in an RDF graph.

A Hierarchy of Federated Path Querying

To address these limitations, the authors propose a hierarchy of increasingly powerful query languages, building upon standard Regular Path Queries (RPQ):

  1. CNRPQ (Conjunctive Nested Regular Path Queries): This extension introduces the conjunction operator ($\wedge$), allowing users to define paths that must satisfy multiple nested conditions simultaneously.
  2. FCNRPQ (Federated CNRPQ): This serves as the bridge between paradigms, allowing a single query to include literals from a relational database alongside graph patterns.
  3. UFCNRPQ (Union of FCNRPQ): The most expressive variant in the hierarchy, adding the union operator ($\vee$) to the federated mix.
The hierarchy of expressivity for various extensions of Regular Path Queries (RPQ), showing the relationships between nested (N), conjunctive ($\wedge$), relational (R), and union (V) operators.

Despite the increased expressivity, the authors rigorously prove that the "data complexity" (the time required to execute a query as the database size grows) remains in polynomial time. This ensures that the framework is not just a theoretical advancement but a practical tool for large-scale data integration.

Experimental Evaluation

The framework was evaluated using a hybrid dataset designed to simulate real-world federated scenarios:

  • Relational Component: A synthetic "Orders" database containing up to 6.4 million tuples, simulating taxi trip records (IDs, timestamps, driver details, and locations).
  • RDF Component: A real-world OpenStreetMap (OSM) dataset consisting of approximately 14,000 lines of map data, including points of interest (POIs) and coordinate data.
The schema of the RDF graph used in the evaluation, based on OpenStreetMap (OSM) data, illustrating the relationships between Ways, Nodes, and Tags.

Key Results and Insights

  • Expressivity vs. Complexity: The research demonstrates that adding conjunction and federation operators makes the language strictly more powerful than standard SPARQL property paths without pushing the problem into uncomputable territory.
  • Scalability: Experiments showed that the system scales gracefully. Even with 6.4 million rows in the relational database, complex federated queries joining map paths with trip orders were completed in under 35 seconds.
  • Efficiency of the Join: The overhead associated with joining graph results with relational data remained a minimal fraction of the total execution time, validating the efficiency of the proposed federation approach.

Conclusion and Future Work

This paper provides a robust mathematical and practical foundation for querying across the RDF-Relational divide. While the current framework handles complex path discovery efficiently, future work remains in optimizing query managers for these federated scenarios and extending the language to support "path variables"—allowing the system to return the full path taken rather than just the endpoints. Additionally, the authors suggest that more sophisticated handling of RDF "blank nodes" could further enhance the language's expressivity.

Summary updated

Abstract

The class of queries for detecting path is an important as those can extract implicit binary relations over the nodes of input graphs. Most of the path querying languages used by the RDF community, like property paths in W3C SPARQL 1.1 and nested regular expressions in nSPARQL are based on the regular expressions. Federated queries allow for combining graph patterns and relational database that enables the evaluations over several heterogeneous data resources within a single query. Federated queries in W3C SPARQL 1.1 currently evaluated over different SPARQL endpoints. In this paper, we present a federated path querying language as an extension of regular path querying language for supporting RDF graph integration with relational database. The federated path querying language is absolutely more expressive than nested regular expressions and negation-free property paths. Its additional expressivity can be used for capturing the conjunction and federation of nested regular path queries. Despite the increase in expressivity, we also show that federated path queries are still enjoy a low computational complexity and can be evaluated efficiently.
BibTeX
@misc{zhang2016path,
  author = {Xiaowang Zhang and Jiahui Zhang and Muhammad Qasim Yasin and Wenrui Wu and Zhiyong Feng},
  title = {{Path discovery by Querying the federation of Relational Database and RDF Graph}},
  year = {2016},
  eprint = {1610.07707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.07707},
}
Figure