King's College London

Research portal

A port graph rewriting system for visual data modelling

Student thesis: Doctoral ThesisDoctor of Philosophy

Relational database technology has been in use since the 1970s and design methodologies evolved since then. Despite four decades of continuous development, these design methodologies are still hard to understand and/or to follow. Surveys have shown that in very complex databases conceptual and/or logical modelling is omitted because the popular methodologies are too cumbersome (e.g. normal form checks). Not to mention the fact that the resulting model is hard to maintain (limited round-trip engineering capabilities). Database designers therefore require a purposely built tool that is aware of and enforces conceptual and logical database design principles. Currently available tools provide limited functionality of this kind and their model validation features are also limited.

The motivation of this research is to provide database designers with a tool that makes database model validation easy and understandable; that makes database testing more straightforward and, all in all, a tool that promotes proper database designs. This thesis presents a new approach to relational database modelling, based on strategic port graph rewriting.

More precisely, the contributions are as follows. A port graph visual language to model relational database schemata is presented. The standard notion of port graph rewrite rule is extended with generic Rule Application Conditions and pattern-based rule generators called Variadic Rewriting Rules. Port graph rewriting rules and strategies are provided to accomplish the following database design tasks: generating a Syntactic closure, finding a Minimal Cover, solving the Membership Problem, finding all candidate keys and obtaining 3NF. Correctness properties e.g. termination, soundness and completeness of these algorithms are shown. A prototype implementation of the Rule Application Conditions extension is provided in a port graph modelling framework called Porgy. Said database design strategies are also implemented in this framework and illustrated with examples.
Original languageEnglish
Awarding Institution
Award date1 Oct 2020


Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454