Applied use of Ehrenfeucht Fraisse Games — Model Transformation

The Object-Role Model Unifying Metamodel

I’ve released my research publicly so that it can be enjoyed by all, link below:

Applied Use of Ehrenfeucht Fraisse Games in Conceptual Model Management and Model Transformation

In essence, the thesis is that the model transformation technology behind the Boston Architecture behind the Boston Multi-Model Conceptual Modelling software and as aspired to by the likes of the Object Management Group (OMG) et al, is best described generically as an applied Ehrenfeucht Fraisse Game (EFG). A generic core metamodel (per Fagin et al) is exploited by way of differentiated interpretation using EFGs.

Object-Role Modeling and Ambiguity — Exploited for gain

The Boston Architecture relies on Object-Role Modeling, and theorems under Finite Model Theory (FMT) in general, being ambiguous when viewed through the lens of an Ehrenfeucht Fraisse Game. This ambiguity can be exploited for productive gain in transformation of conceptual models from one language to another. Common points of structure between different conceptual modelling languages become homomorphic points of structure between differentiated interpretations of the same set of theorems under a common metamodel.

The overall picture of the architecture is below:

The Conceptual Modeling Meta-Model (CMML) and Boston Architecture. Image by author.

In essence, what the architecture allows for is the storage of structural and procedural models within the ORM metamodel, and model transformation by way of differentiated interpretation of the same theorems of/under a common unifying metamodel.

There is a general misconception that Object-Role Modeling is unambiguous, but this is not true; especially of ORM version 2 or ORM2. In other articles I have documented the various ways in which Object-Role Modeling can be ambiguous and especially without software to disambiguate ORM models. I don’t see this as necessarily as a bad thing, because the Boston Architecture relies on ORM being ambiguous under Ehrenfeucht Fraisse Games to achieve model transformation.

The main reason why Object-Role Modeling can be ambiguous, and that exploited, is because logic is not a function of theorems or drawings on a piece of paper/computer screen, but rather is a function of the interpreter (person or computer) of those theorems or drawings.

Object-Role Modeling (or NIAM version 1) was originally synthesised as output of the PhD thesis of Terry Halpin. In essence Halpin mapped a morphism between Object-Role Models (then called NIAM) and theorems of a theory under Finite Model Theory (FMT) called Knowledge Language (KL). An example with a subset of the corresponding KL theorems in the image below:

Homomorphism, Object-Role Modeling to Knowledge Language (KL). Image by author.

I wouldn’t go so far as to say that Halpin’s thesis proves an isomorphism from one to the other, but it makes no difference. The function of deciding over the structure defined by an Object-Role Model or theorems of a theory under finite-model theory is one of the interpreter, not of the drawing or theorems themselves and as they are presented on a piece of paper or computer screen, as we shall see.

ORM version 2, or ORM2, which is the current version of Object-Role Modeling, introduces features that have no correspondence to theorems of KL without the use of software to help disambiguate the drawing, as discussed here . Without the one-to-one mapping from a drawing to theorems of finite model theory, all purposeful use of Halpin’s thesis is lost.

But the ambiguity of Object-Role Modeling version 1 (ORM) can be exploited, because finite model theory has a feature (or flaw if you think of it that way) which renders theorems of a theory under finite model theory open to multiple and varied interpretation. Indeed my business and the Boston architecture relies on the potential of Object-Role Modeling having multiple interpretations.

Ehrenfeucht Fraisse Games

An Ehrenfeucht Fraisse Game (EFG) is a logical game played between two people/interpreters and where structures formed by theorems of a theory are exchanged from the first to the second and the second wins if they come up with a different interpretation of the theorems exchanged. Let’s imagine our Knowledge Language theorems from the viewpoint of two different people:

People engaging in an Ehrenfeucht Fraisse Game. Image by author. Brain images royalty free from Pixabay.

To be unambiguous, each person would have to be forced, by the theorems themselves to have the same interpretation. We know this is not ensured by the very nature of Ehrenfeucht Fraisse Games. There is no proof that the second player will always come up with a different interpretation, but we can prove that it is possible to win by actually playing the game as a second player and winning. And that’s all we need. If we can do it once, we can safely say that the theory is capable of expressing ambiguity and any theory isomorphic with that theory is also capable of expressing ambiguity.

An inherent feature of an Eherenfeucht Fraisse game is that it matters not what the standard interpretation of a theory is, or even the intended meaning of the theorems sent from the first player. It only matters what interpretation the second player has, and if that interpretation is different from the first player. In many respects, this reduces logic to a subjective game that can be observed objectively as the expression of a multi-player game, each working over a theory and possibly the same theorems.

