Abstract
Many of the existing data base models have an underlying graph structure. Even certain models based on set theory rather than graph theory are translatable into some graph representation, an important example being the relational model.
Graphs are used to represent the data base at the schema or at the instances level. Also, the representation may refer to conceptual elements, such as entities, attributes, relationships, or to implementational elements, such as files, records, items, links.
In any case, one wishes to characterize the valid configurations, and the allowable operations which transform one configuration into another one. Valid configurations are those that conform to the integrity constraints declared for the particular data base.
In this work we investigate the use of graph grammars for the specification of data base operations, in ways that preserve the imposed integrity constraints.
Preview
Unable to display preview. Download preview PDF.
References
Kerschberg, L., Klug, A. and Tsichritzis, D. — "A taxonomy of data models" — Proc. of the Very Large Data Bases Conference (1976).
Reisner, P. — "Use of psychological experimentation as an aid to development of a query language", — IEEE Transactions on Software Engineering, SE-3,3 (1977) 218–229.
Zloof, M.M. — "Query by example" — Proc. of National Computer Conference (1975).
Mc Donald, N. and Stonebraker, M. — "Cupid: the friendly query language" — Proc. of ACM Pacific Conference (1975).
Date, C.J. — "An introduction to data-base systems" — Addison-Wesley (1975).
Schneider, H.J. — "Conceptual data base description using graph-grammars" — in "Graphen, Algorithmen, Datenstrukturen" — Noltemeier (ed.) — C. Hanser Verlag (1976).
Brainerd, W.S. and Landweber, L.H. — "Theory of Computation" — John Wiley (1974).
Montanari, U. — "Separable graphs and web grammars" — Information and Control 16 (1970) 243–267.
Furtado, A.L. and Kerschberg, L. — "An algebra of quotient relations" — Proc. of the SIGMOD Conference (1977).
Guttag, J.V. and Horowitz, E. — "The design of data type specifications" — in "Current trends in programming methodology" v. IV — Yeh (ed.) — Prentice-Hall (1978).
CODASYL Systems Committee — "Feature analysis of generalized data base management systems" — report (1971).
Rosenkrantz, D.J. — "Programmed grammars and classes of formal languages" — JACM 16 (1969) 107–131.
ANSI/X3/SPARC Study Group — interim report — bulletin FDT of ACM SIGMOD 7,2 (1975).
Booth, T.L. — "Sequential machines and automata theory" — John Wiley (1967).
Goguen, J.A. et al — "An introduction to categories, algebraic theories and algebras" — IBM report RC 5369 (1975).
Paolini, P. and Pelagatti, G. — "Formal definition of mappings in a data base" — Proc. of the SIGMOD Conference (1977).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1979 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Furtado, A.L. (1979). Transformations of data base structures. In: Claus, V., Ehrig, H., Rozenberg, G. (eds) Graph-Grammars and Their Application to Computer Science and Biology. Graph Grammars 1978. Lecture Notes in Computer Science, vol 73. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0025723
Download citation
DOI: https://doi.org/10.1007/BFb0025723
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-09525-5
Online ISBN: 978-3-540-35091-0
eBook Packages: Springer Book Archive