Navigational Query Languages

Abstract

In this thesis we introduce navigational query languages on graphs. Path queries in our languages are built over several operators: identity, union, composition, projection, coprojection, converse, transitive closure, diversity, intersection and difference. The smallest language we will consider only contains the first 3 operators, while the largest language contains all operators. For these query languages we will characterize their complete relative expressive power, i.e., we will compare the expressive power of languages containing different selections of operators. In these query languages we will also model boolean queries by associating nonempty query results with true and empty query results with false. As for path queries, we will for these boolean queries characterize the complete relative expressive power of our languages. On the other hand, we will also consider other approaches to model boolean queries in our languages and characterize their expressive power.