A Port Graph Rewriting Approach toRelational Database Modelling

EasyChair Preprint 1425

Abstract

We present a new algorithm to compute the Syntactic Closure of a set of functional dependencies, using strategic port graph rewriting. We specify a Visual Domain Specific Language to model relational database schemata as port graphs, and provide an extension to port graph rewriting rules. Using these rules we implement strategies to find the syntactic closure of a set of functional dependencies, analyse the closure and find minimal covers, essential for schema normalisation. We prove soundness and completeness of the computed closure. This methodology is implemented in PORGY, a generic modelling tool that provides a graphical interface and primitives to create and analyse port graph rewriting systems. We illustrate it with examples. Other algorithms to find closures exist, but the strategic graph program provides a visual description of the computation coupled with analysis features not available in other approaches.

Keyphrases: Relational Databases, database design, functional dependency, graph transformation, minimal cover, port graph

@booklet{EasyChair:1425,
  author    = {Maribel Fernandez and Bruno Pinaud and János Varga},
  title     = {A Port Graph Rewriting Approach toRelational Database Modelling},
  howpublished = {EasyChair Preprint 1425},
  year      = {EasyChair, 2019}}