Tuple sequences and lexicographic indexes
Authors:
Open Access
- 1 May 1986
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 33 (3) , 409-422
Abstract
The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem for tuple sequences is considered. The lexicographical ordering of tuple sequences is studied via the notion of (lexicographic) index. A sound and complete set of inference rules for indexes is exhibited, and two algorithmic questions related to indexes examined. Finally, indexes and functional dependencies in combination are studied.Keywords
This publication has 8 references indexed in Scilit:
- Algebraic dependenciesJournal of Computer and System Sciences, 1982
- An extended relational algebra with control over duplicate elimination1982
- The functional data model and the data languages DAPLEXACM Transactions on Database Systems, 1981
- Functional Dependencies in a Relational Database and Propositional LogicIBM Journal of Research and Development, 1977
- A complete axiomatization for functional and multivalued dependencies in database relations1977
- The design and implementation of INGRESACM Transactions on Database Systems, 1976
- System RACM Transactions on Database Systems, 1976
- Reducibility among Combinatorial Problems1972