Ehrenfeucht Fraisse Games cement the view that a standard interpretation of a theory is no guarantee of removing ambiguity. Indeed, EF games ask if there really is any such thing as a standard interpretation. The best we can come up with is a shared interpretation between 2 or more players at any one point in time and where any player can shift interpretations at any point in time.

Different interpretations of an Object-Role Model and how that is exploitable

I write software that uses Object-Role Modeling and its ambiguous nature as part of my business, FactEngine. The Boston software allows you to view your database as an Object-Role Model, an Entity Relationship Diagram or a Property Graph Schema, as below:

Click to enlarge. Morphing conceptual models. Image by author.

Entity Relationship Diagrams and Property Graph Schema have different structures, or points of structure. Many-to-many tables in Entity Relationship Diagrams disappear inside a Property Graph Schema as they are reduced to a relationship, rather than a table/entity. Viz the BookingHasSeat table in the image above as it disappears into a relationship between Booking and Seat nodes in our morphing diagram.

That is, what was a point of structure in one diagram, disappears in the second diagram. The points of structure are changed.

When we consider points of structure, we can envisage the points of structure enthused by theorems of a theory under finite model theory. That is, we can envisage our Entity Relationship Diagram or Property Graph Schema as theorems under Halpin’s Knowledge Language and as Object-Role Models themselves.

And that’s how Boston, the software FactEngine produces, works. The ER Diagrams and Property Graph Schema are stored as Object-Role Models inside the same ORM metamodel that stores the Object-Role Models. Not only that, the ER Diagrams and Property Graph Schema in Boston use exactly the same metamodel! But they have different interpretations.

As an example, watch the following video carefully. The original Entity Relationship Diagram has 11 points of structure (the 11 tables/entities). The Property Graph Schema has 8.

1. The metamodel of the ER Diagram is displayed, as an Object-Role Model.
2. The language of the ER Diagram is changed to Property Graph Schema.
3. The page is closed and reopened…and voila the ER Diagram has converted to a Property Graph Schema with only 8 points of structure.

Click to enlarge. Software playing an Ehrenfeucht Fraisse Game. Image by author.

Effectively we have engaged the Boston software itself to play an Ehrenfeucht Fraisse Game with Object-Role Modeling, and the corresponding theorems of KL under finite model theory, to get two different interpretations of the same Object-Role Model, the metamodel of ER Diagrams and Property Graph Schema. One model, one set of theorems…two interpretations; three if you include the Object-Role Model as a third interpretation with even more points of structure than the other two.

What are the implications for Object-Role Modeling? Object-Role Modeling can be inherently ambiguous by the very nature of logic being a function of the interpreter, not theorems of a theory, so you can safely ignore people who say that Object-Role Modeling is unambiguous.

The implications are that Object-Role Modeling is very useful indeed, because it has an inherent weakness. You can exploit the weaknesses of Object-Role Modeling to view a database as a relational database OR a graph database at the same time.

In an earlier article I argued that all databases can thus be viewed as multi-model and that the definition of a graph database is quite fluid.

Because relational databases can be queried with graph query languages, relational databases can be queried with arguably the best graph query language around …natural language.

Graph query in natural language per FactEngine. Image by author.

This makes Object-Role Modeling perfect for working with Knowledge Graphs.

Thanks for reading. I hope that shares why Object-Role Modeling can be naturally ambiguous and how this inherent weakness in Object-Role Modeling can be exploited to do useful work. As time permits I will write more on Object-Role Modeling, graph databases and Ehrenfeucht Fraisse Games.

Attribution: The ‘Cinema Bookings’ model derived from that previously shared under the ActiveFacts GitHub repository.

Why release this now?

In 2010 I gave a demonstration of the Boston architecture at an ORM conference in Rome. It was then called the Richmond architecture. It has come to my attention that my research was then remodelled and published as original research of others, without attribution of the prior work of the Richmond architecture.

This publication dates the generalised result of what they are trying to do as best described as an Ehrenfeucht Fraisse Game. To my knowledge, my work is the first to describe conceptual model transformation as an Ehrenfeucht Fraisse Game over theorems under a unifying metamodel. I attribute the seminal research in this area to Ronald Fagin et al in his work “Data exchange. Getting to the core” [1]. My work merely generalises the result as a game.

1. Fagin, R., Lolaitis, P.G., Popa, L., (2005), “Data Exchange: Getting to the core”. ACM Transactions on Database Systems, 30(1), p.174–210.

— — — — — — — — — — End — — — — — — — — — — — — -