Tuple sequences and lexicographic indexes
Serge Abiteboul, Seymour Ginsburg · Journal of the ACM · 1986
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.