Personal tools
You are here: Home Graduate Study Incompleteness of relational, XML, and graph database

Incompleteness of relational, XML, and graph database

Incomplete data is ubiquitous and poses even more problems than before.  The more data we accumulate, the more instances of incompleteness we have.  And yet the subject is poorly handled by both practice and theory. Many queries for which students get full marks in their undergraduate courses will not work correctly in the presence of incomplete data, but these ways of evaluating queries are cast in stone (SQL standard). We have many theoretical results on handling incomplete data but they are, by and large, about showing high complexity bounds, and thus are often dismissed by practitioners. Even worse, we have a basic theoretical notion of what it means to answer queries over incomplete data, and yet this is not at all what practical systems do.

The situation looked quite bleak for many years but recently progress has been made that opened totally new avenues of attack. We have elements of a basic theory that apply to the majority of existing data models, but we need to understand how to specialize them and make effective use of them to produce query answers not only in a pure database environment but also in applications such as data integration, data exchange, consistent query answering, and answering queries in the presence of ontologies.

The project brings together tools and techniques from data management, AI, algorithms, programming semantics, and mathematical logic.


Potential Supervisor: Leonid Libkin

Document Actions