Browse Prior Art Database

DESCRIPTION OF A SET-THEORETIC DATA STRUCTURE

IP.com Disclosure Number: IPCOM000128395D
Original Publication Date: 1968-Aug-01
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

Childs, David L.: AUTHOR [+3]

Abstract

This paper is motivated by an assumption that many problems dealing with arbitrarily related data can be expedited on a digital computer by a storage structure which allows rapid execution of operations within and between sets of datum names. Such a structure should allow any set-theoretic operation without restricting the type of sets involved, thus allowing operations on sets of sets of...; sets of ordered pairs, ordered triples, ordered...; sets of variable length ntuples, n-tuples of arbitrary sets; etc., with the assurance that these operations will be executed rapidly. The purpose of a Set-Theoretic Data Structure (STDS) is to provide a storage representation for arbitrarily related data allowing quick access, minimal storage, and extreme flexibility. This paper will describe an STDS with the above properties utilizing a general implementation suitable for paging in a mass memory system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DESCRIPTION OF A SET-THEORETIC DATA STRUCTURE

THE UNIVERSITY OF MICHIGAN Technical Report 3 David L. Childs

CONCOMP: Research in Conversational Use of Computers F.H. Westervelt, Project Director ORA Project 07449

supported by: ADVANCED RESEARCH PROJECTS AGENCY DEPARTMENT OF DEFENSE WASHINGTON, D.C.

CONTRACT NO. DA-49-083 OSA-3050 ARPA ORDER NO. 716

administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1968, revised August 1968

ABSTRACT

This paper is motivated by an assumption that many problems dealing with arbitrarily related data can be expedited on a digital computer by a storage structure which allows rapid execution of operations within and between sets of datum names. Such a structure should allow any set- theoretic operation without restricting the type of sets involved, thus allowing operations on sets of sets of...; sets of ordered pairs, ordered triples, ordered...; sets of variable length ntuples, n- tuples of arbitrary sets; etc., with the assurance that these operations will be executed rapidly. The purpose of a Set-Theoretic Data Structure (STDS) is to provide a storage representation for arbitrarily related data allowing quick access, minimal storage, and extreme flexibility. This paper will describe an STDS with the above properties utilizing a general implementation suitable for paging in a mass memory system.

TABLE OF CONTENTS

ABSTRACT.....iii
I. INTRODUCTION.....1
II. GENERAL STORAGE REPRESENTATION.....2
III. OPERATION OF AN STDS.....4
IV. DETAILS OF β-BLOCK.....7
V. DETAILS OF η - BLOCK.....8
VI. SET REPRESENTATION.....9
VII. COMPLEXES AND N-TUPLES.....10
VIII. SET OPERATION SUBROUTINES.....15

University of Michigan Page 1 Aug 01, 1968

Page 2 of 14

DESCRIPTION OF A SET-THEORETIC DATA STRUCTURE

IX. SOME APPLICATIONS.....19
X. CONCLUSION.....26
APPENDIX.....27
GLOSSARY OF SYMBOLS.....31
REFERENCES.....33

[ Chapter ] I. INTRODUCTION

The overall goal, of which this paper is a part, is the development of a machine-independent data structure allowing rapid processing of data related by arbitrary assignment such as: the contents of a telephone book, library files, census reports, family lineage, graphic displays, information retrieval systems, networks, etc. Data which are non-intrinsically related have to be expressed (stored) in such a way as to define the way in which they are related before any data structure is applicable. Since any relation can be expressed in set theory as a set of ordered pairs and since set theory provides a wealth of operations for dealing with relations, a set- theoretic data structure appears worth investigation.

A Set-Theoretic Data Structure (STDS) is a storage representation of sets and set operations such that: given any family of sets η and any collection S of set operations an STDS is any storage representation which is isomorphic to η with S . The language used with an STDS may contain any set-...