********************************************************************
Seminar
Department
of Systems Engineering and Engineering Management
The Chinese
------------------------------------------------------------------------------------------
|
|
|
|
|
Title |
: |
Cardinality Constraints
for XML Data Trees: Algorithms and Complexity |
|
|
|
|
|
Speaker |
: |
Prof. Sven Hartmann |
|
|
|
Department of Information Systems |
|
|
|
|
|
|
|
|
|
Date |
: |
July 6th, 2007 (Friday) |
|
|
|
|
|
Time |
: |
4:30 p.m. - 5:30 p.m. |
|
|
|
|
|
Venue |
: |
Room 513 |
|
|
|
William M.W. Mong Engineering Building |
|
|
|
(Engineering Building Complex Phase 2) |
|
|
|
CUHK |
|
|
|
|
------------------------------------------------------------------------------------------
Abstract:
|
Integrity constraints play an important role in database
design: They enhance the semantic capabilities of a data model in the sense
that they permit only those databases that are considered meaningful for the
application at hand. Recently, integrity constraints for XML data gained much
attention. Surprisingly, choosing suitable definitions for XML integrity
constraints is not trivial. Due to the intricate tree-like structure of XML
data, decision problems in database practice turn out to be intractable for
many constraint classes. It remains a major challenge to find classes of XML
integrity constraints that can be efficiently reasoned about and are still
expressive enough to capture interesting properties. In our presentation we
introduce cardinality constraints that restrict the number of nodes within
subtrees of an XML data tree that contain specific value-equal subnodes. We demonstrate the applicability of these
constraints in optimising XML queries and
predicting the number of XML query answers, updates and encryptions. We
address decision problems for XML cardinality constraints and show the coNP-hardness of the implication problem. On the other
hand, we identify numerical key constraints as an expressive, yet
"well-behaved" class of cardinality constraints. Using methods from
combinatorial optimisation we present an efficient
algorithm for deciding the implication problem for these constraints. Due to
its low time complexity, our algorithm is of interest for XML key constraints,
too. |
-------------------------------------------------------------------------------------------
Biography:
|
Sven Hartmann is Professor of Information Systems at |
************************* ALL ARE WELCOME ************************
|
|
|
|
|
Host |
: |
Prof. Jeffrey Xu Yu |
|
Tel |
: |
(852) 2609-8309 |
|
Email |
: |
|
|
|
|
|
|
Enquiries |
: |
Bolin Ding or Jeffrey Xu Yu |
|
|
: |
Department of Systems Engineering and Engineering
Management |
|
|
|
CUHK |
|
Website |
: |
|
|
Email |
: |
|
|
|
|
|
********************************************************************