Werner Nutt visiting Webdam
Werner Nutt is visiting Webdam from Monday 20 April to Friday 24 April 2009. He is a professor at the Faculty of Computer Science at the Free University of Bozen-Bolzano.
He will present his work on containment of conjunctive queries over databases with null values Friday at 2:00pm in the meeting room G008.
Title : Containment of Conjunctive Queries over Databases with Null Values (Joint work with Carles Farre, Ernest Teniente, and Toni Urpi, UPC Barcelona)
Summary : Intuitively, one query “contains” another query if it is more general than the other query. Query containment is a key topic in database theory, which was originally motivated as a foundation of query optimisation, but has also other applications, such as integrity checking and information integration.
The containment problem has been studied for many different types of queries. The work so far, however, has never considered the effect of SQL style null values, although they are ubiquitous in real world data and queries have to process them.
In this talk we discuss in which ways null-containment, that is, containment in the presence of null values, differs from the non-null case. We consider conjunctive queries, which are essentially single block SQL queries. We show that null-containment, as in the non-null case, is NP-complete for boolean queries, which return only yes or no, while the situation becomes different from the classical case for queries that output data. We also discuss sufficient, but non-necessary criteria for null-containment, special cases with polynomial complexity, the effect of “is null” tests, as well as null-containment for richer classes of queries where comparisons or unions are allowed.
Short Bio : Werner Nutt is a professor at the Faculty of Computer Science at the Free University of Bozen-Bolzano in the Italian Alps (since 2005). He obtained a PhD and a habilitation from the university of Saarbruecken, was a visiting associate professor in Jerusalem (1997-2000) and a reader at Heriot-Watt University in Edinburgh (2000-2005). His research interests are in Artificial Intelligence and Databases, with a focus on Description Logics, Information Integration and Incomplete Information.