Using tree patterns for flexible handling of XML keys : submitted in partial fulfillment of the requirements for the degree of Master of Science at Massey University, Palmerston North, New Zealand

Abstract

Previous research shows that decision problem of XML keys is far more intricate than its relational counterpart. We review key constraints in the context of XML as introduced by Buneman et al [9, 10] and later refined by Hartmann et al [19, 20]. In this thesis we investigate three path expression languages for defining XML keys. They are path expression PƐ, XPath expression XƐ and tree pattern TP. We focus on a special tree pattern TP called safe tree pattern, denoted by SP, which has been proved to be equivalent to XML keys where Q are in XƐǀ,ǁ, Q¹ are in XPǀ,ǁ and Pₗ,..., Pₖ are in XƐǀ,*. We propose a set of inference rules that is sound and complete for the implication of XML keys in the form of SP. Our new containment result of SP is in PTIME. This result indicates a PTIME algorithm for deciding XML key implication, and shows that reasoning about XML key in SP is practically efficient.