Vertical fragmentation and access path selection are interdependent techniq
ues in physical database design used to enhance performance in database sys
tems. While vertical fragmentation in relational databases deals with assig
nment of attributes to physical files, access path selection deals with sea
rching efficiently the physical location of data records. Vertical fragment
ation is a combinatorial optimization problem that is NP-hard in most cases
, We propose a genetic algorithm approach for the vertical fragmentation pr
oblem while addressing access path selection. The effectiveness and efficie
ncy of the genetic algorithm are illustrated through several database desig
n problems, ranging from 10 attributes/5 transactions to 30 attributes/18 t
ransactions. In most cases, our design solutions match the global optimum s
olutions obtained from an exhaustive enumeration. Compared to unpartitioned
databases, our design solution results in substantial savings (up to 80%)
in the number of disk accesses.