Graph Patterns: Structure, query answering and applications in schema mappings and formal language theory

Graph data appears in a variety of application domains, including social networks, biological databases and the Semantic Web initiative. In all these applications, the underlying data is naturally modelled as graphs. Once we start querying, matching or transforming these graph databases, we often end up with incompletely specified graph data, in the form of a graph pattern. In turn, queries need to be posed against such data, but techniques for querying patterns are generally lacking, and even simple properties of graph patterns, such as the languages needed to specify them, are not well understood. This dissertation provides a thorough study of graph patterns, offering a theoretical formalisation of graph patterns and studying how to query them and how to use them as queries