A genetic algorithm for vertical fragmentation and access path selection

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.