The Implication Problem Of XML Polymorphism Dependency

XML defines a kind of data format, allowing users to define customized XML tag to describe data from a certain field. XML document uses XML language to describe and store data, it is simple, platform-independent, easy to understand and process by machine, all of those advantage makes XML suitable to describe data transformed and shared through internet. Thus, XML becomes a standard adviced by W3 C organization.Similar to relational data, functional depandecy also exists in XML documents, but there are some difference between them. Relational data is horizontal structural while XML shows a hierarchical structure between data which could be viewed as the organizational structure of data. It is easy to find that data dependency not only exists in the value of data, also exists in the organizational structure of data, we name this kind of data dependency as XML polymorphism dependency, XPD for short. XPD can also results in data redundancy.XPD can descible data dependency related to both the value of data and the organizational structure of data. Compared to exised XML functional dependency definations, XPD has a more capable descriptive power, thus XPD is a more general definition of data dependency. In consideration of the important role which functional dependency plays in the relational database normalization theory, research about XPD is important for the XML database normalization theory.This paper analyzes the implication problem of XPD, proposes inference rules of XPD and develops an algorithm which can resolve the implication problem of XPD.We also discuss the interaction between DTD and XPD, finding that some DTD results in the non- axiomatization of XPD.