ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Sort Sets in the Relational Model.

Seymour Ginsburg, Richard Hull: Sort Sets in the Relational Model. PODS 1983: 332-339
@inproceedings{DBLP:conf/pods/GinsburgH83,
  author    = {Seymour Ginsburg and
               Richard Hull},
  title     = {Sort Sets in the Relational Model},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {332-339},
  ee        = {http://doi.acm.org/10.1145/588058.588098, db/conf/pods/GinsburgH83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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, but 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.

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Seymour Ginsburg, Richard Hull: Sort sets in the relational model. J. ACM 33(3): 465-488(1986) BibTeX

References

[A]
...
[BB]
Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[BFH]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[CFP]
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176 BibTeX
[CD1]
C. J. Date, E. F. Codd: The Relational and Network Approaches: Comparison of the Application Programming Interfaces. SIGMOD Workshop, Vol. 2 1974: 83-113 BibTeX
[CD2]
E. F. Codd, C. J. Date: Interactive Support For Non-Programmers: The Relational and Network Approaches. SIGMOD Workshop, Vol. 2 1974: 11-41 BibTeX
[DH]
Jirun Dong, Richard Hull: Applying Approximate Order Dependency to Reduce Indexing Space. SIGMOD Conference 1982: 119-127 BibTeX
[F]
...
[GJ]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[GH1]
Seymour Ginsburg, Richard Hull: Order Dependency in the Relational Model. Theor. Comput. Sci. 26: 149-195(1983) BibTeX
[GH2]
Seymour Ginsburg, Richard Hull: Sort sets in the relational model. J. ACM 33(3): 465-488(1986) BibTeX
[GZ]
Seymour Ginsburg, Sami Mohammed Zaiddan: Properties of functional-dependency families. J. ACM 29(3): 678-698(1982) BibTeX
[PP]
Douglas Stott Parker Jr., Kamran Parsaye-Ghomi: Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies. SIGMOD Conference 1980: 52-57 BibTeX
[SW]
Yehoshua Sagiv, Scott F. Walecka: Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies. J. ACM 29(1): 103-117(1982) BibTeX
[TL]
...
[U]
...
[YP]
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:43 2009