Semantic classifications of queries to relational databases

We survey different semantic classifications of queries to relational databases, as well as the different systems of partial isomorphisms developed as algebraic (hence, semantic) characterizations of equality of theories for databases, in FO and in weaker logics. We introduce an abstract notion of similarity for databases, as equality in the theories for a given logic and we define different sub-classes of queries by requiring that the queries in a given sub-class should not distinguish between databases which are similar. Then we use this general strategy to present a new semantic classification, with the class of bounded variable logics with counting (C k ), as the target logics. One important consequence of the definition of the two semantic classifications of queries which we present here is their orthogonality with the TIME-SPACE hierarchy defined in Turing machine complexity, allowing the definition of finer complexity classes by intersecting orthogonal hierarchies.