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: 742
Venue: PODS
Year: 1985
Pagerank: 0.00011633715
Overall Rank: 1,216 | 91.66%
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
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.2736086e-05
5,312	Explaining Repaired Data with CFDs	2018	VLDB	6.2698779e-05
8,299	Implementing Queries and Updates on Universal Scheme Interfaces	1988	VLDB	5.4574671e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05
9,780	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	5.2209769e-05
13,132	Updating Databases in the Weak Instance Model	1989	PODS	5.093636e-05
13,151	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD	5.093636e-05
13,173	A New Basis for the Weak Instance Model	1987	PODS	5.093636e-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	7,099	Discovering Graph Functional Dependencies	2018	SIGMOD
2	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
3	2,973	Functional Dependencies for Graphs	2016	SIGMOD
4	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	13,155	A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies	1988	SIGMOD
6	13,145	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS
7	203	Dependency Inference	1987	VLDB
8	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
9	13,151	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD
10	8,299	Implementing Queries and Updates on Universal Scheme Interfaces	1988	VLDB