Can Constant-time Maintainability Be More Practical?

Summary: Canonical algorithm for ctm schemas: maintenance via fetching a bounded number of tuples using only conjunctions of equalities (A='a') instead of arbitrary Boolean requests. Shows equality-conjunctions suffice whenever constant-time solutions exist, simplifying the model and boosting practical implementability; relates to FDs, JDs, BCNF and boundedness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 856
Venue: PODS
Year: 1989
Pagerank: 5.093636e-05
Overall Rank: 13,134 | 9.89%
DOI: 10.1145/73721.73733

Incoming Non-self Citations Over Time

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

Authors

1. KE WANG (Chongqing University)

BibTeX Citation

@inproceedings{wang_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Can Constant-time Maintainability Be More Practical?}},
        url = {https://dl.acm.org/doi/10.1145/73721.73733},
        doi = {10.1145/73721.73733},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {WANG, KE},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,120	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.5797982e-05
5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	6.2533477e-05
8,297	Independence-reducible Database Schemes	1988	PODS	5.4574671e-05
8,298	A Characterization of Constant-time-maintainability for BCNF Database Schemes	1988	SIGMOD	5.4574671e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,297	Independence-reducible Database Schemes	1988	PODS
2	13,120	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD
3	10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD
4	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
5	10,160	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
6	4,094	Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints	1987	PODS
7	9,845	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
8	13,171	On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies	1987	PODS
9	5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS
10	8,298	A Characterization of Constant-time-maintainability for BCNF Database Schemes	1988	SIGMOD