Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation

Summary: Introduces independence-reducibility, a tractable modification of key dependencies, and uses it to build BCNF designs optimized for updates and query answering, with a polynomial-time test and minimal relation count. Unifies designs for constant-time-maintainable, independence-reducible, and separable BCNF schemes under a single polynomial-time construction. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2534
Venue: SIGMOD
Year: 1990
Pagerank: 5.093636e-05
Overall Rank: 13,120 | 9.99%
DOI: 10.1145/93597.93624

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Ke Wang (Chongqing University; University of Alberta)

BibTeX Citation

@inproceedings{wang_sigmod90,
        title = {{Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation}},
        author = {Wang, Ke},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.93624},
        url = {https://dl.acm.org/doi/10.1145/93597.93624},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
266	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022823892
742	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00014426824
3,551	Efficient Query Answering in the Representative Instance Approach	1985	PODS	7.3196924e-05
13,134	Can Constant-time Maintainability Be More Practical?	1989	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,155	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD
2	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
3	5,249	Computing Covers for Embedded Functional Dependencies	1987	PODS
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	9,864	Tractable Database Design through Bounded Treewidth	2006	PODS
7	6,153	Independent and Separable Database Schemes	1983	PODS
8	13,170	Logical Design of Relational Database Schemes	1987	PODS
9	8,298	A Characterization of Constant-time-maintainability for BCNF Database Schemes	1988	SIGMOD
10	8,297	Independence-reducible Database Schemes	1988	PODS