Paper Info
Title
Complete approximations of incomplete queries
Abstract
We present a system that computes for a query that may be incomplete, complete approximations from above and from below. We assume a setting where queries are posed over a partially complete database, that is, a database that is generally incomplete, but is known to contain complete information about specific aspects of its application domain. Which parts are complete, is described by a set of so-called table-completeness statements. Previous work led to a theoretical framework and an implementation that allowed one to determine whether in such a scenario a given conjunctive query is guaranteed to return a complete set of answers or not. With the present demonstrator we show how to reformulate the original query in such a way that answers are guaranteed to be complete. If there exists a more general complete query, there is a unique most specific one, which we find. If there exists a more specific complete query, there may even be infinitely many. In this case, we find the least specific specializations whose size is bounded by a threshold provided by the user. Generalizations are computed by a fixpoint iteration, employing an answer set programming engine. Specializations are found leveraging unification from logic programming.
Year
DOI
Venue
2013
10.14778/2536274.2536320
PVLDB
Keywords
Field
DocType
complete information,specific aspect,incomplete query,general complete query,complete set,complete database,complete approximation,original query,conjunctive query,specific complete query,specific specialization
Query optimization,Data mining,Range query (database),Conjunctive query,Computer science,Logic programming,Answer set programming,Complete information,Database,Boolean conjunctive query,Bounded function
Journal
Volume
Issue
ISSN
6
12
2150-8097
Citations 
PageRank 
References 
1
0.36
7
Authors
4
Name
Order
Citations
PageRank
Ognjen Savkovic1389.55
Paramita Mirza2507.83
Alex Tomasi361.44
Werner Nutt42009395.43