  In this paper we give a robust logical and computational characterisation of
peer-to-peer database systems. We first define a pre- cise model-theoretic
semantics of a peer-to-peer system, which allows for local inconsistency
handling. We then characterise the general computa- tional properties for the
problem of answering queries to such a peer-to- peer system. Finally, we devise
tight complexity bounds and distributed procedures for the problem of answering
queries in few relevant special cases.
