Reasoning about Nested Functional Dependencies

Summary: Introduce NFDs: functional dependencies over nested relations using path expressions to capture intra-/inter-set constraints not expressible by classical FDs/MVDs/JDs. Provide logical semantics, a sound & complete eight-rule axiomatization and analysis of empty-set effects for reasoning about complex-type data-warehouse constraints. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1163
Venue: PODS
Year: 1999
Pagerank: 6.6686357e-05
Overall Rank: 4,487 | 69.22%
DOI: 10.1145/303976.303985

Incoming Non-self Citations Over Time

Authors

1. Carmem S. Hara (Federal University of Parana; University of Pennsylvania)
2. Susan B. Davidson (University of Pennsylvania)

BibTeX Citation

@inproceedings{hara_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Reasoning about Nested Functional Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/303976.303985},
        doi = {10.1145/303976.303985},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hara, Carmem S. and Davidson, Susan B.},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
4,167	Integrity Constraints for XML	2000	PODS	6.8578387e-05
8,972	CRIUS: User-Friendly Database Design	2011	VLDB	5.3414676e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
1,056	A Normal Form for Nested Relations	1985	PODS	0.00012388199
3,308	Path Constraints on Semistructured and Structured Data	1998	PODS	7.5381026e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,529	First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies	1978	SIGMOD
2	8,552	Multi-valued Dependencies in the Presence of Lists	2004	PODS
3	203	Dependency Inference	1987	VLDB
4	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
5	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
6	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
7	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
8	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
9	3,461	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
10	495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD