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: h11a4973ddf788970
Venue: PODS
Year: 1987
Pagerank: 6.1585627e-05
Overall Rank: 5,370 | 63.90%
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,761	Propagating Functional Dependencies with Conditions	2008	VLDB	5.68869e-05
6,931	Practical algorithms for finding prime attributes and testing normal forms	1989	PODS	5.6412543e-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
506	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.00017142422
3,476	Reflections on Boyce-Codd Normal Form	1982	VLDB	7.2707399e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,349	Database Decomposition into Fourth Normal Form	1983	VLDB
2	3,287	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
3	9,512	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
4	13,410	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD
5	6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS
6	3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
7	6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
8	13,460	Logical Design of Relational Database Schemes	1987	PODS
9	209	Dependency Inference	1987	VLDB
10	8,465	Independence-reducible Database Schemes	1988	PODS