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: 2524
Venue: SIGMOD
Year: 1989
Pagerank: 8.1135051e-05
Overall Rank: 2,797 | 80.82%
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
199	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025612088
1,199	Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads	2016	SIGMOD	0.00011703966
1,913	Information-Theoretic Tools for Mining Database Structure from Large Data Sets	2004	SIGMOD	9.4928569e-05
2,666	Supporting Table Partitioning By Reference in Oracle	2008	SIGMOD	8.2764713e-05
7,059	A Comparison of Knives for Bread Slicing	2013	VLDB	5.7146962e-05
8,889	Provenance-based Data Skipping	2022	VLDB	5.3512428e-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,059	A Comparison of Knives for Bread Slicing	2013	VLDB
2	3,199	Query Optimization Techniques for Partitioned Tables	2011	SIGMOD
3	3,200	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
4	2,082	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD
5	366	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB
6	2,855	Horizontal Data Partitioning In Database Design	1982	SIGMOD
7	12,383	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB
8	7,464	Partitioning A Relational Database Horizontally Using A Knowledge-Based Approach	1985	SIGMOD
9	996	A Heuristic Approach to Attribute Partitioning	1979	SIGMOD
10	199	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD