Unlocking keys for XML trees
Speaker: Dr Sebastian Link, Massey University
When: 2006-08-31 11:00:00
Venue: 78-420
Host: Dr Guido Governatori
Abstract:The eXtensible markup language (XML) has recently evolved to the
standard for data exchange on the Web, and also represents a uniform
model for data integration. It provides a high degree of syntactic
flexibility but has little to offer to specify the semantics of its
data. Consequently, the study of integrity constraints has been
recognised as one of the most important yet challenging areas of XML
research.
In this talk I will review key constraints in the context of XML as
introduced by Buneman et al [1,2]. It turns out that one of the
proposed inference rules is not sound in general, and the
axiomatisation proposed for XML keys [2] is incomplete even if key
paths are simple. Therefore, the axiomatisation and also the
implication problem for XML keys are still open.
I will then present a set of inference rules that is indeed sound
and complete for the implication of XML keys with simple key
paths. The technique for proving completeness enables one to
characterise XML key implication in terms of the reachability
problem of vertices in digraphs. This results in a quadratic time
algorithm for deciding XML key implication, and shows that reasoning
for XML keys is practically efficient.
Finally, a new class of XML constraints is introduced that subsumes
keys. I will briefly sketch how to extend the axiomatisation and
solution to the implication problem from keys to this broader class.
[1] Buneman, Davidson, Fan, Hara, Tan. Keys for XML. Computer Networks
39(5):473-487. 2002
[2] Buneman, Davidson, Fan, Hara, Tan. Reasoning about keys for XML.
Information Systems 28(8):1037-1063. 2003
Biography:(biography unavailable)
Type: DKE
Contact:Dr Guido Governatori, seminar host (guido@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)