User Tools

Site Tools


modeling:hypergraph-er

Scientific Grounding

The highest abstraction level that is considered in RobMoSys is related to Hierarchical Hypergraphs and Entity-Relation models. The Entity-Relationship1) model was one of the first approaches for formal “data base” models of knowledge.2) It has gained renewed interest because of the rising popularity of the “Semantic Web”3).

One of the main challenges is to represent context, more in particular, to deal with the combinatorial explosion in the number of relationships needed to represent – and interconnect – all relevant pieces of information and knowledge in multi-domain ICT and engineering systems. Such interconnected knowledge forms graph networks of links and properties. This fact poses difficulties to Lisp, Prolog, or other “programming languages” for Artificial Intelligence (AI), since they only have representations for relationship trees as first-class citizens. The same holds for the frame languages 4) in AI, which considered “multiple inheritance” as a key feature. This last feature, together with “data encapsulation”, are two major aspects of strict object oriented languages and models, that make “open world” 5)6) knowledge representations difficult; the SOLID principles of object orientation better support knowledge representation, especially via its “D” feature, that is, the Dependency inversion principle, which states that one should “depend upon abstractions, not on concretions”. However, none of these approaches offers infinitely composable knowledge representations, because they only partially support the essential features outlined in the sections below.

Hierarchical Hypergraph

The modern, higher-order, version of the Entity-Relationship model is that of a hierarchical (property) hypergraph7)8):

  • hierarchical : every node and every edge can be a full graph in itself. In other words, any Relation can be considered an Entity in itself, and can hence be used as an argument in another, higher-order Relationship.
  • hypergraph: every edge can connect more than two nodes; that is, it is an n-ary “hyperedge”
  • property meta data: every node and every edge in the graph has a property data structure attached to it; two (mandatory) parts of those properties are the following meta data:
    • unique node/edge identifier : other relationships in the graph can refer to this node or edge.
    • meta model identifier : each node or edge has a type, indicated by the unique identifier of the graph that models that type.

Often used synonyms for the term “Entity” are: object, concept, atom, primitive. “Relationships” are also called: rules, axioms, constraints, links, expressions. Often used extra meta data is the so-called provenance of a model: who made it? when? what version is it? Etcetera. State of the art formal meta models to represent such provenance are W3C provenance9), and Dublin Core10).

Entity-Relation Model

Each “thing” to be modelled will have a number of data structures that represent its properties. That can be done via (possibly nested) key-value pairs, with each key having, a type, a unique identifier (with which Relationships can refer to it), and a role to play in the “thing” properties. While efficient implementations of those properties can be realised with the rich data structure primitives in computer programming langauges, the meaning of such properties, as just described above, is a hierarchical hypergraph.

A Relationship between Entities is a named directed graph, representing the Role that each Entity plays as an Argument in the Relationship:

  • the top node carries the meta data of the Relationship, of which the two major ones are: (i) its unique “identifier ” (with which other Relationships can refer to it), and (ii) the context (all the externally defined Entities and Relationships whose names are being used in the model of this Relationship). Other meta data in the top node are: type and provenance. In addition to the identifier (which in principle should only be computer-readable), models often carry human-readbale names and description strings, possibly in various languages. However, these are not used in linking Entities together into Relationships.
  • from the top node, there are Role edges towards each of the Entity nodes that figure as Arguments in the relationship. Each Role edge also has similar meta data properties as the top node, but the most distinguishing one represents the purpose (“role”) of a particular argument in the Relationship. This is formally represented by a specific Relationship in itself.

Each “value” in an Argument has a domain (or “universe of discourse”): the type and the set(s) of possible values that the “key” can have. In other words, that domain brings its own property data structure to each argument. Remark the recurring pattern of “identifiers”, “types” and “contexts”, in the nodes and edges of a hierarchical hypergraph. And also remark that the graph is directed : pointing from the Relationship to the Entities, and down to the latters’ proeprties.

Natural modelling levels of abstraction

“Abstraction” is a key concept in modelling, but it is hard to define axiomatically. Below, three core “meta meta” forms of modelling are described11):

  • mereology – parts: there is already quite some (mature) formalisation available in the state of the art, to structure “Entities’; for example, the Wikipedia article in the subject has a good overview and pointers to the literature. The key Relationship is has-a (also called, “has-part” or similarly equivalent names), and is-equal.
  • topology – structure of interconnections between parts: this kind of structural model is a key property of any system, and also here the state of the art insights and formalizations are sufficiently mature to have unambiguous and consistent semantics of formal models, to the extent that it is realistic to develop “standards” and “tools”.

