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
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