Abstract
Given the set of intended transactions, in this paper, we model the problem of choosing the most efficient decomposition of the universal set of attributes. Unlike other models which neglect the logical structure developed in database theory, the model developed in this paper incorporates it as part of a mathematical program. This provides a comprehensive and an integrated formulation for the combined logical and physical database design problem. The integrated problem and its ∍-approximation schemes are shown to be NP-complete. An example included at the end of the paper shows the benefit of such an approach over more conventional ones.
Original language | English (US) |
---|---|
Pages (from-to) | 955-967 |
Number of pages | 13 |
Journal | IEEE Transactions on Computers |
Volume | 38 |
Issue number | 7 |
DOIs | |
State | Published - Jul 1989 |
Externally published | Yes |
Keywords
- Complexity
- logical and physical database design
- lossless join
- models
- universal relation
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics