MODELS OF APPROXIMATION IN DATABASES

Partial information in databases can arise when information from sever al databases is combined, Even if each database is complete for some ' 'world'', the combined databases will not be, and answers to queries a gainst such combined databases can only be approximated. In this paper we describe various situations in which a precise answer cannot be ob tained for a query asked against multiple databases. Based on an analy sis of these situations, we propose a classification of constructs tha t can be used to model approximations. The main goal of the paper is t o study several formal models of approximations and their semantics. I n particular, we obtain universality properties for these models of ap proximations. Universality properties suggest syntax for languages wit h approximations based on the operations which are naturally associate d with them. We prove universality properties for most of the approxim ation constructs. Then we design languages built around datatypes give n by the approximation constructs. A straightforward approach results in languages that have a number of limitations. In an attempt to overc ome those limitations, we explain how all the languages can be embedde d into a language for conjunctive and disjunctive sets from Libkin and Wong (1996) and demonstrate its usefulness in querying independent da tabases. We also discuss the semantics of approximation constructs and the relationship between them.