Functional dependencies over XML documents with DTDs

  • Sven Hartmann
  • Sebastian Link
  • Klaus-Dieter Schewe


In this article an axiomatisation for functional dependencies over XML documents is presented. The approach is based on a representation of XML document type definitions (or XML schemata) by nested attributes using constructors for records, disjoint unions and lists, and a particular null value, which covers optionality. Infinite structures that may result from referencing attributes in XML are captured by rational trees. Using a partial order on nested attributes we obtain non-distributive Brouwer algebras. The operations of the Brouwer algebra are exploited in the soundness and completeness proofs for derivation rules for functional dependencies.


Download data is not yet available.
How to Cite
Hartmann, S., Link, S., & Schewe, K.-D. (2005). Functional dependencies over XML documents with DTDs. Acta Cybernetica, 17(1), 153-171. Retrieved from
Regular articles