Welcome to BIG !


Dr. Sebastian Link will give a talk about his research topic. Everybody is welcome.
Sebastian Link (Victoria University of Wellington)
Reasoning about XML constraints
- This talk is based on one paper to be published in ACM Trans. Database Systems in June 2009, and one paper accepted to Information and Computation.
Time and Date
3pm, Monday, June 22.
Seminar Room 1 (rm2006) (20th floor), NII.

Constraints are important for a variety of XML recommendations and applications. Consequently, there are numerous opportunities for advancing the treatment of XML semantics. In particular, suitable notions of keys will enhance XML's capabilities of modeling, managing and processing native XML data. However, the different ways of accessing and comparing XML elements make it challenging to balance expressiveness and tractability.

In this talk, I will survey different notions of XML keys and their associated computational properties. A class of XML keys will be identified that is expressive and can be reasoned about efficiently. The class is robust in the sense that its associated implication problem can be characterized by the reachability problem of two fixed nodes in a suitable digraph. This yields a compact algorithm that decides XML key implication in time quadratic in the size of the input. Subsequently, it will be shown how this class can be made more expressive without loss of efficiency. Finally, the border to intractability is drawn by identifying some classes of XML constraints that subsume XML keys and whose associated implication problem is coNP-hard.

Contact Information
Hiroyuki Kato (+81-34212-2589)