%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "2.20",
%%% date = "17 October 2006",
%%% time = "05:44:13 MDT",
%%% filename = "tods.bib",
%%% address = "University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "27396 29387 154426 1542591",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "bibliography, BibTeX, database systems,
%%% TODS",
%%% license = "public domain",
%%% supported = "yes",
%%% docstring = "This is a COMPLETE BibTeX bibliography for
%%% ACM Transactions on Database Systems (TODS)
%%% (CODEN ATDSD3, ISSN 0362-5915), which began
%%% publishing in March 1976.
%%%
%%% The companion bibliography pods.bib covers
%%% the ACM SIGACT-SIGMOD Symposia on
%%% Principles of Database Systems, and the
%%% companion bibliography vldb.bib covers the
%%% International Conferences on Very Large
%%% Data Bases. The companion bibliography
%%% sigmod.bib covers the ACM Special Interest
%%% Group on Management of Data SIGMOD Record
%%% newsletter.
%%%
%%% The journal has a World Wide Web site at
%%%
%%% http://www.acm.org/tods/
%%% http://www.acm.org/pubs/contents/journals/tods/
%%%
%%% At version 2.20, the year coverage looked
%%% like this:
%%%
%%% 1975 ( 1) 1986 ( 25) 1997 ( 14)
%%% 1976 ( 20) 1987 ( 25) 1998 ( 14)
%%% 1977 ( 23) 1988 ( 18) 1999 ( 13)
%%% 1978 ( 21) 1989 ( 23) 2000 ( 12)
%%% 1979 ( 27) 1990 ( 22) 2001 ( 13)
%%% 1980 ( 25) 1991 ( 24) 2002 ( 11)
%%% 1981 ( 30) 1992 ( 20) 2003 ( 15)
%%% 1982 ( 31) 1993 ( 20) 2004 ( 22)
%%% 1983 ( 30) 1994 ( 17) 2005 ( 29)
%%% 1984 ( 32) 1995 ( 13) 2006 ( 28)
%%% 1985 ( 25) 1996 ( 14)
%%% 19xx ( 2)
%%%
%%% Article: 650
%%% Book: 3
%%% InProceedings: 1
%%% Proceedings: 5
%%%
%%% Total entries: 659
%%%
%%% This bibliography was initially built from
%%% searches in the OCLC Content1st database.
%%% Additions were then made from all of the
%%% bibliographies in the TeX User Group
%%% collection, from bibliographies in the
%%% author's personal files, from the IEEE
%%% INSPEC CD-ROM database (1989--1995), from
%%% the Compendex database, from the American
%%% Mathematical Society MathSciNet database,
%%% and from the computer science bibliography
%%% collection on ftp.ira.uka.de in
%%% /pub/bibliography to which many people of
%%% have contributed. The snapshot of this
%%% collection was taken on 5-May-1994, and it
%%% consists of 441 BibTeX files, 2,672,675
%%% lines, 205,289 entries, and 6,375
%%% <at>String{} abbreviations, occupying
%%% 94.8MB of disk space. Missing data in many
%%% entries were supplied after consulting
%%% original journal issues.
%%%
%%% Numerous errors in the sources noted above
%%% have been corrected. Spelling has been
%%% verified with the UNIX spell and GNU ispell
%%% programs using the exception dictionary
%%% stored in the companion file with extension
%%% .sok.
%%%
%%% BibTeX citation tags are uniformly chosen as
%%% name:year:abbrev, where name is the family
%%% name of the first author or editor, year is a
%%% 4-digit number, and abbrev is a 3-letter
%%% condensation of important title words.
%%% Citation labels were automatically generated
%%% by software developed for the BibNet Project.
%%%
%%% In this bibliography, entries are sorted in
%%% publication order, with the help of
%%% ``bibsort -byvolume''. The bibsort utility
%%% is available from ftp.math.utah.edu in
%%% /pub/tex/bib.
%%%
%%% The checksum field above contains a CRC-16
%%% checksum as the first value, followed by the
%%% equivalent of the standard UNIX wc (word
%%% count) utility output of lines, words, and
%%% characters. This is produced by Robert
%%% Solovay's checksum utility.",
%%% }
%%% ====================================================================
@Preamble{
"\hyphenation{
}"
}
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Journal abbreviations:
@String{j-CACM = "Communications of the ACM"}
@String{j-TODS = "ACM Transactions on Database Systems"}
%%% ====================================================================
%%% Publishers and their addresses:
@String{pub-ACM = "ACM Press"}
@String{pub-ACM:adr = "New York, NY 10036, USA"}
@String{pub-IEEE = "IEEE Computer Society Press"}
@String{pub-IEEE:adr = "1109 Spring Street, Suite 300, Silver
Spring, MD 20910, USA"}
@String{pub-MORGAN-KAUFMANN = "Morgan Kaufmann Publishers"}
@String{pub-MORGAN-KAUFMANN:adr = "Los Altos, CA 94022, USA"}
%%% ====================================================================
%%% Bibliography entries:
@Article{Yao:1977:ABA,
author = "S. B. Yao",
title = "Approximating Block Accesses in Database
Organization",
journal = j-CACM,
volume = "20",
number = "4",
pages = "260--261",
month = apr,
year = "1977",
CODEN = "CACMA2",
ISSN = "0001-0782",
bibdate = "Tue Sep 20 23:14:33 1994",
bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Graefe.bib
and
ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib",
note = "Also published in \cite{Yao:1977:ABM}.",
keywords = "selectivity estimation I/O cost query optimization
CACM",
}
@Article{Hsiao:1976:ATD,
author = "David K. Hsiao",
title = "{ACM Transactions on Database Systems}: aim and
scope",
journal = j-TODS,
volume = "1",
number = "1",
pages = "1--2",
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p1-hsiao/p1-hsiao.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p1-hsiao/",
abstract = "Record-keeping and decision-making in industry and
government are increasingly based on data stored in
computer processable databases. Thus the need for
improved computer technology for building, managing,
and using these databases is clearly evident. This need
is particularly acute in a complex society where the
interrelationships among various aspects of the society
must be identified and represented. The data which must
be used to represent these relationships are growing
more complex in nature and becoming greater in size.
Furthermore, the increasing on-line use of computer
systems and the proliferation and mass introduction of
multilevel secondary storage suggests that future
computer systems will be primarily oriented toward
database management. The large size of future on-line
databases will require the computer system to manage
local as well as physical resources. The management of
logical resources is concerned with the organization,
access, update, storage, and sharing of the data and
programs in the database. In addition, the sharing of
data means that the database system must be capable of
providing privacy protection and of controlling access
to the users' data. The term {\em data\/} is
interpreted broadly to include textual, numeric, and
signal data as well as data found in structured
records.\par
The aim of {\em ACM Transactions on Database Systems\/}
(TODS) is to serve as a focal point for an integrated
dissemination of database research and development on
storage and processor hardware, system software,
applications, information science, information
analysis, and file management. These areas are
particularly relevant to the following ACM Special
Interest Groups: Business Data Processing (SIGBDP),
Information Retrieval (SIGIR), and Management of Data
(SIGMOD). TODS will also embrace parts of the
Management/Database Systems and the Information
Retrieval and Language Processing sections of {\em
Communications of the ACM}.\par
High quality papers on all aspects of computer database
systems will be published in TODS. The scope of TODS
emphasizes data structures; storage organization; data
collection and dissemination; search and retrieval
strategies; update strategies; access control
techniques; data integrity; security and protection;
design and implementation of database software;
database related languages including data description
languages, query languages, and procedural and
nonprocedural data manipulation languages; language
processing; analysis and classification of data;
database utilities; data translation techniques;
distributed database problems and techniques; database
recovery and restart; database restructuring; adaptive
data structures; concurrent access techniques; database
computer hardware architecture; performance and
evaluation; intelligent front ends; and related
subjects such as privacy and economic issues.",
acknowledgement = ack-nhfb,
subject = "Information Systems --- Database Management ---
Systems (H.2.4)",
}
@Article{Chen:1976:ERM,
author = "Peter Pin-Shan S. Chen",
title = "The Entity-Relationship Model: Toward a Unified View
of Data",
journal = j-TODS,
volume = "1",
number = "1",
pages = "9--36",
month = mar,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compiler/prog.lang.theory.bib; Database/Graefe.bib;
Distributed/gesturing.bib;
http://www.acm.org/pubs/toc/; Misc/is.bib;
Object/Nierstrasz.bib",
note = "Reprinted in \cite{Stonebraker:1988:RDS}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p9-chen/p9-chen.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p9-chen/",
abstract = "A data model, called the entity-relationship model, is
proposed. This model incorporates some of the important
semantic information about the real world. A special
diagrammatic technique is introduced as a tool for
database design. An example of database design and
description using the model and the diagrammatic
technique is given. Some implications for data
integrity, information retrieval, and data manipulation
are discussed.\par
The entity-relationship model can be used as a basis
for unification of different views of data: the network
model, the relational model, and the entity set model.
Semantic ambiguities in these models are analyzed.
Possible ways to derive their views of data from the
entity-relationship model are presented.",
acknowledgement = ack-nhfb,
keywords = "Data Base Task Group; data definition and
manipulation; data integrity and consistency; data
models; database design; dblit; entity set model;
entity-relationship; entity-relationship model; logical
view of data; network model; relational model;
semantics of data; TODS",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases}",
}
@Article{Bayer:1976:EST,
author = "R. Bayer and J. K. Metzger",
title = "On the Encipherment of Search Trees and Random Access
Files",
journal = j-TODS,
volume = "1",
number = "1",
pages = "37--52",
month = mar,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in \cite[p.~508--510]{Kerr:1975:PIC}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p37-bayer/p37-bayer.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p37-bayer/",
abstract = "The securing of information in indexed, random access
files by means of privacy transformations must be
considered as a problem distinct from that for
sequential files. Not only must processing overhead due
to encrypting be considered, but also threats to
encipherment arising from updating and the file
structure itself must be countered. A general
encipherment scheme is proposed for files maintained in
a paged structure in secondary storage. This is applied
to the encipherment of indexes organized as $B$-trees;
a $B$-tree is a particular type of multiway search
tree. Threats to the encipherment of $B$-trees,
especially relating to updating, are examined, and
countermeasures are proposed for each. In addition, the
effect of encipherment on file access and update, on
paging mechanisms, and on files related to the
enciphered index are discussed. Many of the concepts
presented may be readily transferred to other forms of
multiway index trees and to binary search trees.",
acknowledgement = ack-nhfb,
annote = "Trees versus hashing as his 1974 IFIP paper?",
keywords = "",
subject = "Software --- Operating Systems --- Security and
Protection (D.4.6): {\bf Access controls}; Software ---
Operating Systems --- Security and Protection (D.4.6):
{\bf Cryptographic controls}",
}
@Article{Lin:1976:DRA,
author = "Chyuan Shiun Lin and Diane C. P. Smith and John Miles
Smith",
title = "The design of a rotating associative memory for
relational database applications",
journal = j-TODS,
volume = "1",
number = "1",
pages = "53--65",
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p53-lin/p53-lin.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p53-lin/",
abstract = "The design and motivation for a rotating associative
relational store (RARES) is described. RARES is
designed to enhance the performance of an optimizing
relational query interface by supporting important high
level optimization techniques. In particular, it can
perform tuple selection operations at the storage
device and also can provide a mechanism for efficient
sorting. Like other designs for rotating associative
stores, RARES contains search logic which is attached
to the heads of a rotating head-per-track storage
device. RARES is distinct from other designs in that it
utilizes a novel ``orthogonal'' storage layout. This
layout allows a high output rate of selected tuples
even when a sort order in the stored relation must be
preserved. As in certain other designs, RARES can
usually output a tuple as soon as it is found to
satisfy the selection criteria. However, relative to
these designs, the orthogonal layout allows an order of
magnitude reduction in the capacity of storage local to
the search logic.",
acknowledgement = ack-nhfb,
keywords = "associative memory; content addressability; data
organization; head-per-track disks; memory systems;
relational database; rotating devices; search logic;
sorting technique",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases}",
}
@Article{Mahmoud:1976:OAR,
author = "Samy Mahmoud and J. S. Riordon",
title = "Optimal Allocation of Resources in Distributed
Information Networks",
journal = j-TODS,
volume = "1",
number = "1",
pages = "66--78",
month = mar,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p66-mahmoud/p66-mahmoud.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p66-mahmoud/",
abstract = "The problems of file allocation and capacity
assignment in a fixed topology distributed computer
network are examined. These two aspects of the design
are tightly coupled by means of an average message
delay constraint. The objective is to allocate copies
of information files to network nodes and capacities to
network links so that a minimum cost is achieved
subject to network delay and file availability
constraints. A model for solving the problem is
formulated and the resulting optimization problem is
shown to fall into a class of nonlinear integer
programming problems. Deterministic techniques for
solving this class of problems are computationally
cumbersome, even for small size problems. A new
heuristic algorithm is developed, which is based on a
decomposition technique that greatly reduces the
computational complexity of the problem. Numerical
results for a variety of network configurations
indicate that the heuristic algorithm, while not
theoretically convergent, yields practicable low cost
solutions with substantial savings in computer
processing time and storage requirements. Moreover, it
is shown that this algorithm is capable of solving
realistic network problems whose solutions using
deterministic techniques are computationally
intractable.",
acknowledgement = ack-nhfb,
keywords = "data files; distributed computed; information
networks; link capacities; resource sharing",
subject = "Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2)",
}
@Article{Stemple:1976:DMF,
author = "David W. Stemple",
title = "A Database Management Facility for Automatic
Generation of Database Managers",
journal = j-TODS,
volume = "1",
number = "1",
pages = "79--94",
month = mar,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in \cite[p.~252]{Kerr:1975:PIC}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-1/p79-stemple/p79-stemple.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-1/p79-stemple/",
abstract = "A facility is described for the implementation of
database management systems having high degrees of {\em
horizontal\/} data independence, i.e. independence from
chosen logical properties of a database as opposed to
{\em vertical\/} independence from storage structures.
The facility consists of a high level language for the
specification of virtual database managers, a compiler
from this language to a pseudomachine language, and an
interpreter for the pseudomachine language.\par
It is shown how this facility can be used to produce
efficient database management systems with any degree
of both horizontal and vertical data independence. Two
key features of this tool are the compilation of
tailored database managers from individual schemas and
multiple levels of optional binding.",
acknowledgement = ack-nhfb,
annote = "Describes SLUSH and SLIM, a proposed compiler and
interpreter to operate on network schemas with
adjustable binding times.",
keywords = "data independence; database management systems",
subject = "Information Systems --- Database Management ---
Systems (H.2.4); Information Systems --- Database
Management (H.2); Software --- Operating Systems ---
Systems Programs and Utilities (D.4.9): {\bf make}",
}
@Article{Astrahan:1976:SRR,
author = "M. M. Astrahan and M. W. Blasgen and D. D. Chamberlin
and K. P. Eswaran and J. N. Gray and P. P. Griffiths
and W. F. King and R. A. Lorie and P. R. McJones and J.
W. Mehl and G. R. Putzolu and I. L. Traiger and B. W.
Wade and V. Watson",
title = "{System R}: {A} Relational Approach to Database
Management",
journal = j-TODS,
volume = "1",
number = "2",
pages = "97--137",
month = jun,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/; Object/Nierstrasz.bib",
note = "Also published in/as: IBM, San Jose, Research Report.
No. RJ-1738, Feb. 1976. Reprinted in
\cite{Stonebraker:1988:RDS}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-2/p97-astrahan/p97-astrahan.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-2/p97-astrahan/",
abstract = "System R is a database management system which
provides a high level relational data interface. The
systems provides a high level of data independence by
isolating the end user as much as possible from
underlying storage structures. The system permits
definition of a variety of relational views on common
underlying data. Data control features are provided,
including authorization, integrity assertions,
triggered transactions, a logging and recovery
subsystem, and facilities for maintaining data
consistency in a shared-update environment.\par
This paper contains a description of the overall
architecture and design of the system. At the present
time the system is being implemented and the design
evaluated. We emphasize that System R is a vehicle for
research in database architecture, and is not planned
as a product.",
acknowledgement = ack-nhfb,
keywords = "authorization; data structures; database; dblit; index
structures; locking; nonprocedural language; recovery;
relational model; TODS relation database IBM San Jose",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf System R}; Information Systems
--- Database Management --- Systems (H.2.4): {\bf
Relational databases}; Information Systems --- Database
Management (H.2)",
}
@Article{Navathe:1976:RLD,
author = "Shamkant B. Navathe and James P. Fry",
title = "Restructuring for Large Data Bases: Three Levels of
Abstraction",
journal = j-TODS,
volume = "1",
number = "2",
pages = "138--158",
month = mar,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in \cite[p.~174]{Kerr:1975:PIC}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-2/p138-navathe/p138-navathe.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-2/p138-navathe/",
abstract = "The development of a powerful restructuring function
involves two important components--the unambiguous
specification of the restructuring operations and the
realization of these operations in a software system.
This paper is directed to the first component in the
belief that a precise specification will provide a firm
foundation for the development of restructuring
algorithms and, subsequently, their implementation. The
paper completely defines the semantics of the
restructuring of tree structured databases.\par
The delineation of the restructuring function is
accomplished by formulating three different levels of
abstraction, with each level of abstraction
representing successively more detailed semantics of
the function.\par
At the first level of abstraction, the schema
modification, three types are identified--naming,
combining, and relating; these three types are further
divided into eight schema operations. The second level
of abstraction, the instance operations, constitutes
the transformations on the data instances; they are
divided into group operations such as replication,
factoring, union, etc., and group relation operations
such as collapsing, refinement, fusion, etc. The final
level, the item value operations, includes the actual
item operations, such as copy value, delete value, or
create a null value.",
acknowledgement = ack-nhfb,
keywords = "data definition; data translation; database; database
management systems; logical restructuring",
subject = "Information Systems --- Database Management (H.2);
Information Systems --- Database Management ---
Heterogeneous Databases (H.2.5): {\bf Data
translation**}",
}
@Article{Yao:1976:DDR,
author = "S. B. Yao and K. S. Das and T. J. Teorey",
title = "A Dynamic Database Reorganization Algorithm",
journal = j-TODS,
volume = "1",
number = "2",
pages = "159--174",
month = jun,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in/as: Purdue Un., TR-168, Nov. 1975.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-2/p159-yao/p159-yao.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-2/p159-yao/",
abstract = "Reorganization is necessary in some databases for
overcoming the performance deterioration caused by
updates. The paper presents a dynamic reorganization
algorithm which makes the reorganization decision by
measuring the database search costs. Previously, the
reorganization intervals could only be determined for
linear deterioration and known database lifetime. It is
shown that the dynamic reorganization algorithm is near
optimum for constant reorganization cost and is
superior for increasing reorganization cost. In
addition, it can be applied to cases of unknown
database lifetime and nonlinear performance
deterioration. The simplicity, generality, and
efficiency appear to make this good heuristic for
database reorganization.",
acknowledgement = ack-nhfb,
keywords = "database; file organization; information retrieval;
reorganization",
subject = "Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2): {\bf File
organization}; Information Systems --- Information
Storage and Retrieval --- Information Search and
Retrieval (H.3.3): {\bf Retrieval models}",
}
@Article{Burkhard:1976:HTA,
author = "Walter A. Burkhard",
title = "Hashing and Trie Algorithms for Partial-Match
Retrieval",
journal = j-TODS,
volume = "1",
number = "2",
pages = "175--187",
month = jun,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib; Graphics/siggraph/76.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in/as: UCSD, Appl. Physics and Inf. Sc,
CS TR.2, Jun. 1975.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-2/p175-burkhard/p175-burkhard.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-2/p175-burkhard/",
abstract = "File designs suitable for retrieval from a file of
$k$-letter words when queries may be only partially
specified are examined. A new class of partial match
file designs (called PMF designs) based upon hash
coding and trie search algorithms which provide good
worst-case performance is introduced. Upper bounds on
the worst-case performance of these designs are given
along with examples of files achieving the bound. Other
instances of PMF designs are known to have better
worst-case performances. The implementation of the file
designs with associated retrieval algorithms is
considered. The amount of storage required is
essentially that required of the records themselves.",
acknowledgement = ack-nhfb,
keywords = "algorithms; analysis; associative retrieval; hash
coding; partial match; retrieval; searching; trie
search",
oldlabel = "geom-96",
subject = "Mathematics of Computing --- Mathematical Software
(G.4): {\bf Algorithm design and analysis}; Information
Systems --- Information Storage and Retrieval ---
Information Search and Retrieval (H.3.3): {\bf
Retrieval models}",
}
@Article{Stonebraker:1976:DII,
author = "Michael Stonebraker and Eugene Wong and Peter Kreps
and Gerald Held",
title = "The Design and Implementation of {INGRES}",
journal = j-TODS,
volume = "1",
number = "3",
pages = "189--222",
month = sep,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/; Parallel/Multi.bib",
note = "Reprinted in \cite{Stonebraker:1988:RDS}. Also
published in/as: UCB, Elec. Res. Lab, Memo No.
ERL-M577, Jan. 1976.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-3/p189-stonebraker/p189-stonebraker.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-3/p189-stonebraker/",
abstract = "The currently operational (March 1976) version of the
INGRES database management system is described. This
multiuser system gives a relational view of data,
supports two high level nonprocedural data
sublanguages, and runs as a collection of user
processes on top of the UNIX operating system for
Digital Equipment Corporation PDP 11/40, 11/45, and
11/70 computers. Emphasis is on the design decisions
and tradeoffs related to (1) structuring the system
into processes, (2) embedding one command language in a
general purpose programming language, (3) the
algorithms implemented to process interactions, (4) the
access methods implemented, (5) the concurrency and
recovery control currently provided, and (6) the data
structures used for system catalogs and the role of the
database administrator.\par
Also discussed are (1) support for integrity
constraints (which is only partly operational), (2) the
not yet supported features concerning views and
protection, and (3) future plans concerning the
system.",
acknowledgement = ack-nhfb,
annote = "Describes implementation of INGRES, a non-distributed
relational database system. This paper is useful for
understanding the distributed INGRES paper.",
keywords = "concurrency; data integrity; data organization; data
sublanguage; database optimization; nonprocedural
language; protection; QUEL EQUEL query modification
process structure Halloween problem TODS; query
decomposition; query language; relational database",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases};
Information Systems --- Database Management ---
Languages (H.2.3); Information Systems --- Database
Management --- General (H.2.0): {\bf Security,
integrity, and protection**}",
}
@Article{Wong:1976:DSQ,
author = "Eugene Wong and Karel Youssefi",
title = "Decomposition --- {A} Strategy for Query Processing",
journal = j-TODS,
volume = "1",
number = "3",
pages = "223--241",
month = sep,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in/as: UCB, Elec. Res. Lab, Memo No.
ERL-574, Jan. 1976;",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-3/p223-wong/p223-wong.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-3/p223-wong/",
abstract = "Strategy for processing multivariable queries in the
database management system INGRES is considered. The
general procedure is to decompose the query into a
sequence of one-variable queries by alternating between
(a) reduction: breaking off components of the query
which are joined to it by a single variable, and (b)
tuple substitution: substituting for one of the
variables a tuple at a time. Algorithms for reduction
and for choosing the variable to be substituted are
given. In most cases the latter decision depends on
estimation of costs; heuristic procedures for making
such estimates are outlined.",
acknowledgement = ack-nhfb,
annote = "INGRES query decomposition by reduction to single
variable queries, and tuple substitution --- choosing a
variable and for it from all tuples, generating a
family of queries in one fewer variable.",
keywords = "connected query; decomposition; detachment; Ingres
TODS; irreducible query; joining (overlapping)
variable; query processing; relational database; tuple
substitution; variable selection",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases};
Information Systems --- Database Management --- Systems
(H.2.4): {\bf Query processing}",
}
@Article{Griffiths:1976:AMR,
author = "Patricia P. Griffiths and Bradford W. Wade",
title = "An Authorization Mechanism for a Relational Database
System",
journal = j-TODS,
volume = "1",
number = "3",
pages = "242--255",
month = sep,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-3/p242-griffiths/p242-griffiths.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-3/p242-griffiths/",
abstract = "A multiuser database system must selectively permit
users to share data, while retaining the ability to
restrict data access. There must be a mechanism to
provide protection and security, permitting information
to be accessed only by properly authorized users.
Further, when tables or restricted views of tables are
created and destroyed dynamically, the granting,
authentication, and revocation of authorization to use
them must also be dynamic. Each of these issues and
their solutions in the context of the relational
database management system System R are discussed.
\par
When a database user creates a table, he is fully and
solely authorized to perform upon it actions such as
read, insert, update, and delete. He may explicitly
grant to any other user any or all of his privileges on
the table. In addition he may specify that that user is
authorized to further grant these privileges to still
other users. The result is a directed graph of granted
privileges originating from the table creator.\par
At some later time a user A may revoke some or all of
the privileges which he previously granted to another
user B. This action usually revokes the entire subgraph
of the grants originating from A's grant to B. It may
be, however, that B will still possess the revoked
privileges by means of a grant from another user C, and
therefore some or all of B's grants should not be
revoked. This problem is discussed in detail, and an
algorithm for detecting exactly which of B's grants
should be revoked is presented.",
acknowledgement = ack-nhfb,
annote = "Defines a dynamic authorization mechanism. A database
user can grant or revoke privileges (such as to read,
insert, or delete) on a file that he has created.
Furthermore, he can authorize others to grant these
same privileges. The database management system keeps
track of a directed graph, emanating from the creator
of granted privileges.",
keywords = "access control; authorization; data dependent
authorization; database systems; privacy; protection in
databases; revocation of authorization; security",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases};
Information Systems --- Database Management --- Systems
(H.2.4); Information Systems --- Database Management
--- General (H.2.0): {\bf Security, integrity, and
protection**}",
}
@Article{Severance:1976:DFT,
author = "Dennis G. Severance and Guy M. Lohman",
title = "Differential Files: Their Application to the
Maintenance of Large Databases",
journal = j-TODS,
volume = "1",
number = "3",
pages = "256--267",
month = sep,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-3/p256-severance/p256-severance.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-3/p256-severance/",
abstract = "The representation of a collection of data in terms of
its differences from some preestablished point of
reference is a basic storage compaction technique which
finds wide applicability. This paper describes a
differential database representation which is shown to
be an efficient method for storing large and volatile
databases. The technique confines database
modifications to a relatively small area of physical
storage and as a result offers two significant
operational advantages. First, because the ``reference
point'' for the database is inherently static, it can
be simply and efficiently stored. Second, since all
modifications to the database are physically localized,
the process of backup and the process of recovery are
relatively fast and inexpensive.",
acknowledgement = ack-nhfb,
keywords = "backup and recovery; data sharing; database
maintenance; differential files",
subject = "Information Systems --- Database Management (H.2);
Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2): {\bf File
organization}",
}
@Article{Shneiderman:1976:BSS,
author = "Ben Shneiderman and Victor Goodman",
title = "Batched Searching of Sequential and Tree Structured
Files",
journal = j-TODS,
volume = "1",
number = "3",
pages = "268--275",
month = sep,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "See comments in \cite{Piwowarski:1985:CBS}. Also
published in/as: Indiana Un., CSD Tech. Ref. 0132.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-3/p268-shneiderman/p268-shneiderman.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-3/p268-shneiderman/",
abstract = "The technique of batching searches has been ignored in
the context of disk based online data retrieval
systems. This paper suggests that batching be
reconsidered for such systems since the potential
reduction in processor demand may actually reduce
response time. An analysis with sample numerical
results and algorithms is presented.",
acknowledgement = ack-nhfb,
keywords = "",
subject = "Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2): {\bf File
organization}; Information Systems --- Information
Storage and Retrieval (H.3)",
}
@Article{Bernstein:1976:STN,
author = "Philip A. Bernstein",
title = "Synthesizing Third Normal Form Relations from
Functional Dependencies",
journal = j-TODS,
volume = "1",
number = "4",
pages = "277--298",
month = dec,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib; Distributed/gesturing.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-4/p277-bernstein/p277-bernstein.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-4/p277-bernstein/",
abstract = "It has been proposed that the description of a
relational database can be formulated as a set of
functional relationships among database attributes.
These functional relationships can then be used to
synthesize algorithmically a relational scheme. It is
the purpose of this paper to present an effective
procedure for performing such a synthesis. The schema
that results from this procedure is proved to be in
Codd's third normal form and to contain the fewest
possible number of relations. Problems with earlier
attempts to construct such a procedure are also
discussed.",
acknowledgement = ack-nhfb,
keywords = "database schema; functional dependency; relational
model; semantics of data; third normal form",
subject = "Information Systems --- Database Management ---
Logical Design (H.2.1): {\bf Normal forms}; Information
Systems --- Database Management --- Logical Design
(H.2.1): {\bf Schema and subschema}; Information
Systems --- Database Management --- Logical Design
(H.2.1): {\bf Data models}",
}
@Article{Liu:1976:APS,
author = "Jane W. S. Liu",
title = "Algorithms for parsing search queries in systems with
inverted file organization",
journal = j-TODS,
volume = "1",
number = "4",
pages = "299--316",
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-4/p299-liu/p299-liu.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-4/p299-liu/",
abstract = "In an inverted file system a query is in the form of a
Boolean expression of index terms. In response to a
query the system accesses the inverted lists
corresponding to the index terms, merges them, and
selects from the merged list those records that satisfy
the search logic. Considered in this paper is the
problem of determining a Boolean expression which leads
to the minimum total merge time among all Boolean
expressions that are equivalent to the expression given
in the query. This problem is the same as finding an
optimal merge tree among all trees that realize the
truth function determined by the Boolean expression in
the query. Several algorithms are described which
generate optimal merge trees when the sizes of overlaps
between different lists are small compared with the
length of the lists.",
acknowledgement = ack-nhfb,
keywords = "inverted file systems; merge algorithms; parsing
Boolean queries",
subject = "Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2): {\bf File
organization}; Mathematics of Computing ---
Mathematical Software (G.4): {\bf Algorithm design and
analysis}; Information Systems --- Database Management
--- Systems (H.2.4): {\bf Query processing}",
}
@Article{Sherman:1976:PDM,
author = "Stephen W. Sherman and Richard S. Brice",
title = "Performance of a Database Manager in a Virtual Memory
System",
journal = j-TODS,
volume = "1",
number = "4",
pages = "317--343",
month = dec,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-4/p317-sherman/p317-sherman.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-4/p317-sherman/",
abstract = "Buffer space is created and managed in database
systems in order to reduce accesses to the I/O devices
for database information. In systems using virtual
memory any increase in the buffer space may be
accompanied by an increase in paging. The effects of
these factors on system performance are quantified
where system performance is a function of page faults
and database accesses to I/O devices. This phenomenon
is examined through the analysis of empirical data
gathered in a multifactor experiment. The factors
considered are memory size, size of buffer space,
memory replacement algorithm, and buffer management
algorithm. The improvement of system performance
through an increase in the size of the buffer space is
demonstrated. It is also shown that for certain values
of the other factors an increase in the size of the
buffer space can cause performance to deteriorate.",
acknowledgement = ack-nhfb,
keywords = "buffer manager; Buffer operating system support TODS;
database management; double paging; page faults; page
replacement algorithm; performance; virtual buffer;
virtual memory",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Database Manager}; Mathematics of
Computing --- Mathematical Software (G.4): {\bf
Algorithm design and analysis}; Computer Systems
Organization --- Performance of Systems (C.4)",
}
@Article{Donovan:1976:DSA,
author = "John J. Donovan",
title = "Database System Approach to Management Decision
Support",
journal = j-TODS,
volume = "1",
number = "4",
pages = "344--369",
month = dec,
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-4/p344-donovan/p344-donovan.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-4/p344-donovan/",
abstract = "Traditional intuitive methods of decision-making are
no longer adequate to deal with the complex problems
faced by the modern policymaker. Thus systems must be
developed to provide the information and analysis
necessary for the decisions which must be made. These
systems are called decision support systems. Although
database systems provide a key ingredient to decision
support systems, the problems now facing the
policymaker are different from those problems to which
database systems have been applied in the past. The
problems are usually not known in advance, they are
constantly changing, and answers are needed quickly.
Hence additional technologies, methodologies, and
approaches must expand the traditional areas of
database and operating systems research (as well as
other software and hardware research) in order for them
to become truly effective in supporting policymakers.
\par
This paper describes recent work in this area and
indicates where future work is needed. Specifically the
paper discusses: (1) why there exists a vital need for
decision support systems; (2) examples from work in the
field of energy which make explicit the characteristics
which distinguish these decision support systems from
traditional operational and managerial systems; (3) how
an awareness of decision support systems has evolved,
including a brief review of work done by others and a
statement of the computational needs of decision
support systems which are consistent with contemporary
technology; (4) an approach which has been made to meet
many of these computational needs through the
development and implementation of a computational
facility, the Generalized Management Information System
(GMIS); and (5) the application of this computational
facility to a complex and important energy problem
facing New England in a typical study within the New
England Energy Management Information System (NEEMIS)
Project.",
acknowledgement = ack-nhfb,
keywords = "database systems; decision support systems; management
applications; modeling; networking; relational; virtual
machines",
subject = "Information Systems --- Database Management (H.2);
Information Systems --- Database Management --- Systems
(H.2.4)",
}
@Article{McGee:1976:UCD,
author = "William C. McGee",
title = "On user criteria for data model evaluation",
journal = j-TODS,
volume = "1",
number = "4",
pages = "370--387",
year = "1976",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1976-1-4/p370-mcgee/p370-mcgee.pdf;
http://www.acm.org/pubs/citations/journals/tods/1976-1-4/p370-mcgee/",
abstract = "The emergence of a database technology in recent years
has focused interest on the subject of data models. A
data model is the class of logical data structures
which a computer system or language makes available to
the user for the purpose of formulating data processing
applications. The diversity of computer systems and
languages has resulted in a corresponding diversity of
data models, and has created a problem for the user in
selecting a data model which is in some sense
appropriate to a given application. An evaluation
procedure is needed which will allow the user to
evaluate alternative models in the context of a
specific set of applications. This paper takes a first
step toward such a procedure by identifying the
attributes of a data model which can be used as
criteria for evaluating the model. Two kinds of
criteria are presented: use criteria, which measure the
usability of the model; and implementation criteria,
which measure the implementability of the model and the
efficiency of the resulting implementation. The use of
the criteria is illustrated by applying them to three
specific models: an $n$-ary relational model, a
hierarchic model, and a network model.",
acknowledgement = ack-nhfb,
keywords = "data model; data model evaluation; data model
selection; hierarchic model; network model; relational
model",
subject = "Information Systems --- Database Management ---
Logical Design (H.2.1): {\bf Data models}",
}
@Article{Kam:1977:MSD,
author = "John B. Kam and Jeffrey D. Ullman",
title = "A Model of Statistical Databases and Their Security",
journal = j-TODS,
volume = "2",
number = "1",
pages = "1--10",
month = mar,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-1/p1-kam/p1-kam.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-1/p1-kam/",
abstract = "Considered here, for a particular model of databases
in which only information about relatively large sets
of records can be obtained, is the question of whether
one can from statistical information obtain information
about individuals. Under the assumption that the data
in the database is taken from arbitrary integers, it is
shown that essentially nothing can be inferred. It is
also shown that when the values are known to be
imprecise in some fixed range, one can often deduce the
values of individual records.",
acknowledgement = ack-nhfb,
keywords = "compromisability; data security; linear independence;
statistical database; vector spece",
subject = "Information Systems --- Database Management ---
Database Applications (H.2.8): {\bf Statistical
databases}; Information Systems --- Database Management
--- General (H.2.0): {\bf Security, integrity, and
protection**}",
}
@Article{Bayer:1977:PBT,
author = "Rudolf Bayer and Karl Unterauer",
title = "Prefix {B}-trees",
journal = j-TODS,
volume = "2",
number = "1",
pages = "11--26",
month = mar,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in/as: IBM Yorktwon, Technical Report
RJ1796, Jun. 1976.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-1/p11-bayer/p11-bayer.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-1/p11-bayer/",
abstract = "Two modifications of $B$-trees are described, simple
prefix $B$-trees and prefix $B$-trees. Both store only
parts of keys, namely prefixes, in the index part of a
$B$*-tree. In simple prefix $B$-trees those prefixes
are selected carefully to minimize their length. In
prefix $B$-trees the prefixes need not be fully stored,
but are reconstructed as the tree is searched. Prefix
$B$-trees are designed to combine some of the
advantages of $B$-trees, digital search trees, and key
compression techniques while reducing the processing
overhead of compression techniques.",
acknowledgement = ack-nhfb,
annote = "Index Btree structures can easily be compressed.",
keywords = "truncation compression TODS",
subject = "Data --- Data Structures (E.1): {\bf Trees}",
}
@Article{Schkolnick:1977:CAH,
author = "Mario Schkolnick",
title = "A Clustering Algorithm for Hierarchical Structures",
journal = j-TODS,
volume = "2",
number = "1",
pages = "27--44",
month = may,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Tue Dec 10 09:36:45 1996",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib",
annote = "Optimal file partitioning, applied to IMS.",
}
@Article{Yao:1977:ABM,
author = "S. B. Yao",
title = "An Attribute Based Model for Database Access Cost
Analysis",
journal = j-TODS,
volume = "2",
number = "1",
pages = "45--67",
month = mar,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/",
note = "Also published in \cite{Yao:1977:ABA}.",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-1/p45-yao/p45-yao.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-1/p45-yao/",
abstract = "A generalized model for physical database
organizations is presented. Existing database
organizations are shown to fit easily into the model as
special cases. Generalized access algorithms and cost
equations associated with the model are developed and
analyzed. The model provides a general design framework
in which the distinguishing properties of database
organizations are made explicit and their performances
can be compared.",
acknowledgement = ack-nhfb,
keywords = "B-tree; database model; database organization;
database performance; estimation approximation TODS;
evaluation; index organization; index sequential;
inverted file; multilist",
subject = "Information Systems --- Database Management ---
Logical Design (H.2.1); Information Systems ---
Information Storage and Retrieval --- Content Analysis
and Indexing (H.3.1); Data --- Data Structures (E.1):
{\bf Trees}",
}
@Article{Anderson:1977:MCS,
author = "Henry D. Anderson and P. Bruce Berra",
title = "Minimum Cost Selection of Secondary Indexes for
Formatted Files",
journal = j-TODS,
volume = "2",
number = "1",
pages = "68--90",
month = mar,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
http://www.acm.org/pubs/toc/; Misc/is.bib",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-1/p68-anderson/p68-anderson.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-1/p68-anderson/",
abstract = "Secondary indexes are often used in database
management systems for secondary key retrieval.
Although their use can improve retrieval time
significantly, the cost of index maintenance and
storage increases the overhead of the file processing
application. The optimal set of indexed secondary keys
for a particular application depends on a number of
application dependent factors. In this paper a cost
function is developed for the evaluation of candidate
indexing choices and applied to the optimization of
index selection. Factors accounted for include file
size, the relative rates of retrieval and maintenance
and the distribution of retrieval and maintenance over
the candidate keys, index structure, and system
charging rates. Among the results demonstrated are the
increased effectiveness of secondary indexes for large
files, the effect of the relative rates of retrieval
and maintenance, the greater cost of allowing for
arbitrarily formulated queries, and the impact on cost
of the use of different index structures.",
acknowledgement = ack-nhfb,
keywords = "access methods; access path; Boolean query; cost
function; data management; database; file design; file
organization; inverted file; inverted index;
maintenance; optimization; retrieval; secondary index;
secondary key; secondary key access",
subject = "Information Systems --- Information Storage and
Retrieval --- Content Analysis and Indexing (H.3.1):
{\bf Indexing methods}; Information Systems ---
Information Storage and Retrieval --- Information
Storage (H.3.2): {\bf File organization}; Information
Systems --- Database Management --- Physical Design
(H.2.2): {\bf Access methods}; Information Systems ---
Database Management (H.2)",
}
@Article{Lorie:1977:PIL,
author = "Raymond A. Lorie",
title = "Physical Integrity in a Large Segmented Database",
journal = j-TODS,
volume = "2",
number = "1",
pages = "91--104",
month = mar,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-1/p91-lorie/p91-lorie.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-1/p91-lorie/",
abstract = "A database system can generally be divided into three
major components. One component supports the logical
database as seen by the user. Another component maps
the information into physical records. The third
component, called the storage component, is responsible
for mapping these records onto auxiliary storage
(generally disks) and controlling their transfer to and
from main storage.\par
This paper is primarily concerned with the
implementation of a storage component. It considers a
simple and classical interface to the storage
component: Seen at this level the database is a
collection of segments. Each segment is a linear
address space.\par
A recovery scheme is first proposed for system failure
(hardware or software error which causes the contents
of main storage to be lost). It is based on maintaining
a dual mapping between pages and their location on
disk. One mapping represents the current state of a
segment being modified; the other represents a previous
backup state. At any time the backup state can be
replaced by the current state without any data merging.
Procedures for segment modification, save, and restore
are analyzed. Another section proposes a facility for
protection against damage to the auxiliary storage
itself. It is shown how such protection can be obtained
by copying on a tape (checkpoint) only those pages that
have been modified since the last checkpoint.",
acknowledgement = ack-nhfb,
keywords = "checkpoint-restart; database; recovery; storage
management",
subject = "Information Systems --- Database Management ---
General (H.2.0): {\bf Security, integrity, and
protection**}; Information Systems --- Information
Storage and Retrieval --- Information Storage (H.3.2);
Information Systems --- Database Management ---
Physical Design (H.2.2): {\bf Recovery and restart}",
}
@Article{Smith:1977:DAA,
author = "John Miles Smith and Diane C. P. Smith",
title = "Database abstractions: Aggregation and
Generalization",
journal = j-TODS,
volume = "2",
number = "2",
pages = "105--133",
month = jun,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; Database/Wiederhold.bib;
Distributed/gesturing.bib;
http://www.acm.org/pubs/toc/; Object/Nierstrasz.bib",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-2/p105-smith/p105-smith.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-2/p105-smith/",
abstract = "Two kinds of abstraction that are fundamentally
important in database design and usage are defined.
Aggregation is an abstraction which turns a
relationship between objects into an aggregate object.
Generalization is an abstraction which turns a class of
objects into a generic object. It is suggested that all
objects (individual, aggregate, generic) should be
given uniform treatment in models of the real world. A
new data type, called generic, is developed as a
primitive for defining such models. Models defined with
this primitive are structured as a set of aggregation
hierarchies intersecting with a set of generalization
hierarchies. Abstract objects occur at the points of
intersection. This high level structure provides a
discipline for the organization of relational
databases. In particular this discipline allows: (i) an
important class of views to be integrated and
maintained; (ii) stability of data and programs under
certain evolutionary changes; (iii) easier
understanding of complex models and more natural {\em
query formulation;\/} (iv) {\em a more systematic
approach to database design;\/} (v) {\em more
optimization\/} to be performed at lower implementation
levels. The generic type is formalized by a set of
invariant properties. These properties should be
satisfied by all relations in a database if
abstractions are to be preserved. A triggering
mechanism for automatically maintaining these
invariants during update operations is proposed. A
simple mapping of aggregation/generalization
hierarchies onto owner-coupled set structures is
given.",
acknowledgement = ack-nhfb,
keywords = "aggregation; data abstraction; data model; data type;
database design; dblit data abstraction;
generalization; integrity constraints; knowledge
representation; relational database",
subject = "Information Systems --- Database Management ---
Logical Design (H.2.1): {\bf Data models}; Information
Systems --- Database Management --- Systems (H.2.4):
{\bf Relational databases}; Software --- Software
Engineering --- Software Architectures (D.2.11): {\bf
Data abstraction}",
}
@Article{Shu:1977:EDE,
author = "N. C. Shu and B. C. Housel and R. W. Taylor and S. P.
Ghosh and V. Y. Lum",
title = "{EXPRESS}: a data {EXtraction, Processing, and
Restructuring System}",
journal = j-TODS,
volume = "2",
number = "2",
pages = "134--174",
month = jun,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-2/p134-shu/p134-shu.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-2/p134-shu/",
abstract = "EXPRESS is an experimental prototype data translation
system which can access a wide variety of data and
restructure it for new uses. The system is driven by
two very high level nonprocedural languages: DEFINE for
data description and CONVERT for data restructuring.
Program generation and cooperating process techniques
are used to achieve efficient operation.\par
This paper describes the design and implementation of
EXPRESS. DEFINE and CONVERT are summarized and the
implementation architecture presented.\par
The DEFINE description is compiled into a customized
PL/1 program for accessing source data. The
restructuring specified in CONVERT is compiled into a
set of customized PL/1 procedures to derive multiple
target files from multiple input files. Job steps and
job control statements are generated automatically.
During execution, the generated procedures run under
control of a process supervisor, which coordinates
buffer management and handles file allocation,
deallocation, and all input/output requests.\par
The architecture of EXPRESS allows efficiency in
execution by avoiding unnecessary secondary storage
references while at the same time allowing the
individual procedures to be independent of each other.
Its modular structure permits the system to be extended
or transferred to another environment easily.",
acknowledgement = ack-nhfb,
keywords = "data conversion; data description languages; data
manipulation languages; data restructuring; data
translation; file conversion; program generation; very
high level languages",
subject = "Information Systems --- Database Management ---
Heterogeneous Databases (H.2.5): {\bf Data
translation**}; Information Systems --- Information
Storage and Retrieval --- Information Storage (H.3.2):
{\bf File organization}; Information Systems ---
Database Management --- Languages (H.2.3)",
}
@Article{Ozkarahan:1977:PER,
author = "E. A. Ozkarahan and S. A. Schuster and K. C. Sevcik",
title = "Performance Evaluation of a Relational Associative
Processor",
journal = j-TODS,
volume = "2",
number = "2",
pages = "175--195",
month = jun,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-2/p175-ozkarahan/p175-ozkarahan.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-2/p175-ozkarahan/",
abstract = "An associative processor called RAP has been designed
to provide hardware support for the use and
manipulation of databases. RAP is particularly suited
for supporting relational databases. In this paper, the
relational operations provided by the RAP hardware are
described, and a representative approach to providing
the same relational operations with conventional
software and hardware is devised. Analytic models are
constructed for RAP and the conventional system. The
execution times of several of the operations are shown
to be vastly improved with RAP for large relations.",
acknowledgement = ack-nhfb,
keywords = "associative processors; database machines; performance
evaluation; RAP hardware support database machine TODS;
relational databases",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases}; Hardware
--- Control Structures and Microprogramming --- Control
Structure Performance Analysis and Design Aids
(B.1.2)",
}
@Article{Brice:1977:EPD,
author = "Richard S. Brice and Stephen W. Sherman",
title = "An Extension on the Performance of a Database Manager
in a Virtual Memory System Using Partially Locked
Virtual Buffers",
journal = j-TODS,
volume = "2",
number = "2",
pages = "196--207",
month = jun,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Database/Graefe.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-2/p196-brice/p196-brice.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-2/p196-brice/",
abstract = "Buffer pools are created and managed in database
systems in order to reduce the total number of accesses
to the I/O devices. In systems using virtual memory,
any reduction in I/O accesses may be accompanied by an
increase in paging. The effects of these factors on
system performance are quantified, where system
performance is a function of page faults and database
accesses to the I/O devices. A previous study of this
phenomenon is extended through the analysis of
empirical data gathered in a multifactor experiment. In
this study memory is partitioned between the program
and the buffer so that the impact of the controlled
factors can be more effectively evaluated. It is
possible to improve system performance through the use
of different paging algorithms in the program partition
and the buffer partition. Also, the effects on system
performance as the virtual buffer size is increased
beyond the real memory allocated to the buffer
partition are investigated.",
acknowledgement = ack-nhfb,
keywords = "buffer manager; database management; double paging;
locked buffer; page faults; page replacement algorithm;
performance; pinning fixing TODS; virtual buffer;
virtual memory",
subject = "Hardware --- Control Structures and Microprogramming
--- Control Structure Performance Analysis and Design
Aids (B.1.2); Information Systems --- Database
Management --- Systems (H.2.4): {\bf Database
Manager}",
}
@Article{Lohman:1977:OPB,
author = "Guy M. Lohman and John A. Muckstadt",
title = "Optimal Policy for Batch Operations: Backup,
Checkpointing, Reorganization, and Updating",
journal = j-TODS,
volume = "2",
number = "3",
pages = "209--222",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p209-lohman/p209-lohman.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p209-lohman/",
abstract = "Many database maintenance operations are performed
periodically in batches, even in realtime systems. The
purpose of this paper is to present a general model for
determining the optimal frequency of these batch
operations. Specifically, optimal backup,
checkpointing, batch updating, and reorganization
policies are derived. The approach used exploits
inventory parallels by seeking the optimal number of
items--rather than a time interval--to trigger a batch.
The Renewal Reward Theorem is used to find the average
long run costs for backup, recovery, and item storage,
per unit time, which is then minimized to find the
optimal backup policy. This approach permits far less
restrictive assumptions about the update arrival
process than did previous models, as well as inclusion
of storage costs for the updates. The optimal
checkpointing, batch updating, and reorganization
policies are shown to be special cases of this optimal
backup policy. The derivation of previous results as
special cases of this model, and an example,
demonstrate the generality of the methodology
developed.",
acknowledgement = ack-nhfb,
classification = "723",
keywords = "backup frequency; batch operations; batch update;
checkpoint interval; data base systems; database
maintenance; file reorganization; inventory theory;
real-time systems; renewal theory",
subject = "Information Systems --- Database Management ---
General (H.2.0)",
}
@Article{Wong:1977:IHT,
author = "Kai C. Wong and Murray Edelberg",
title = "Interval Hierarchies and Their Application to
Predicate Files",
journal = j-TODS,
volume = "2",
number = "3",
pages = "223--232",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p223-wong/p223-wong.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p223-wong/",
abstract = "Predicates are used extensively in modern database
systems for purposes ranging from user specification of
associative accesses to data, to user-invisible system
control functions such as concurrency control and data
distribution. Collections of predicates, or predicate
files, must be maintained and accessed efficiently. A
dynamic index is described, called an interval
hierarchy, which supports several important retrieval
operations on files of simple conjunctive predicates.
Search and maintenance algorithms for interval
hierarchies are given. For a file of n predicates,
typical of the kind expected in practice, these
algorithms require time equal to $O(\log n)$.",
acknowledgement = ack-nhfb,
classification = "723",
keywords = "concurrency control; data base systems; database
system; distributed data; index; interval; predicate
file",
subject = "Software --- Operating Systems --- Storage Management
(D.4.2): {\bf Storage hierarchies}; Information Systems
--- Information Storage and Retrieval --- Information
Storage (H.3.2): {\bf File organization}; Information
Systems --- Database Management --- Systems (H.2.4):
{\bf Distributed databases}; Information Systems ---
Database Management --- Systems (H.2.4): {\bf
Concurrency}; Information Systems --- Information
Storage and Retrieval --- Content Analysis and Indexing
(H.3.1): {\bf Indexing methods}",
}
@Article{Ries:1977:ELG,
author = "Daniel R. Ries and Michael Stonebraker",
title = "Effects of Locking Granularity in a Database
Management System",
journal = j-TODS,
volume = "2",
number = "3",
pages = "233--246",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p233-ries/p233-ries.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p233-ries/",
abstract = "Many database systems guarantee some form of integrity
control upon multiple concurrent updates by some form
of locking. Some ``granule'' of the database is chosen
as the unit which is individually locked, and a lock
management algorithm is used to ensure integrity. Using
a simulation model, this paper explores the desired
size of a granule. Under a wide variety of seemingly
realistic conditions, surprisingly coarse granularity
is called for. The paper concludes with some
implications of these results concerning the viability
of so-called predicate locking.",
acknowledgement = ack-nhfb,
classification = "723",
keywords = "concurrency; consistency; data base systems; database
management; locking granularity; multiple updates;
predicate locks",
subject = "Information Systems --- Database Management ---
Systems (H.2.4); Information Systems --- Database
Management (H.2); Information Systems --- Database
Management --- Systems (H.2.4): {\bf Concurrency}",
}
@Article{Schmidt:1977:SHL,
author = "Joachim W. Schmidt",
title = "Some High Level Language Constructs for Data of Type
Relation",
journal = j-TODS,
volume = "2",
number = "3",
pages = "247--261",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p247-schmidt/p247-schmidt.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p247-schmidt/",
abstract = "For the extension of high level languages by data
types of mode relation, three language constructs are
proposed and discussed: a repetition statement
controlled by relations, predicates as a generalization
of Boolean expressions, and a constructor for relations
using predicates. The language constructs are developed
step by step starting with a set of elementary
operations on relations. They are designed to fit into
PASCAL without introducing too many additional
concepts.",
acknowledgement = ack-nhfb,
annote = "PASCAL/R",
classification = "723",
keywords = "computer programming languages; data type; database;
high level language; language extension; nonprocedural
language; relational calculus; relational model",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases};
Information Systems --- Database Management ---
Languages (H.2.3)",
}
@Article{Fagin:1977:MVD,
author = "Ronald Fagin",
title = "Multi-Valued Dependencies and a New Normal Form for
Relational Databases",
journal = j-TODS,
volume = "2",
number = "3",
pages = "262--278",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; Distributed/gesturing.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p262-fagin/p262-fagin.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p262-fagin/",
abstract = "A new type of dependency, which includes the
well-known functional dependencies as a special case,
is defined for relational databases. By using this
concept, a new (``fourth'') normal form for relation
schemata is defined. This fourth normal form is
strictly stronger than Codd's ``improved third normal
form'' (or ``Boyce-Codd normal form''). It is shown
that every relation schema can be decomposed into a
family of relation schemata in fourth normal form
without loss of information (that is, the original
relation can be obtained from the new relations by
taking joins).",
acknowledgement = ack-nhfb,
annote = "Multivalued dependency is defined for relational
databases, a new (``fourth'') normal form is strictly
stronger than Codd's.",
classification = "723",
keywords = "3NF; 4NF; Boyce-Codd normal form; data base systems;
database design; decomposition; fourth normal form;
functional dependency; multivalued dependency;
normalization; relational database; third normal form",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases};
Information Systems --- Database Management --- Logical
Design (H.2.1): {\bf Normal forms}",
}
@Article{March:1977:DER,
author = "Salvatore T. March and Dennis G. Severance",
title = "The Determination of Efficient Record Segmentations
and Blocking Factors for Shared Data Files",
journal = j-TODS,
volume = "2",
number = "3",
pages = "279--296",
month = sep,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-3/p279-march/p279-march.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-3/p279-march/",
abstract = "It is generally believed that 80 percent of all
retrieval from a commercial database is directed at
only 20 percent of the stored data items. By
partitioning data items into primary and secondary
record segments, storing them in physically separate
files, and judiciously allocating available buffer
space to the two files, it is possible to significantly
reduce the average cost of information retrieval from a
shared database. An analytic model, based upon
knowledge of data item lengths, data access costs, and
user retrieval patterns, is developed to assist an
analyst with this assignment problem. A computationally
tractable design algorithm is presented and results of
its application are described.",
acknowledgement = ack-nhfb,
classification = "723; 901",
keywords = "bicriterion mathematical programs; branch and bound;
buffer allocation; data base systems; data management;
information science --- information retrieval; network
flows; record design; record segmentation",
subject = "Information Systems --- Database Management (H.2);
Information Systems --- Information Storage and
Retrieval --- Information Storage (H.3.2): {\bf File
organization}",
}
@Article{Ozkarahan:1977:AAF,
author = "E. A. Ozkarahan and K. C. Sevcik",
title = "Analysis of Architectural Features for Enhancing the
Performance of a Database Machine",
journal = j-TODS,
volume = "2",
number = "4",
pages = "297--316",
month = dec,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-4/p297-ozkarahan/p297-ozkarahan.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-4/p297-ozkarahan/",
abstract = "RAP (Relational Associative Processor) is a
``back-end'' database processor that is intended to
take over much of the effort of database management in
a computer system. In order to enhance RAP's
performance its design includes mechanisms for
permitting features analogous to multiprogramming and
virtual memory as in general purpose computer systems.
It is the purpose of this paper to present the detailed
design of these mechanisms, along with some analysis
that supports their value. Specifically, (1) the
response time provided by RAP under several scheduling
disciplines involving priority by class is analyzed,
(2) the cost effectiveness of the additional hardware
in RAP necessary to support multiprogramming is
assessed, and (3) a detailed design of the RAP virtual
memory system and its monitor is presented.",
acknowledgement = ack-nhfb,
annote = "RAP (Relational Associative Processor) is a ``back-end
database processor''; its design includes mechanisms
for multiprogramming and virtual memory.",
classification = "722; 723",
keywords = "associative processors; computer architecture;
computer architecture, hardware support TODS; data base
systems; database machines; database management",
subject = "Information Systems --- Database Management (H.2)",
}
@Article{Rissanen:1977:ICR,
author = "Jorma Rissanen",
title = "Independent Components of Relations",
journal = j-TODS,
volume = "2",
number = "4",
pages = "317--325",
month = dec,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-4/p317-rissanen/p317-rissanen.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-4/p317-rissanen/",
abstract = "In a multiattribute relation or, equivalently, a
multicolumn table a certain collection of the
projections can be shown to be independent in much the
same way as the factors in a Cartesian product or
orthogonal components of a vector. A precise notion of
independence for relations is defined and studied. The
main result states that the operator which reconstructs
the original relation from its independent components
is the natural join, and that independent components
split the full family of functional dependencies into
corresponding component families. These give an
easy-to-check criterion for independence.",
acknowledgement = ack-nhfb,
annote = "In a multi-attribute relation a certain collection of
projections can be shown to be independent. The
operator which reconstructs the original relation is
the natural join. Independent components split the full
family of functional dependencies into corresponding
component families.",
classification = "723",
keywords = "data base systems; database; functional dependencies;
relations",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Relational databases}",
}
@Article{Bonczek:1977:TGB,
author = "Robert H. Bonczek and James I. Cash and Andrew B.
Whinston",
title = "A Transformational Grammar-Based Query Processor for
Access Control in a Planning System",
journal = j-TODS,
volume = "2",
number = "4",
pages = "326--338",
month = dec,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-4/p326-bonczek/p326-bonczek.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-4/p326-bonczek/",
abstract = "Providing computer facilities and data availability to
larger numbers of users generates increased system
vulnerability which is partially offset by software
security systems. Much too often these systems are
presented as ad hoc additions to the basic data
management system. One very important constituent of
software security systems is the access control
mechanism which may be the last resource available to
prohibit unauthorized data retrieval. This paper
presents a specification for an access control
mechanism. The mechanism is specified in a context for
use with the GPLAN decision support system by a
theoretical description consistent with the formal
definition of GPLAN's query language. Incorporation of
the mechanism into the language guarantees it will not
be an ad hoc addition. Furthermore, it provides a
facile introduction of data security dictates into the
language processor.",
acknowledgement = ack-nhfb,
classification = "723",
keywords = "access control; data processing; data security;
database; decision support system; planning system",
subject = "Information Systems --- Database Management ---
Systems (H.2.4): {\bf Query processing}; Information
Systems --- Database Management --- General (H.2.0):
{\bf Security, integrity, and protection**};
Information Systems --- Database Management ---
Physical Design (H.2.2): {\bf Access methods}",
}
@Article{Lang:1977:DBP,
author = "Tom{\'a}s Lang and Christopher Wood and Eduardo B.
Fern{\'a}ndez",
title = "Database Buffer Paging in Virtual Storage Systems",
journal = j-TODS,
volume = "2",
number = "4",
pages = "339--351",
month = dec,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-4/p339-lang/p339-lang.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-4/p339-lang/",
abstract = "Three models, corresponding to different sets of
assumptions, are analyzed to study the behavior of a
database buffer in a paging environment. The models
correspond to practical situations and vary in their
search strategies and replacement algorithms. The
variation of I/O cost with respect to buffer size is
determined for the three models. The analysis is valid
for arbitrary database and buffer sizes, and the I/O
cost is obtained in terms of the miss ratio, the buffer
size, the number of main memory pages available for the
buffer, and the relative buffer and database access
costs.",
acknowledgement = ack-nhfb,
annote = "The variation of I/O cost with respect to buffer size
is determined for three models: the IMS/360 database
buffer, with LRU memory replacement, and a prefix table
in main memory indicating which database pages are in
the VSAM buffer.",
classification = "723",
keywords = "buffer management; computer systems performance; data
base systems; database performance; page replacement
algorithm; virtual memory",
subject = "Information Systems --- Database Management ---
General (H.2.0); Information Systems --- Database
Management --- Systems (H.2.4)",
}
@Article{Thomas:1977:VAP,
author = "D. A. Thomas and B. Pagurek and R. J. Buhr",
title = "Validation Algorithms for Pointer Values in {DBTG}
Databases",
journal = j-TODS,
volume = "2",
number = "4",
pages = "352--369",
month = dec,
year = "1977",
CODEN = "ATDSD3",
ISSN = "0362-5915",
bibdate = "Sat Apr 14 10:34:48 MDT 2001",
bibsource = "Compendex database; Database/Graefe.bib;
Database/Wiederhold.bib; http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org/pubs/articles/journals/tods/1977-2-4/p352-thomas/p352-thomas.pdf;
http://www.acm.org/pubs/citations/journals/tods/1977-2-4/p352-thomas/",
abstract = "This paper develops algorithms for verifying pointer
values in DBTG (Data Base Task Group) type databases.
To validate pointer implemented access paths and set
structures, two algorithms are developed. The first
procedure exploits the ``typed pointer'' concept
employed in modern programming languages to diagnose
abnormalities in directories and set instances. The
second algorithm completes pointer validation by
examining set instances to ensure that each DBTG set
has a unique owner. Sequential processing is used by
both algorithms, allowing a straightforward
implementation which is efficient in both time and
space. As presented, the algorithms are independent of
implementation schema and physical structure.",
acknowledgement = ack-nhfb,
annote = "Type Checking algorithm detects and locates errors in
the pointers which are used to represent chained and
pointer array implemented sets. In addition to invalid
set