IQPI: An incremental system for answering imprecise queries using approximate dependencies and concept similarities

Most of the proposed systems to process queries over web databases require the user to provide some information regarding the relative importance of attributes and the similarities between nominal values. Recently, a new system called AIMQ has been proposed, which is based on measuring concept similarities. This system is end-user independent and can answer imprecise queries. The main drawback of this system is that it is not incremental. All computations must be repeated when a tuple is added to the database. As a solution to this problem, in this article, we propose an incremental and efficient system called IQPI, which can be considered as the incremental version of AIM. In IQPI, the set of approximate dependencies between attributes are mined, first (using our new efficient approach). Using this set of dependencies, the user's imprecise query is converted into some precise queries. Each of the precise queries is then fed into the system and the results are filtered (to obtain most relevant answers) using concept similarity graphs. These graphs are constructed in another part of the system and each edge in a graph represents the similarity between two nominal values. The structure of the similarity graphs are such that the least amount of computation is needed for them to be updated, when database is changed. In dependency mining part of the system, we present a new incremental algorithm that is based on logical operations over bit strings. It is crucial for a search system to be incremental, due to the dynamic nature of the world-wide web.