Generating relations using formal grammars

Abstract

Grammars generating 2-dimensional arrays have been studied by many people [1, 2, 3, 4). One effort was Random Context Array Grammars [4], where different types of context conditions placed on the production, were used to control the generating process. Relations, as used in relational data bases, can be considered as rectangular arrays, and therefore it should be possible to generate and manipulate relations using 2-dimensional Grammars. Simple Relation Grammars generate relations, and can simulate some unary operations like select and project on these relations. Extended Relation Grammars also generate relations, but these relations can communicate with each other within a "Extended Relation Schema (ERS)". Within such an ERS binary operations like union and join can be simulated. This paper is a summary of a research project of which certain parts have already been submitted for publication.