Dependencies for Graphs

Summary: GEDs: graph-pattern + attribute-dependency rules unifying graph-FDs with constant literals (to catch inconsistencies) and id-literals to represent keys. Develop a confluent chase, settle satisfiability/implication/validation decision complexity (±constants/ids), give a sound-and-complete finite-implication axiom system, and analyze extensions with built-ins/disjunction. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2248a61c123784c8
Venue: PODS
Year: 2017
Pagerank: 8.5665938e-05
Overall Rank: 2,364 | 84.11%
DOI: 10.1145/3034786.3056114

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Ping Lu (Beihang University)

BibTeX Citation

@inproceedings{fan_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Dependencies for Graphs}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056114},
        doi = {10.1145/3034786.3056114},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Lu, Ping},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,831	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9602632e-05
5,233	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2176841e-05
5,798	Normalizing Property Graphs	2023	VLDB	5.9905343e-05
7,226	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5810344e-05
7,243	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5768239e-05
7,342	Discovering Association Rules from Big Graphs	2022	VLDB	5.5480127e-05
7,478	Extending Graph Patterns with Conditions	2020	SIGMOD	5.5150923e-05
8,218	Towards Event Prediction in Temporal Graphs	2022	VLDB	5.3762638e-05
8,293	Capturing Associations in Graphs	2020	VLDB	5.3612871e-05
8,398	Deducing Certain Fixes to Graphs	2019	VLDB	5.3399392e-05
8,590	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.3071244e-05
9,291	Knowledge Translation	2020	VLDB	5.2003084e-05
9,732	Explaining GNN-based Recommendations in Logic	2025	VLDB	5.1349531e-05
9,806	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1257999e-05
11,106	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.9793485e-05
11,121	User-Centric Property Graph Repairs	2025	SIGMOD	4.9793485e-05
11,153	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD	4.9793485e-05
11,186	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9793485e-05
11,428	Versatile Property Graph Transformations	2025	VLDB	4.9793485e-05
11,550	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9793485e-05
11,563	Extending Graph Rules with Oracles	2024	VLDB	4.9793485e-05
11,961	Temporal Dependencies for Graphs	2021	SIGMOD	4.9793485e-05
12,210	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
1,575	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010194712
1,710	A Normal Form for XML Documents	2002	PODS	9.8199787e-05
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2910005e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
3,317	Keys for Graphs	2015	VLDB	7.436464e-05
4,233	The Interaction between Functional Dependencies and Template Dependencies	1980	SIGMOD	6.7136317e-05
7,185	Exploiting Equality Generating Dependencies in Checking Chase Termination	2016	VLDB	5.591248e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	209	Dependency Inference	1987	VLDB
2	8,982	Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability	2015	PODS
3	13,549	A Theory Of Data Dependencies Over Relational Expressions	1982	PODS
4	3,356	The Implication And Finite Implication Problems For Typed Template Dependencies	1982	PODS
5	1,291	Extending Dependencies with Conditions	2007	VLDB
6	9,704	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB
7	8,293	Capturing Associations in Graphs	2020	VLDB
8	7,243	Discovering Graph Functional Dependencies	2018	SIGMOD
9	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
10	3,026	Functional Dependencies for Graphs	2016	SIGMOD