Computing Covers for Embedded Functional Dependencies

Summary: Computes covers for functional dependencies embedded in a sub-schema and presents Reduction By Resolution (RBR), an algorithm that simplifies solving embedded-FD cover problems. Although worst-case exponential, RBR is polynomial on many input classes and enables BCNF testing and decomposition. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 777
Venue: PODS
Year: 1987
Pagerank: 6.2996929e-05
Overall Rank: 5,249 | 63.99%
DOI: 10.1145/28659.28665

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (Institute for Applied Mathematics, National Research Council)

BibTeX Citation

@inproceedings{gottlob_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{Computing Covers for Embedded Functional Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/28659.28665},
        doi = {10.1145/28659.28665},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,639	Propagating Functional Dependencies with Conditions	2008	VLDB	5.8165825e-05
6,798	Practical algorithms for finding prime attributes and testing normal forms	1989	PODS	5.7707336e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.00017513721
3,437	Reflections on Boyce-Codd Normal Form	1982	VLDB	7.4157489e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,259	Database Decomposition into Fourth Normal Form	1983	VLDB
2	3,222	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
3	13,120	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD
4	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
5	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
6	3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
7	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
8	13,170	Logical Design of Relational Database Schemes	1987	PODS
9	203	Dependency Inference	1987	VLDB
10	8,297	Independence-reducible Database Schemes	1988	PODS