Master Thesis Defense by Mr Sergey Paramonov
Mr Sergey Paramonov defended his master thesis on 'A Logic Programming Approach to Query Completeness'.
Mr Sergey Paramonov defended his master thesis on 'A Logic Programming Approach to Query Completeness' at TUW on 10 January 2012.
Abstract:
How to manage incomplete information has been studied in database research almost from the beginning. The focus was on how to represent incomplete information and how to compute certain answers. Less attention has been given to describing which parts of a database are complete and how to find out whether a query returns complete answers over a partially complete database
To address these questions, we build on previous work by Motro (1989) and Levy (1995) who formalized when a query is complete over a partially complete database and what it means that parts of the tables are complete. Recently, Razniewski and Nutt (2011) characterized the complexity of various reasoning tasks in this setting. It was open, however, how to implement completeness reasoners in practice. In this talk, we introduce the problem of query completeness reasoning and show that it can be mapped elegantly to answer set programming (ASP) over datalog with negation. Then we consider extensions of the original problem that take into account foreign key constraints and finite domain constraints on attributes. To encode the extensions, we make use of Skolem functions and of datalog rules with disjunctions in the head. We show the correctness and completeness of the encodings by several characterization theorems. We also discuss a possible approach that takes into account presence of comparisons and show how it can already solve this problem if comparisons satisfy some syntactical restrictions. With our encodings we can solve completeness reasoning tasks using the DLV system, which implements answer set programming for disjunctive logic programs. DLV is being developed at TU Vienna and at the U of Calabria.