Models for the Combined Logical and Physical Design of Databases

Rajiv M. Dewan, Bezalel Gavish

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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 languageEnglish (US)
Pages (from-to)955-967
Number of pages13
JournalIEEE Transactions on Computers
Issue number7
StatePublished - Jul 1989
Externally publishedYes


  • 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


Dive into the research topics of 'Models for the Combined Logical and Physical Design of Databases'. Together they form a unique fingerprint.

Cite this