Consistency of mappings

Grigoris Karvounarakis
University of Pennsylvania

The vision of the SHARQ (Sharing Heterogeneous and Autonomous
Resources and Queries) project involves the ability of peers to
autonomously join the system and create new mappings between peer
schemas. This raises the question whether there are cases in which
adding a mapping could "break" the system, in the sense that there are
no instances for the peers that satisfy all the mappings. We define
the notion of consistency to capture this property of sets of
mappings. We identify classes of mappings that are always consistent
and provide an algorithm to decide consistency in other cases. In a
related issue, we provide an algorithm to check if the result of
evaluating a conjunctive query is always empty, over all instances
that satisfy a consistent set of mappings; such queries need not be
evaluated at all,  regardless of the actual data in the peers, while
identifying such queries allows the system to provide more accurate
feedback to the user (instead of just returning an empty answer to the
query).