Accession Number:

ADA012308

Title:

An Analysis of Optimal Retrieval Systems with Updates.

Descriptive Note:

Technical rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE RESEARCH LAB OF ELECTRONICS

Personal Author(s):

Report Date:

1975-06-01

Pagination or Media Count:

72.0

Abstract:

The performance of computer-implemented systems for data storage, retrieval, and update is investigated. A data structure is modeled by a set D d sub 1, d sub 2,...d subabsolute value of D of data bases. A set of questions Lambda lambda sub 1, lambda sub 2,...,lambda sub n about any d an element of D may be answered. A memory that is bit-addressable by an algorithm or an automaton models a computer. A retrieval system is composed of a particular mapping of data bases onto memory representations and a particular algorithm or automaton. By accessing bits of memory the algorithm can answer any lambda an element of Lambda about the d represented in memory and can update memory to represent a new d an element of D. Lower bounds are derived for the performance measures of storage efficiency, retrieval efficiency, and update efficiency. The minima are simultaneously attainable by a retrieval system for some data structures of interest. trading relations between the measures exist for other data structures.

Subject Categories:

  • Information Science
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE