NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/comp/theory/2832

Internet Message Format | 1993-01-08 | 7.9 KB

Xref: sparky comp.theory:2832 comp.compilers:2118
Newsgroups: comp.theory,comp.compilers
Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
From: [e-mail] (Uwe Assmann)
Subject: SUMMARY: Graph grammars and ER model
Reply-To: [e-mail] (Uwe Assmann)
Organization: GMD
Date: Fri, 8 Jan 1993 09:31:39 GMT
Approved: [e-mail]
Message-ID: <[e-mail]>
Followup-To: comp.theory
Keywords: theory, summary
References: <[e-mail]>
Sender: [e-mail]
Lines: 158

Some weeks I posted a request for information about the relationship of
graph grammars and the ER-model. Here is a summary on the responses I got.
Thanks for everybody who responded, for me it was a good help.  My
questions were:

1) Hierarchy of graph grammars?
2) Correspondence between graphs and the Entity-Relationship model?
3) Besides graph grammars, are there other graph manipulation formalisms?

---------------------------------------------------------
Reply-To: [e-mail] (Marc Andries)

I just read your posting in comp.theory about graph grammar classes. As
the application of graph-rewriting to database manipulation is the topic
of the PhD-thesis I'm preparing, I think I can supply you with some useful
information.

First, I'm puzzled by the remark after your first question. I just had a
look at LNCS 291, i.e. the proceedings of the 3rd International GG
workshop, and on page 47 (the article of Manfred Nagl), I found 3 big
diagrams relating dozens of different types of graph grammars. Isn't this
what you're looking for ?

As for your second question, I'd like to refer you to LNCS 532, i.e. the
proceedings of the 4th International GG workshop, more precisely the
article of my supervisor Gregor Engels, on pp. 344-361, called "Elementary
actions on an extended Entity-Relationship Approach".  This article, as
well [EK80] in it's reference list, are the ONLY articles I know of that
relate DBs & GGs (that is, except the ones I'm currently working on 8-) ).

Finally, I suspect the answer to your third question is "no": "graph
grammar" (or more precisely "graph rewriting system") is used as a common
denominator for all kinds of graph manipulation formalisms.

---------------------------------------------------------
Reply-To: [e-mail] (Dr Jarzabek Stanislaw)

I used do work on a modeling formalism for software environments and for
this I integrated ER model with attribute grammars. This work was
described in Software Engineering Journal, March 1990, v 5 no 2 p. 125. I
never checked this in detail but have an impression that this formalism
has descriptive power close to graph grammars. In addition, it allows one
to specify what information should be stored in a database.

---------------------------------------------------------
Reply-To: [e-mail] (Harel David)

Regarding your second question ("Are there any papers on the
correspondence between graphs and the Entity-Relationship model from
databases?"), you might want to look at my paper in the May 1988 issue of
CACM. There is a discussion there about basing ER diagrams on something
called a higraph, which is a cross between graphs, hypergraphs and things
reminiscient of Venn diagrams.

--------------------------------------------------------- Reply-To:
[e-mail] (Reinier Post)

>3) Besides graph grammars, are there other graph manipulation formalisms?

The language I'm currently working on, called GOOD, is a graph
manipulation language intended for use as a database query language.  (It
is not of my own invention; I'm merely studying some details.)  See, e.g.

@inproceedings{GOODpods,
   title = {A Graph-Oriented Object Database Model},
   author = {M. Gyssens, J. Paredaens and D. {Van Gucht}},
   booktitle = "Proc. of the ACM Symp. Principles of Database Systems",
   month = {mar},
   year = {1990}
}

---------------------------------------------------------
Reply-To: [e-mail] (Andreas Schuerr)

Brandenburg F.J.: On polynomial time graph grammars Proc. STACS 88, LNCS
294, Springer 1988, pp. 227-236

Brandenburg F.J.: The equivalence of boundary and confluent graph grammars
on graph languages of bounded degree, in: Rewriting Techniques and
Applications (R.V. Book, ed.), LNCS 488, Springer 1991, pp. 312-322

Courcelle B., Engelfriet J.: A logical characterisation of the sets of
hypergraphs defined by hyperedge replacement grammars, Report 91-41
Unversity of Bordeaux, France 1991

Engelfriet J.: A Greibach Normal Form for context-free graph grammars,
ICALP'92 Proc. (W. Kuich ed.), LNCS 623 Springer 1992, pp. 138-149

Engelfriet J., Heyker L.M.: Context-free hypergraph grammars have the same
term-generation power as attribute grammars, Acta Informatica 29, 1992,
pp. 161- 210

Engelfriet J., Leih G., Rozenberg G.: Apex graph grammars and attribute
grammars, Acta Informatica 25, 1988, pp. 537-571

Habel A., Kreowski H.-J., Vogler W.: Decidable boundedness problems for
hyperedge-replacement graph grammars, in Proc.  TAPSOFT '89, LNCS 351,
Springer 1989, pp. 275-289

UND NATUERLICH:

Nagl M.: Graph-Grammatiken, Vieweg Verlag 1979


---------------------------------------------------------
Reply-To: [e-mail] (Heiko Doerr)

Zu Deiner Frage nach Graphgrammatikklassen u.a. moechte ich folgendes
beisteuern. Vielleicht hast Du die Angaben bereits, aber vielleicht eben
auch nicht.

Zu 1): Graphklassen: Die einzige Klassifikation, die ich kenne, ist die
von Nagl in seinem Buch "Graph-Grammatiken". Dabei geht er von den
syntaktischen Eigenschaften der linken Seite und der Maechtigkeit der
Einbettungsueber- fuehrung aus. Er versucht eine Klassifikation analog der
Chomsky-Hierarchie.  Dies ist aber ziemlich umstaendlich, da wesentlich
mehr Kombinationen von syntaktischen Einschraenkungen moeglich sind. Er
stellt eine Hierarchie von Graphsprachen auf, die mit Grammatiken eines
bestimmten Typs erzeugt werden koennen. Dazu simuliert er jede
Produktionen einer Grammatik durch eine Menge von Produktionen einer
anderen Grammatik. Wesentlich dabei sind nichtterminale Symbole.
Beliebige Erweiterungen von Grammatiken durch etwa Attributierung und/oder
Programmierung erschweren eine Vergleichbarkeit. JedeR baut so
ihren/seinen Kalkuel. (Ich auch)

Zu 2): Ich weiss, dass Gregor Engels Graph-Grammatiken mit erweiterten ER-
Diagrammen verbunden hat. Ich kann Dir dafuer aber leider keine Referenz
geben. Diese Arbeiten sind an der TU Braunschweig entstanden. Gregor
Engels ist jetzt an der Leiden University, Dept. of CS, POB 9512, NL-2300
RA Leiden.  Sicher wirst Du etwas von ihm direkt erfahren koennen.

Zu 3): Im weiteren Sinne sind wohl auch Graphreduktionstechniken, die zur
Implementierung von funktionalen Sprachen verwendet werden, als
Graphmanipulationskalkuel zu verstehen. Sie lassen sich aber auch als
Sonder- fall von GG'en auffassen. Ich selbst bin im Moment dabei, eine
Version von GG'en zu definieren, mit der Ersetzungen durch eine spezielle
abstrakte Maschine durchgefuehrt werden koennen. Dadurch soll eine
Reduktion des Aufwandes einer Ersetzung erreicht werden. Naeheres dazu
wird im Lauf des Monats fertig (hoffentlich!).

---------------------------------------------------------
Reply-To: Ulrich Hoffmann <[e-mail]>

Prof. Juergen Ebert aus Koblenz arbeitet ueber dieses Thema.  Er will
demnaechst eine Veroeffentlichung ueber das Verhaeltnis von
Graphgrammatiken und ER publizieren.  Im APPLY-Projekt haben wir eine
Graphsprache als Zwischensprache.  Angeregt durch Prof. Eberts Vorgehen
soll deren Syntax demnaechst durch eine Graph-Grammatik basierend auf
ER-Diagrammen beschrieben werden soll.
--
Uwe Assmann
GMD Forschungsstelle an der Universitaet Karlsruhe
Vincenz-Priessnitz-Str. 1
7500 Karlsruhe GERMANY
Email: [e-mail] Tel: [phone] Fax: [phone]
--
Send compilers articles to [e-mail] or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.