---
title: "A Decomposition Storage Model"
authors:
  - "George P. Copeland"
  - "Setrag N. Khoshafian"
year: 1985
venue: "SIGMOD"
arxiv: null
doi: "10.1145/318898.318923"
source: "https://doi.org/10.1145/318898.318923"
topics:
  - relational-ecs-queries
  - array-programming-apl-bqn-q
seed_rank: 153
seed_batch: "prefill-2026-08-13"
reviewed: "2026-08-13"
pool: "languages"
relevance_score: 9
cites:
  - title: "The Grid File"
    url: "https://doi.org/10.1145/348.318586"
    year: 1984
    arxiv: null
    doi: "10.1145/348.318586"
  - title: "Extending the database relational model to capture more meaning"
    url: "https://doi.org/10.1145/320107.320109"
    year: 1979
    arxiv: null
    doi: "10.1145/320107.320109"
  - title: "Organization and maintenance of large ordered indexes"
    url: "https://doi.org/10.1007/bf00288683"
    year: 1972
    arxiv: null
    doi: "10.1007/bf00288683"
  - title: "Smalltalk-80: The Language and its Implementation"
    url: "https://inria.hal.science/hal-05183338"
    year: 1983
    arxiv: null
    doi: null
  - title: "Multivalued dependencies and a new normal form for relational databases"
    url: "https://doi.org/10.1145/320557.320571"
    year: 1977
    arxiv: null
    doi: "10.1145/320557.320571"
  - title: "Extending the data base relational model to capture more meaning"
    url: "https://doi.org/10.1145/582095.582122"
    year: 1979
    arxiv: null
    doi: "10.1145/582095.582122"
  - title: "Making smalltalk a database system"
    url: "https://doi.org/10.1145/602259.602300"
    year: 1984
    arxiv: null
    doi: "10.1145/602259.602300"
  - title: "Multidimensional Binary Search Trees in Database Applications"
    url: "https://doi.org/10.1109/tse.1979.234200"
    year: 1979
    arxiv: null
    doi: "10.1109/tse.1979.234200"
  - title: "Differential files"
    url: "https://doi.org/10.1145/320473.320484"
    year: 1976
    arxiv: null
    doi: "10.1145/320473.320484"
  - title: "The case for the reduced instruction set computer"
    url: "https://doi.org/10.1145/641914.641917"
    year: 1980
    arxiv: null
    doi: "10.1145/641914.641917"
  - title: "Prefix <i>B</i> -trees"
    url: "https://doi.org/10.1145/320521.320530"
    year: 1977
    arxiv: null
    doi: "10.1145/320521.320530"
  - title: "Modeling the storage architectures of commercial database systems"
    url: "https://doi.org/10.1145/4879.5392"
    year: 1985
    arxiv: null
    doi: "10.1145/4879.5392"
---

# A Decomposition Storage Model

## One-sentence takeaway

Copeland and Khoshafian argue that n-ary relations should be stored as per-attribute binary relations of \( \langle \text{surrogate}, \text{value} \rangle \) pairs rather than as n-ary n-tuples.

## Why it matters here

This is the physical twin of ano's columnar ECS world store: each component is a DSM column keyed by entity surrogate, so schema evolution, nulls, and attribute-local scans are storage facts rather than ORM accidents.

## Key ideas

- The n-ary storage model (NSM) clusters a whole tuple; DSM decomposes a relation into one binary relation per attribute, joined logically by invariant surrogates.
- Surrogates are system-owned identities that survive value updates, so identity is not a primary-key value the user can overwrite.
- Clustering, compression, and I/O become per-attribute: a query that touches two columns need not bring the other eighteen.
- Nulls and evolving schemas are cheap because a missing attribute is simply an absent pair, not a wide-row hole.
- The paper contrasts DSM with NSM on update, retrieval, and storage-cost grounds and treats the decomposition as a physical design, not a new data model.

## Caveats

## Links

- DOI: [10.1145/318898.318923](https://doi.org/10.1145/318898.318923)
- ACM: https://dl.acm.org/doi/10.1145/318898.318923