Date and time: 11.30am - 12.30pm, Friday 22th January, 2010
Venue: Floor 8, Building 14 (IS Common Area)
Abstract:
Constraints can restrict the possible instances of a database system
to
those considered meaningful for the underlying application domain.
Therefore, they are fundamental to database design, efficient update
processing and semantic query optimization. While research on this
topic has been extensive, currently existing theories of database
constraints apply to only a small number of instances that occur in
real database systems.
In this talk we will develop a theory that i) applies to real-world
instances as permitted by SQL (the data definition and query language
standard), ii) subsumes several existing orthogonal theories, and iii)
results in efficient tools for effective constraint and database
management. Specifically, we axiomatize the implication of a large
class of database constraints, and establish almost linear-time
algorithms that decide whether a database constraint is implied by a
given set of constraints. Furthermore, we show that the
implication of
several classes of constraints corresponds exactly to the logical
implication of a number of para-consistent logic fragments, including
Graham Priest's well-known Logic of Paradox. These correspondences
provide database administrators with an effective mechanism to balance
the expressiveness and tractability of consequence relations, and to
control the degree by which the existing classical theory of database
constraints can be soundly approximated in practice.
No previous knowledge of databases or logics is assumed.
About the speaker:
From Sebastian's web page:
Sebastian is Associate Professor of e-Commerce at SIM. Before joining
VUW he was a member of the Department of Information Systems and the
Information Science Research Center at Massey University. Sebastian's
research is considered to be on the leading edge of international
research in database theory. He was a recipient in the 2008 round of
Marsden funding for his project Cardinality Constraints for XML:
Challenging the Trade-off between Expressiveness and Tractability,
2009-2011.
Seminar Organisation
Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Sebastian Sardina, the seminar co-ordinator.