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: h0fa516796d48fbcb
Venue: SIGMOD
Year: 2016
Pagerank: 7.7351194e-05
Overall Rank: 3,027 | 79.66%
DOI: 10.1145/2882903.2915232

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Yinghui Wu (Washington State University)
3. Jingbo Xu (Beihang University; University of Edinburgh)

BibTeX Citation

@inproceedings{fan_sigmod16,
        title = {{Functional Dependencies for Graphs}},
        author = {Fan, Wenfei and Wu, Yinghui and Xu, Jingbo},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915232},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915232},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9382307e-05
3,769	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.0282248e-05
5,800	Normalizing Property Graphs	2023	VLDB	5.9876984e-05
6,528	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7540798e-05
7,016	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6184227e-05
7,228	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5783924e-05
7,245	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5741839e-05
7,345	Discovering Association Rules from Big Graphs	2022	VLDB	5.5453863e-05
7,483	Extending Graph Patterns with Conditions	2020	SIGMOD	5.5124816e-05
8,299	Capturing Associations in Graphs	2020	VLDB	5.3587491e-05
8,403	Deducing Certain Fixes to Graphs	2019	VLDB	5.3374114e-05
8,597	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.3046172e-05
8,695	Knowledge Graph Exploration Systems: are we lost?	2022	CIDR	5.2880532e-05
9,737	Explaining GNN-based Recommendations in Logic	2025	VLDB	5.1325223e-05
9,813	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1233734e-05
9,973	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1014161e-05
10,189	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0628015e-05
10,651	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.9769913e-05
10,730	Structural Normalization of Property Graphs	2026	VLDB	4.9769913e-05
11,130	User-Centric Property Graph Repairs	2025	SIGMOD	4.9769913e-05
11,195	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9769913e-05
11,434	Versatile Property Graph Transformations	2025	VLDB	4.9769913e-05
11,556	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9769913e-05
11,564	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.9769913e-05
11,569	Extending Graph Rules with Oracles	2024	VLDB	4.9769913e-05
11,730	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9769913e-05
11,882	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	4.9769913e-05
11,967	Temporal Dependencies for Graphs	2021	SIGMOD	4.9769913e-05
11,972	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	4.9769913e-05
11,991	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	4.9769913e-05
12,036	GEDet: Detecting Erroneous Nodes with A Few Examples	2021	VLDB	4.9769913e-05
12,160	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.9769913e-05
12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9769913e-05

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
328	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00020921862
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018190518
512	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017053842
1,042	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012331317
1,572	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.0001019315
1,710	A Normal Form for XML Documents	2002	PODS	9.815332e-05
2,424	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.483813e-05
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2782871e-05
3,068	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6841028e-05
3,317	Keys for Graphs	2015	VLDB	7.432944e-05
5,955	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.9331392e-05
6,152	DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication	2015	VLDB	5.8673753e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,483	Extending Graph Patterns with Conditions	2020	SIGMOD
2	8,299	Capturing Associations in Graphs	2020	VLDB
3	7,289	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
4	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
5	6,766	Propagating Functional Dependencies with Conditions	2008	VLDB
6	12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD
7	11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	2,365	Dependencies for Graphs	2017	PODS
9	2,099	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
10	7,245	Discovering Graph Functional Dependencies	2018	SIGMOD