Multi-valued Dependencies in the Presence of Lists

Summary: Axiomatizes multi-valued dependencies for nested list-typed data via an abstract nested-attribute/co-Heyting algebra, characterizing satisfaction as lossless decomposition. Gives sound and complete finite-implication rules, introduces a new list-specific inference rule and studies rule minimality. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1334
Venue: PODS
Year: 2004
Pagerank: 5.4119882e-05
Overall Rank: 8,552 | 41.33%
DOI: 10.1145/1055558.1055603

Incoming Non-self Citations Over Time

Authors

1. Sven Hartmann (Information Science Research Centre; Massey University)
2. Sebastian Link (Information Science Research Centre; Massey University)

BibTeX Citation

@inproceedings{hartmann_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Multi-valued Dependencies in the Presence of Lists}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055603},
        doi = {10.1145/1055558.1055603},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hartmann, Sven and Link, Sebastian},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,726	Differential Constraints	2005	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	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
2	13,259	A Theory Of Data Dependencies Over Relational Expressions	1982	PODS
3	1,056	A Normal Form for Nested Relations	1985	PODS
4	2,529	REAL-WORLD MVD's	1981	SIGMOD
5	13,192	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS
6	4,487	Reasoning about Nested Functional Dependencies	1999	PODS
7	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
8	6,505	Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies	1980	SIGMOD
9	6,478	Weak Multivalued Dependencies+	1984	PODS
10	495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD