The purpose of this paper is to introduce the notions of sort sets and sort set dependencies and to present certain fundamental results regarding them. Essentially, a set of attributes representing totally ordered domains is a sort set for an instance of a relation if that instance can be sorted simultaneously on those attributes; in this case, we also say that the instance satisfies the sort-set dependency defined by those attributes.

The motivation presented for this type of dependency is not to avoid kinds of anomalies, as is the case with other types of dependencies. Here the primary reason for interest in sort-set dependencies, as illustrated in some examples, stems from the possibilities they afford for enhancing performance of a relational database.

The subject and style in this paper are in the spirit of the authors’ earlier one [1], which describes order dependencies. These were generalizations of functional dependencies; rather than insisting on equality of tuple components, as is the case with functional dependencies, order dependencies insist on specified order relationships (for example, >) to hold. Many of the results in the current paper either relate sort-set dependencies to order dependencies, or prove whether or not sort-set dependencies enjoy certain analogous properties to order dependencies.

One example of the former type of result is contained in the third section of this paper; here, a correspondence is shown between eligible sort sets of an order-dependency schema and cliques of a simple graph induced by that schema. A related result in the same section is the co-NP-completeness of determining this property.

In the fourth (and last) section of this paper, the authors present many results of the latter type. In particular, they exhibit a finite, sound, complete set of inference rules for sort-set dependencies; but they later prove that no such set exists for sets which include both sort-set and functional dependencies. Finally, existence of Armstrong relations, separators, and a further generalization called “weak separators” are examined for the various types of dependencies.

The style of the paper is abstract, with theorems carefully stated and proved. There are, however, comments, previews, and summaries of the results which help put them into perspective.