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
5260
Venue
SIGMOD
Year
2016
Pagerank
7.0554625e-05
Overall Rank
3,478 | 75.83%
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,517 Dependencies for Graphs 2017 PODS 8.6058545e-05
3,439 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 7.0916563e-05
4,486 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 6.1413967e-05
5,911 Normalizing Property Graphs 2023 VLDB 5.2718035e-05
6,691 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9573939e-05
7,120 Discovering Graph Functional Dependencies 2018 SIGMOD 4.8200122e-05
7,179 A Hierarchical Contraction Scheme for Querying Big Graphs 2022 SIGMOD 4.803776e-05
7,187 Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs) 2019 VLDB 4.8020046e-05
7,283 Discovering Association Rules from Big Graphs 2022 VLDB 4.7716465e-05
7,566 Extending Graph Patterns with Conditions 2020 SIGMOD 4.7047078e-05
8,145 Capturing Associations in Graphs 2020 VLDB 4.5724134e-05
8,282 Knowledge Graph Exploration Systems: are we lost? 2022 CIDR 4.5392079e-05
8,363 Deducing Certain Fixes to Graphs 2019 VLDB 4.5311185e-05
8,405 Ontology-based Entity Matching in Attributed Graphs 2019 VLDB 4.516252e-05
9,406 Explaining GNN-based Recommendations in Logic 2025 VLDB 4.3399748e-05
9,489 Making It Tractable to Catch Duplicates and Conflicts in Graphs 2023 SIGMOD 4.3300131e-05
9,847 Discovering Top-k Relevant and Diversified Rules 2024 SIGMOD 4.2680295e-05
10,163 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 4.1905499e-05
10,250 Structural Normalization of Property Graphs 2026 VLDB 4.1905499e-05
10,406 User-Centric Property Graph Repairs 2025 SIGMOD 4.1905499e-05
10,496 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.1905499e-05
10,849 Versatile Property Graph Transformations 2025 VLDB 4.1905499e-05
11,004 Capturing More Associations by Referencing External Graphs 2024 VLDB 4.1905499e-05
11,013 Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates 2024 VLDB 4.1905499e-05
11,019 Extending Graph Rules with Oracles 2024 VLDB 4.1905499e-05
11,211 Enriching Recommendation Models with Logic Conditions 2023 SIGMOD 4.1905499e-05
11,371 PGE: Robust Product Graph Embedding Learning for Error Detection 2022 VLDB 4.1905499e-05
11,459 Temporal Dependencies for Graphs 2021 SIGMOD 4.1905499e-05
11,464 GRIP: Constraint-based Explanation of Missing Answers for Graph Queries 2021 SIGMOD 4.1905499e-05
11,484 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.1905499e-05
11,494 Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency 2021 SIGMOD 4.1905499e-05
11,533 GEDet: Detecting Erroneous Nodes with A Few Examples 2021 VLDB 4.1905499e-05
11,664 Answering Why-questions by Exemplars in Attributed Graphs 2019 SIGMOD 4.1905499e-05
11,711 Catching Numeric Inconsistencies in Graphs 2018 SIGMOD 4.1905499e-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
289 Declarative Information Extraction Using Datalog with Embedded Extraction Predicates 2007 VLDB 0.00028865317
587 Scalable SPARQL Querying of Large RDF Graphs 2011 VLDB 0.00019623493
648 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018688754
1,487 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00011691164
1,820 A Normal Form for XML Documents 2002 PODS 0.00010410152
2,172 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 9.37776e-05
2,714 Minimal MapReduce Algorithms 2013 SIGMOD 8.2426646e-05
2,728 Keys for Graphs 2015 VLDB 8.2228869e-05
3,000 BigDansing: A System for Big Data Cleansing 2015 SIGMOD 7.7447724e-05
3,188 Scalable Big Graph Processing in MapReduce 2014 SIGMOD 7.4142307e-05
6,119 Distributed Graph Simulation: Impossibility and Possibility 2014 VLDB 5.1991813e-05
6,323 DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication 2015 VLDB 5.1072687e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,566 Extending Graph Patterns with Conditions 2020 SIGMOD 4.7047078e-05
8,145 Capturing Associations in Graphs 2020 VLDB 4.5724134e-05
7,361 Discovery Algorithms for Embedded Functional Dependencies 2020 SIGMOD 4.7469673e-05
6,385 Propagating Functional Dependencies with Conditions 2008 VLDB 5.0826969e-05
1,187 On Generating Near-Optimal Tableaux for Conditional Functional Dependencies 2008 VLDB 0.00013432048
11,711 Catching Numeric Inconsistencies in Graphs 2018 SIGMOD 4.1905499e-05
10,595 Efficient Discovery of Relaxed Functional Dependencies 2025 VLDB 4.1905499e-05
2,517 Dependencies for Graphs 2017 PODS 8.6058545e-05
2,064 Functional and Inclusion Dependencies: A Graph Theoretic Approach 1984 PODS 9.6485054e-05
7,120 Discovering Graph Functional Dependencies 2018 SIGMOD 4.8200122e-05