Propagating Functional Dependencies with Conditions

Summary: Characterizes conditional functional-dependency propagation through relational-algebra views, with tight complexity bounds from polynomial time to undecidable, including finite-domain effects. Gives the first minimal-cover algorithm for CFDs propagated by SPC views and validates its efficiency experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9874
Venue: VLDB
Year: 2008
Pagerank: 5.8165825e-05
Overall Rank: 6,639 | 54.46%
DOI: 10.14778/1453856.1453901

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (AT&T; Harbin Institute of Technologies; University of Edinburgh)
2. Shuai Ma (University of Edinburgh)
3. Yanli Hu (National University of Defense Technology; University of Edinburgh)
4. Jie Liu (Chinese Academy of Sciences)
5. Yinghui Wu (University of Edinburgh)

BibTeX Citation

@article{fan_vldb08,
        title = {{Propagating Functional Dependencies with Conditions}},
        author = {Fan, Wenfei and Ma, Shuai and Hu, Yanli and Liu, Jie and Wu, Yinghui},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {391--402},
        doi = {10.14778/1453856.1453901},
        url = {https://doi.org/10.14778/1453856.1453901},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,872	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	8.0104819e-05
4,890	Descriptive and Prescriptive Data Cleaning	2014	SIGMOD	6.4590072e-05

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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
1,277	Extending Dependencies with Conditions	2007	VLDB	0.00011368191
2,617	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.3391085e-05
5,249	Computing Covers for Embedded Functional Dependencies	1987	PODS	6.2996929e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,894	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB
2	3,527	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD
3	1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
4	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
5	620	On Propagation of Deletions and Annotations Through Views	2002	PODS
6	2,973	Functional Dependencies for Graphs	2016	SIGMOD
7	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	203	Dependency Inference	1987	VLDB
9	5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
10	1,075	Updates Of Relational Views	1983	PODS