Sort sets in the relational model

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 separator, is given and then used to study the relationship between order and sort-set dependencies.

REFERENCES

• 1: ARMSTRONG, W.W. Dependency structures of database relationships. In Proceedings of the IFIP 74. North-Holland, Amsterdam, 1974, pp. 580-583.
• 2: Paolo Atzeni , Nicola M. Morfuni, Functional Dependencies and Disjunctive Existence Constraints in Database Relations with Null Values, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.69-81, July 16-20, 1984
• 3: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 4: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 5: CASANOVA, M. A., FAGIN~ R., AND PAPADIMITRIOU, C. H. Inclusion dependencies and their interaction with functional dependencies. J. Comput. Syst. Sci. 28, l (1984), 29-59.
• 6: CODD, E. F., AND DATE, C. J. The relational and network approaches: Comparison of the application programming interfaces. Tech. Rep. RJ 1401 (#21706). IBM, San Jose, Calif., June 1974.
• 7: CODD, E. F., AND DATE, C. J. Interactive support for non-programmers: The relational and network approaches. Tech. Rep. RJ 1400 (#21638). IBM, San Jose, Calif., June 1974.
• 8: Jirun Dong , Richard Hull, Applying approximate order dependency to reduce indexing space, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582375]
• 9: FAGIN, R. Functional dependencies in a relational database and propositional logic. IBM J. Res. Develop. 21, 6 (Nov. 1977), 534-544.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: GINSBURG, S., AND HULL, R. Order dependency in the relational model. Theoret. Comput. Sci. 26 (1983), 149-195.
• 12: Seymour Ginsburg , Sami Mohammed Zaiddan, Properties of functional-dependency families, Journal of the ACM (JACM), v.29 n.3, p.678-698, July 1982 [doi>10.1145/322326.322331]
• 13: D. Stott Parker, Jr. , Kamran Parsaye-Ghomi, Inferences involving embedded multivalued dependencies and transitive dependencies, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582259]
• 14: Yehoshua Sagiv , Scott F. Walecka, Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies, Journal of the ACM (JACM), v.29 n.1, p.103-117, Jan. 1982 [doi>10.1145/322290.322297]
• 15: Dionysios C. Tsichritzis , Frederick H. Lochovsky, Data Models, Prentice Hall Professional Technical Reference, 1982
• 16: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 17: YANNAKA~IS, M., AND PAPADIMITRIOU, C.H. Algebraic dependencies. J. Comput. Syst. Sci. 25 (1982), 2-41.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Design, Management, Performance, Theory, Verification