A genetic algorithm for vertical fragmentation and access path selection

Authors
Citation
Sk. Song et N. Gorla, A genetic algorithm for vertical fragmentation and access path selection, COMPUTER J, 43(1), 2000, pp. 81-93
Citations number
29
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTER JOURNAL
ISSN journal
00104620 → ACNP
Volume
43
Issue
1
Year of publication
2000
Pages
81 - 93
Database
ISI
SICI code
0010-4620(2000)43:1<81:AGAFVF>2.0.ZU;2-M
Abstract
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.