Data schemata based on directed graphs

Rooted, labeled, directed graphs (RLDs) are taken as the basis for describing data structures. A constructive formalism is set up to describe RLDs, generate them by means of grammars, and carry out operations such as accessing nodes, inserting and deleting data items, and recognizing graph patterns. It is shown how the formalism can be translated into languages for data definition and data manipulation, of the type associated with data-base systems. The availability of the formalism allows a systematic development of such languages, and provides a method of incorporating consistency preconditions to structural operations and proving the correctness of the data structures that arise in using such languages.