Sort Sets in the Relational Model* (extended abstract)

Summary: Introduce 'sort set' to formalize simultaneous ordering of multiple attributes; characterize when order dependencies imply sort sets and exploit them for implementation/optimization. Give finite complete axioms for sort-set dependencies (implication polytime; with FDs co-NP-complete) and define 'separators' generalizing Armstrong relations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 669
Venue: PODS
Year: 1983
Pagerank: 5.695798e-05
Overall Rank: 7,126 | 51.11%
DOI: 10.1145/588058.588098

Incoming Non-self Citations Over Time

Authors

1. Seymour Ginsburg (University of Southern California)
2. Richard Hull (University of Southern California)

BibTeX Citation

@inproceedings{ginsburg_pods83,
        address = {New York, NY, USA},
        series = {{PODS} '83},
        title = {{Sort Sets in the Relational Model* (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/588058.588098},
        doi = {10.1145/588058.588098},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ginsburg, Seymour and Hull, Richard},
        year = {1983}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,842	Sequential Dependencies	2009	VLDB	9.6345922e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD	0.00017513721
3,763	Applying Approximate Order Dependency to Reduce Indexing Space	1982	SIGMOD	7.144792e-05
6,505	Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies	1980	SIGMOD	5.8583679e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
2	7,732	On the complexity of division and set joins in the relational algebra	2005	PODS
3	13,145	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS
4	3,763	Applying Approximate Order Dependency to Reduce Indexing Space	1982	SIGMOD
5	203	Dependency Inference	1987	VLDB
6	4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB
7	589	On The Semantics Of The Relational Data Model	1975	SIGMOD
8	6,114	Fundamentals of Order Dependencies	2012	VLDB
9	6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB
10	14,469	SMALL ARMSTRONG RELATIONS FOR DATABASE DESIGN (Extended abstract)	1985	PODS