Using Transversals for Discovering XML Functional Dependencies

Dependency discovery is an important technique for relational database design due to numerous applications like normalisation and query optimisation. Similar applications are likely to exist in the context of XML. To date, there are few investigations into dependency discovery in the context of XML. We propose a transversal approach for discovering a class of subgraph-based XML functional dependencies with pre-image semantics (XFDs). We cover all aspects of the discovery process, from determining agree sets to the extraction of an XFD cover. An inherent challenge is the large and complex search space of valid XFDs due to the tree-structure of XML data.