Access Path Selection in a Relational Database Management System.

Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., & Price, T. G. (1979). Access Path Selection in a Relational Database Management System. Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, 23-34.

Type

Conference paper

Intellectual base

Primary research

Year

1979

DOI

10.1145/582095.582099

Link

https://doi.org/10.1145/582095.582099

Cited from

computer_science

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Complexity (Time/Space)
  • The practical difference (30 vs 10⁹ operations) is constant-factor overhead, but determines whether queries complete in seconds or hours

    This sourceSystem R cost-based access-path/query optimization — table-scan vs index-based access — supports the data-warehouse example at D30-146. Verified existing and supporting.

• Equivalence-Preserving Rewriting
  • Database query optimisation: relational-algebra rewrites — selection push-down, join reordering, predicate rewriting — transform a declarative query into operationally different but result-equivalent plans, and the optimiser picks the lowest estimated cost.

    This sourceFoundational cost-based query optimization: relational-algebra-equivalent plans generated by rewrite rules and ranked by an estimated-cost model.

• Index
  • The prime's design discipline is what the index makes askable: selectivity governs whether the index helps at all — indexing a boolean is_active column where half the rows match is nearly useless, because the index still points at 500,000 rows, whereas last_name is highly selective.

    This sourceEstablishes selectivity as the determinant of whether an index pays off — a low-selectivity key points at too many rows to beat a scan.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:0e0d49ff91f6 · see in the full table