Database Paper Browser

Back to papers

Functional Dependencies for Graphs

Summary: Proposes GFDs, a class of graph functional dependencies unifying attribute-value and topological constraints, subsuming CFDs. Complexity: coNP/NP-complete; the approach provides parallel scalable algorithms for violation detection on large graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5259
Venue
SIGMOD
Year
2016
Pagerank
8.7882979e-05
Overall Rank
2,450 | 82.96%
DOI
10.1145/2882903.2915232

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
2,527 Dependencies for Graphs 2017 PODS 8.5954406e-05
3,394 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 7.1480446e-05
4,494 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 6.1414196e-05
5,910 Normalizing Property Graphs 2023 VLDB 5.2768691e-05
6,690 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9621556e-05
6,703 Discovering Graph Functional Dependencies 2018 SIGMOD 4.9555163e-05
6,730 A Hierarchical Contraction Scheme for Querying Big Graphs 2022 SIGMOD 4.9479867e-05
7,185 Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs) 2019 VLDB 4.8066159e-05
7,287 Discovering Association Rules from Big Graphs 2022 VLDB 4.7762276e-05
7,641 Extending Graph Patterns with Conditions 2020 SIGMOD 4.6902655e-05
8,211 Capturing Associations in Graphs 2020 VLDB 4.5581054e-05
8,289 Knowledge Graph Exploration Systems: are we lost? 2022 CIDR 4.5435639e-05
8,409 Ontology-based Entity Matching in Attributed Graphs 2019 VLDB 4.5205877e-05
8,422 Deducing Certain Fixes to Graphs 2019 VLDB 4.5167705e-05
9,400 Explaining GNN-based Recommendations in Logic 2025 VLDB 4.3441378e-05
9,487 Making It Tractable to Catch Duplicates and Conflicts in Graphs 2023 SIGMOD 4.3341665e-05
9,564 Catching Numeric Inconsistencies in Graphs 2018 SIGMOD 4.3254416e-05
9,847 Discovering Top-k Relevant and Diversified Rules 2024 SIGMOD 4.2721228e-05
10,163 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 4.1945683e-05
10,250 Structural Normalization of Property Graphs 2026 VLDB 4.1945683e-05
10,395 User-Centric Property Graph Repairs 2025 SIGMOD 4.1945683e-05
10,486 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.1945683e-05
10,845 Versatile Property Graph Transformations 2025 VLDB 4.1945683e-05
11,001 Capturing More Associations by Referencing External Graphs 2024 VLDB 4.1945683e-05
11,010 Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates 2024 VLDB 4.1945683e-05
11,016 Extending Graph Rules with Oracles 2024 VLDB 4.1945683e-05
11,209 Enriching Recommendation Models with Logic Conditions 2023 SIGMOD 4.1945683e-05
11,369 PGE: Robust Product Graph Embedding Learning for Error Detection 2022 VLDB 4.1945683e-05
11,456 Temporal Dependencies for Graphs 2021 SIGMOD 4.1945683e-05
11,461 GRIP: Constraint-based Explanation of Missing Answers for Graph Queries 2021 SIGMOD 4.1945683e-05
11,480 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.1945683e-05
11,490 Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency 2021 SIGMOD 4.1945683e-05
11,529 GEDet: Detecting Erroneous Nodes with A Few Examples 2021 VLDB 4.1945683e-05
11,659 Answering Why-questions by Exemplars in Attributed Graphs 2019 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
287 Declarative Information Extraction Using Datalog with Embedded Extraction Predicates 2007 VLDB 0.00028971272
582 Scalable SPARQL Querying of Large RDF Graphs 2011 VLDB 0.00019723083
651 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018648572
1,500 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00011674394
1,803 A Normal Form for XML Documents 2002 PODS 0.00010504331
2,162 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 9.3964337e-05
2,674 Minimal MapReduce Algorithms 2013 SIGMOD 8.3328645e-05
2,946 BigDansing: A System for Big Data Cleansing 2015 SIGMOD 7.8372441e-05
3,129 Scalable Big Graph Processing in MapReduce 2014 SIGMOD 7.5008242e-05
3,694 Keys for Graphs 2015 VLDB 6.8345712e-05
6,127 DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication 2015 VLDB 5.1981241e-05
6,146 Distributed Graph Simulation: Impossibility and Possibility 2014 VLDB 5.1857597e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,641 Extending Graph Patterns with Conditions 2020 SIGMOD 4.6902655e-05
8,211 Capturing Associations in Graphs 2020 VLDB 4.5581054e-05
7,366 Discovery Algorithms for Embedded Functional Dependencies 2020 SIGMOD 4.7515248e-05
6,385 Propagating Functional Dependencies with Conditions 2008 VLDB 5.0875028e-05
1,188 On Generating Near-Optimal Tableaux for Conditional Functional Dependencies 2008 VLDB 0.00013441729
9,564 Catching Numeric Inconsistencies in Graphs 2018 SIGMOD 4.3254416e-05
10,587 Efficient Discovery of Relaxed Functional Dependencies 2025 VLDB 4.1945683e-05
2,527 Dependencies for Graphs 2017 PODS 8.5954406e-05
2,058 Functional and Inclusion Dependencies: A Graph Theoretic Approach 1984 PODS 9.6585264e-05
6,703 Discovering Graph Functional Dependencies 2018 SIGMOD 4.9555163e-05