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: h7571b5d96d03f936
Venue: VLDB
Year: 2008
Pagerank: 5.68869e-05
Overall Rank: 6,761 | 54.55%
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,904	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	7.8801067e-05
4,998	Descriptive and Prescriptive Data Cleaning	2014	SIGMOD	6.3207886e-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
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011156154
2,647	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.1764914e-05
5,370	Computing Covers for Embedded Functional Dependencies	1987	PODS	6.1585627e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,950	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB
2	3,598	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD
3	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
4	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
5	590	On Propagation of Deletions and Annotations Through Views	2002	PODS
6	3,026	Functional Dependencies for Graphs	2016	SIGMOD
7	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	209	Dependency Inference	1987	VLDB
9	5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
10	1,088	Updates Of Relational Views	1983	PODS