Concretization (or specialization) can be considered as the opposite of abstraction. In this sense, raising the level of abstraction means to get more general purpose while lowering the level of abstraction means to get more specific with respect to e.g. a certain domain. It is only natural that the general purpose (i.e. higher) abstraction levels tend to leave open some semantic variability. For instance, UML (as one representative for general-purpose modeling languages) purposefully defines “semantic variation points”. These “semantic variation points” can be fixed by e.g. deriving domain-specific models (in terms of UML by defining UML profiles). In this sense, RobMoSys as well defines several levels of abstractions, with “Hierarchical Hypergraphs” and “Entity-Relation” levels on top, over “Block-Port-Connector” and “RobMoSys composition structures” and down to concrete realizations (sometimes “reference implementations”). Going gown this abstraction hierarchy also means getting more domain-specific and narrowing semantic variability.


Formalization

This section provides formal specifications for the Hierarchical Hypergraphs and for an Entity-Relation model.

Hierarchical Hypergraph

  • “a hypergraph H is a pair H = (X,E) where X is a set of elements called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or edges” Wiki:Hypergraph
  • hyperedge: each vertex in the graph can connect more than two nodes
  • hierarchy: each node or edge in the graph can be a full graph in itself

Entity-Relation Model

Entity-Relation is a specialization of a Hypergraph. Therefore, Entity-Relation conforms-to a Hypergraph.

  • entity
    • the “things”
    • entity instantiates a node of its meta-model
      • uniquely referencing an element of its meta-model
    • entity has a unique identifier
      • uniquely referencing this primitive
  • relation
    • n-ary link between primitives
    • relation instantiates a hyper-edge of its meta-model
      • uniquely referencing an element of its meta-model
    • relation has a unique identifier
      • uniquely referencing this relation
  • property
    • attribute of a primitive or a relation

Basic set of standard relations for linking different levels of abstraction

We do not introduce a RobMoSys specific definition for these relations. Instead, we just use their “common sense definition”. The following explanations are just typical “common sense descriptions”:

  • is-a
    • this is inheritance
    • an element of a model derives from an element of a metamodel
  • instance-of
    • this is often just a synonym for “is-a”
    • one talks of an instance when it is the final element in an inheritance hierarchy. What is considered a final element depends on what parts of the inheritance hierarchy you see.
  • conforms-to
    • a meta-model is a model that defines the language for expressing a model. A model represents an abstracted representation of an artefact. A model conforms to a meta-model. One model can have multiple models to which it conforms.
  • constraints
    • this is a particular relation
    • it can be applied to primitives, relations and properties

See next:

References

1)
P. P.-S. Chen. The entity-relationship model—Toward a unified view of data. ACM Transactions on Database Systems, 1(1):9–36, 1976.
2)
At more or less the same time, similar developments took place around knowledge representations via “programming languages”, such as Lisp or Prolog.
3)
T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web. Scientific American, 284(5):34–43, 2001.
4)
M. L. Minsky. A framework for representing knowledge. In P. H. Winston and B. Horn, editors, The psychology of computer vision. 1975.
5)
R. Reiter. On closed world data bases. In Logic and Data Bases, pages 55–76. 1978.
6)
S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 3rd edition, 2009.
7)
G. Engels and A. Schürr. Encapsulated hierarchical graphs, graph types, and meta types. Electronic Notes in Theoretical Computer Science, 2:101–109, 1995.
8)
M. Levene and A. Poulovassilis. An object-oriented data model formalised through hypergraphs. Data & Knowledge Engineering, 6:205–224, 1991.
9)
W3C. An overview of the prov family of documents. https://www.w3.org/TR/prov-overview/, 2013.
10)
Dublin Core Metadata Initiative. Dublin core metadata element set. http://dublincore.org/documents/dces/.
11)
P. Borst, H. Akkermans, and J. Top. “Engineering ontologies”. International Journal on Human-Computer Studies, 46:365–406, 1997.
modeling:hypergraph-er · Last modified: 2017/06/19 11:08
http://www.robmosys.eu/wiki/modeling:hypergraph-er