Partition Semantics for Relations

Summary: Introduce partition semantics for relations, defining partition dependencies (PDs) via the product/sum duality of partitions, generalizing FDs and able to express both functional determination and transitive closure. Characterize PD inference as the uniform word problem in a lattice, give polynomial-time inference and consistency algorithms, and relate PDs to variants of the weak-instance assumption. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h6c9af4dbcaddd8e3
Venue: PODS
Year: 1985
Pagerank: 0.00011452588
Overall Rank: 1,223 | 91.78%
DOI: 10.1145/325405.325452

Incoming Non-self Citations Over Time

Authors

1. Stavros S. Cosmadakis (Massachusetts Institute of Technology)
2. Paris C. Kanellakis (Brown University; Massachusetts Institute of Technology)
3. Nicolas Spyratos (University of Paris)

BibTeX Citation

@inproceedings{cosmadakis_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{Partition Semantics for Relations}},
        url = {https://dl.acm.org/doi/10.1145/325405.325452},
        doi = {10.1145/325405.325452},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cosmadakis, Stavros S. and Kanellakis, Paris C. and Spyratos, Nicolas},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0893712e-05
5,388	Explaining Repaired Data with CFDs	2018	VLDB	6.151535e-05
8,203	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3786539e-05
8,467	Implementing Queries and Updates on Universal Scheme Interfaces	1988	VLDB	5.3350162e-05
9,958	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	5.1038322e-05
13,422	Updating Databases in the Weak Instance Model	1989	PODS	4.9793485e-05
13,441	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD	4.9793485e-05
13,463	A New Basis for the Weak Instance Model	1987	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS
2	7,243	Discovering Graph Functional Dependencies	2018	SIGMOD
3	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
4	3,026	Functional Dependencies for Graphs	2016	SIGMOD
5	13,445	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD
6	13,435	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS
7	209	Dependency Inference	1987	VLDB
8	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
9	8,467	Implementing Queries and Updates on Universal Scheme Interfaces	1988	VLDB
10	13,441	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD