Vertical Partitioning for Database Design: A Graphical Algorithm

Summary: Proposes a graphical vertical-partitioning algorithm that starts from an attribute-affinity complete graph and uses a linearly connected spanning tree to generate fragments, treating cycles as units. Claims efficiency and a cleaner alternative without arbitrary objective functions, improving prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h00af0e8f4d58e3de
Venue: SIGMOD
Year: 1989
Pagerank: 7.9702688e-05
Overall Rank: 2,823 | 81.03%
DOI: 10.1145/67544.66966

Incoming Non-self Citations Over Time

Authors

1. Shamkant B. Navathe (University of Florida)
2. Minyoung Ra (University of Florida)

BibTeX Citation

@inproceedings{navathe_sigmod89,
        title = {{Vertical Partitioning for Database Design: A Graphical Algorithm}},
        author = {Navathe, Shamkant B. and Ra, Minyoung},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66966},
        url = {https://dl.acm.org/doi/10.1145/67544.66966},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
195	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025628849
1,200	Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads	2016	SIGMOD	0.00011563303
1,969	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.2935435e-05
2,704	Supporting Table Partitioning By Reference in Oracle	2008	SIGMOD	8.1149334e-05
7,199	A Comparison of Knives for Bread Slicing	2013	VLDB	5.5883682e-05
8,495	Provenance-based Data Skipping	2022	VLDB	5.3304338e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,199	A Comparison of Knives for Bread Slicing	2013	VLDB
2	3,143	Query Optimization Techniques for Partitioned Tables	2011	SIGMOD
3	3,239	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
4	2,111	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD
5	376	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB
6	12,674	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB
7	2,811	Horizontal Data Partitioning In Database Design	1982	SIGMOD
8	7,603	Partitioning A Relational Database Horizontally Using A Knowledge-Based Approach	1985	SIGMOD
9	1,013	A Heuristic Approach to Attribute Partitioning	1979	SIGMOD
10	195	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD