Tuple sequences and indexes. (English) Zbl 0554.68070

Abiteboul, Serge; Ginsburg, Seymour

Automata, languages and programming, 11th Colloq., Antwerp/Belg. 1984, Lect. Notes Comput. Sci. 172, 41-50 (1984).

[For the entire collection see Zbl 0543.00014.]
The concept of tuple sequence is introduced in order to investigate structure connected with relational model implementation. Well-known problems like decomposition and duplicates are addressed for tuple sequences. The lexicographical ordering of tuple sequences is studied via the notion of index (dependency). Certain properties of index families are shown, and two algorithmic questions related to indexes considered. Also, a sound and complete set of inference rules for indexes is exhibited. Finally, indexes and functional dependencies in combination are studied.

MSC:

68P20

Information storage and retrieval of data

Keywords:

relational model; lexicographical ordering; index families; inference rules for indexes; functional dependencies

Citations:

Zbl 0543.00014