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.
Juan Reutter is an assistant professor at the Department of Computer Science at the Pontificia Universidad Católica de Chile, and an associate investigator of the Centre for Semantic Web Research. He studied for his PhD in the School of Informatics at the University of Edinburgh, working in the database group of the Laboratory for Foundations of Computer Science under the supervision of Professor Leonid Libkin. He received the Best Paper Award at PODS in 2011 and the “Ramon Salas” Award for the best work in engineering produced by Chilean researchers in 2012. He has served on the program committee for SIGMOD and AAAI conferences and has published several papers in major database conferences and journals.
3 Graph Patterns
4 Answering Queries Over Graph Patterns
5 Tractable Query Answering
6 Schema Mappings and Data Exchange
7 Applications in Formal Language Theory
8 Decision Problems for Incomplete Automata
9 Conclusions and Future Work
Appendix: Proofs and Additional Results