Graph Patterns: Structure, Query Answering and Applications in Schema Mappings and Formal Language Theory
Juan Reutter, University of Edinburgh
Graph data management is currently one of the most active topics in knowledge engineering, driven by the graph models that underpin the Semantic Web, social network analysis, biological databases, geographical information systems, and many others.
One of the key problems in the area is to understand how to efficiently query huge volumes of graph-based data. Essentially the problem is to find a sub-graph pattern representing the information being sought. This is a challenge in itself, made more complicated by the fact that real-world queries often lead to incomplete graph patterns. The work presented in this thesis shows that graph pattern queries are computationally more challenging than other common paradigms for knowledge retrieval. It develops restrictions on patterns to form a tractable sub-set that can be used for efficient queries, and applies these results to problems in information exchange.
The committee felt that this thesis was exceptionally strong, containing both theoretical analysis and practical applications to an area of great and growing importance in computer science. It provides a well-founded way of addressing a topic that spans a large range of fields of current interest in a way that offers significant prospects for further fruitful research.
About the author:
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.
His research interests are in different aspects of data management and automata theory, including graph and semi-structured databases, ontology-based data access, data exchange, metadata management and the semantic web. 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.
The Use of Automated Search in Deriving Software Testing Strategies
Simon Poulding, University of York
Some strategies for selecting test data are, in theory, very effective at detecting faults in software but, in practice, are difficult and costly to use. This thesis proposes that metaheuristic search may be used to bridge this gap between theory and practice, and demonstrates how such an approach enables the use of a sophisticated and effective strategy for random test data generation that would otherwise be too costly. The cost-effectiveness of this search-based approach is enhanced by the rigorous empirical determination of an efficient configuration of the search algorithm, and by the exploitation of commodity GPU cards to parallelise the algorithm. The use of a flexible grammar representation for the domain of test inputs ensures that this approach can be applied to a wide range of software.
The committee felt that the thesis takes an approach that has been regarded as attractive in theory but difficult in practice, and turns it into a potentially useful tool for testing large systems. This has enormous implications for the practice of software engineering and for the development of robust and dependable software under realistic industrial conditions.
About the author:
Simon Poulding studied for his PhD in the Department of Computer Science at the University of York. During this time he participated in two inter-university research projects on search-based software engineering (SEBASE and DAASE) that were funded by the EPSRC. Simon previously worked as a commercial software engineer before returning to academia to attain an MSc in Mathematics prior to starting his PhD. He is currently a postdoctoral researcher in the Software Engineering Research Lab at the Blekinge Institute of Technology, Sweden, where he is investigating techniques to verify the performance efficiency and robustness of software systems.
The 2014 panel members were:
- Simon Dobson (St Andrews, Chair)
- Russell Beale (Birmingham)
- Joemon Jose (Glasgow)
- Perdita Stevens (Edinburgh)
- Steve Pettifer (Manchester)
- Iain Phillips (Loughborough)