The implication problem for ‘closest node’ functional dependencies in complete XML documents

• Published in: Journal of computer and system sciences 2012-07, Vol.78 (4), p.1045-1098
• Main Authors: Vincent, M.W., Liu, J., Mohania, M.
• Format: Article
• Language: English
• Subjects: Algorithms; Axiom system; Axioms; Data integration; Design engineering; DTD; Extensible Markup Language; Functional dependency; Implication; Relational data bases; Sound; XML
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2012.01.003

With the growing use of XML as a format for the permanent storage of data, the study of functional dependencies in XML (XFDs) is of fundamental importance in a number of areas such as understanding how to effectively design XML databases without redundancy or update problems, and data integration. In this article we investigate a particular type of XFD, called a weak ‘closest node’ XFD, that has been shown to extend the classical notion of a functional dependency in relational databases. More specifically, we investigate the implication problem for weak ‘closest node’ XFDs in the context of XML documents with no missing information. The implication problem is the most important one in dependency theory, and is the problem of determining if a set of dependencies logically implies another dependency. Our first, and main, contribution is to provide an axiom system for XFD implication. We prove that our axiom system is both sound and complete, and we then use this result to develop a sound and complete quadratic time closure algorithm for XFD implication. Our second contribution is to investigate the implication problem for XFDs in the presence of a Document Type Definition (DTD). We show that for a class of DTDs called structured DTDs, the implication problem for a set of XFDs and a structured DTD can be converted to the implication problem for a set of XFDs alone, and so is axiomatizable and efficiently solvable by the first contribution. We do this by augmenting the original set of XFDs with additional XFDs generated from the structure of the DTD. ► We study the implication problem for ‘closest node’ XML functional dependencies. ► This type of constraint extends the notion of a relational functional dependency. ► The class of XML documents considered are those with no missing information. ► A sound and complete axiom set and an efficient algorithm for implication is given. ► The case where a structured DTD is present is also shown to be axiomatizable.