Abstract
Real-life spatial databases are inherently incomplete. This is in particular the case when data from different sources are combined. An extreme example are volunteered geographical information systems like OpenStreetMap. When querying such databases the question arises how reliable are the retrieved answers. For instance, for positive queries, which ask for existing patterns of objects, further answers could show up if the data is completed. For queries with negation, it is furthermore possible that after data completion objects cease to satisfy a query. On the OpenStreetMap wiki, contributors have started to record for some areas which object types have been mapped completely. Given a query, we show how such metainformation can be used to classify objects in the database as certain answers, which are certainly answers in reality, impossible answers, which in reality are definitely not answers, and possible answers, for which it is not known whether they are answers in reality. In addition, we compute the completeness area of a query, that is the maximal area for which it is certain that no further answer objects exist in reality. All this additional information can be computed with standard operations on spatial data. Experiments suggest that the computation of such completeness information is feasible.