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):
- 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.
- FCNRPQ (Federated CNRPQ): This serves as the bridge between paradigms, allowing a single query to include literals from a relational database alongside graph patterns.
- UFCNRPQ (Union of FCNRPQ): The most expressive variant in the hierarchy, adding the union operator ($\vee$) to the federated mix.
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.
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