yet tractable XML keys

Constraints are important for a variety of XML recommen-dations and applications. Consequently, there are numerous opportunities for advancing the treatment of XML seman-tics. In particular, suitable notions of keys will enhance XML’s capabilities of modeling, managing and processing native XML data. However, the different ways of access-ing and comparing XML elements make it challenging to balance expressiveness and tractability. We investigate XML keys which uniquely identify XML elements based on a very general notion of value-equality: isomorphic subtrees with the identity on data values. Pre-viously, an XML key fragment has been recognised that is robust in the sense that its implication problem can be ex-pressed as the reachability problem in a suitable digraph. We analyse the impact of extending this fragment by struc-tural keys that uniquely identify XML elements indepen-dently of any data. We establish a sound and complete set of inference rules for this expressive fragment of XML keys, and encode these rules in an algorithm that decides the as-sociated implication problem in time quadratic in the size of the input keys. Consequently, we gain significant expres-siveness without any loss of efficiency in comparison to less expressive XML key fragments. 1