  In this extended abstract we provide a unifying framework that can be used to
characterize and compare the expressive power of query languages for different
data base models. The framework is based upon the new idea of valid partition,
that is a partition of the elements of a given data base, where each class of
the partition is composed by elements that cannot be separated (distinguished)
according to some level of information contained in the data base. We describe
two applications of this new framework, first by deriving a new syntactic
characterization of the expressive power of relational algebra which is
equivalent to the one given by Paredaens, and subsequently by studying the
expressive power of a simple graph-based data model.
