Schema Mappings for Data Graphs
Summary: Defines schema mappings for data graphs (property graphs carrying attribute data) and shows that even simple recursive navigation combined with data predicates makes answering mixed navigation–data queries undecidable. Proves decidability (but intractability) when recursive target navigation is disallowed, proposes using unmarked nulls to recover tractability for regular-path-like queries, and shows richer patterns trigger undecidability again. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Nadime Francis
- 2. Leonid Libkin
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,038 | Transforming Property Graphs | 2024 | VLDB | 4.3997447e-05 |
| 10,235 | Repairing Property Graphs under PG-Constraints | 2026 | VLDB | 4.1905499e-05 |
| 10,849 | Versatile Property Graph Transformations | 2025 | VLDB | 4.1905499e-05 |
| 11,484 | Structural Generalizability: The Case of Similarity Search | 2021 | SIGMOD | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 47 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069691761 |
| 364 | A Graphical Query Language Supporting Recursion | 1987 | SIGMOD | 0.00025657601 |
| 483 | Clio Grows Up: From Research Prototype to Industrial Tool | 2005 | SIGMOD | 0.00022101908 |
| 3,835 | ++Spicy: an Open-Source Tool for Second-Generation Schema Mapping and Data Exchange | 2011 | VLDB | 6.7129526e-05 |
| 5,863 | Making SQL Queries Correct on Incomplete Databases: A Feasibility Study | 2016 | PODS | 5.2949117e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,750 | Normalization and Optimization of Schema Mappings | 2009 | VLDB | 5.9424107e-05 |
| 9,676 | Schema-Based Query Optimisation for Graph Databases | 2025 | SIGMOD | 4.3006524e-05 |
| 3,872 | Designing and Refining Schema Mappings via Data Examples | 2011 | SIGMOD | 6.6737583e-05 |
| 12,090 | Getting Unique Solution in Data Exchange | 2013 | VLDB | 4.1905499e-05 |
| 3,922 | On the Complexity of Deriving Schema Mappings from Database Instances | 2008 | PODS | 6.6238781e-05 |
| 5,727 | Query Processing under GLAV Mappings for Relational and Graph Databases | 2013 | VLDB | 5.3501787e-05 |
| 4,468 | Data Exchange and Schema Mappings in Open and Closed Worlds | 2008 | PODS | 6.1543925e-05 |
| 3,507 | Data Exchange and Incomplete Information | 2006 | PODS | 7.0299158e-05 |
| 4,980 | Towards a Theory of Schema-Mapping Optimization | 2008 | PODS | 5.7825422e-05 |
| 1,040 | Querying Graph Databases | 2013 | PODS | 0.00014483577 |