Sort sets in the relational model
Authors:
Open Access
- 1 May 1986
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 33 (3) , 465-488
Abstract
The notion ofsort setis 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 calledseparator, is given and then used to study the relationship between order and sort-set dependencies.Keywords
This publication has 8 references indexed in Scilit:
- Inclusion dependencies and their interaction with functional dependenciesJournal of Computer and System Sciences, 1984
- Functional dependencies and disjunctive existence constraints in database relations with null valuesLecture Notes in Computer Science, 1984
- Order dependency in the relational modelTheoretical Computer Science, 1983
- Algebraic dependenciesJournal of Computer and System Sciences, 1982
- Properties of functional-dependency familiesJournal of the ACM, 1982
- Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued DependenciesJournal of the ACM, 1982
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979
- Functional Dependencies in a Relational Database and Propositional LogicIBM Journal of Research and Development, 1977