### Sort sets in the relational modelSort sets in the relational model

Access Restriction
Subscribed

 Author Ginsburg, Seymour ♦ Hull, Richard Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1986 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The notion of sort set is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning complexity, Armstrong relations, and cliques of certain graphs. Sort-set dependencies are then introduced. A (finite) sound and complete set of inference rules for sort-set dependencies is presented, as well as a proof that there is no such set for functional and sort-set dependencies taken together. Deciding logical implication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP-complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation. A natural generalization of Armstrong relation, here called $\textit{separator},$ is given and then used to study the relationship between order and sort-set dependencies. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1986-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 33 Issue Number 3 Page Count 24 Starting Page 465 Ending Page 488

#### Open content in new tab

Source: ACM Digital Library