iRel Interface (v1_0)

iRel Requirements
EntArr Proposal (v1 1)
"None" Type Proposal
iRel Use Cases

Given the requirements in IRel Design, we now describe the iRel interface.

Data model

There are many ways to formulate a data model for storing relations. For example, each type instance of relation in an application (e.g. mesh-geometry) could be represented by a distinct instance of the iRel interface. Or, each direction of a given relation could be a distinct relation, whether represented by a distinct iRel instance or not. The data model describes these and other specifics of how relations are described through the iRel intereface. We define the data model in iRel using the following types:

Interface type enumeration

The interfaces being related, e.g. iMesh, iGeom, iField. In higher-level languages, interface instances would be passed to iRel using some parent data type, e.g. iBase, with member functions called by iRel passing through to the concrete interface type (iMesh, iGeom). This could also be done in a lower level language, using indirection (e.g. function pointers). In practice, though, we anticipate a relatively low number of distinct interfaces being related by iRel, and in most cases those interface types will seldom change and will likely be known by both iRel and the applications using iRel. Therefore, we specify an interface type enumeration IfaceType, whose values currently include (iRel_IGEOM_IFACE, iRel_IMESH_IFACE, iRel_IFIELD_IFACE). Interface handles are specified to iRel as (iBase_Instance, IfaceType) tuples.

Relation Type

The Relation Type denotes what kind of data in one interface are related to what kind of data in another. The kinds of data being associated is Entity, and Set.

  • Entity is a basic data of an interface, for instance, mesh entity of iMesh interface, geometric model entity of iGeom interface.
  • Set is an arbitrary grouping of entities and sets with parent/child links with other sets. Relation Type with Set can be symmetric or asymmetric.
  • Symmetric (default): sets point to entities or sets on the other side (symmetric). For symmetric relation types, given an entity or set to be related, the relation has O(1) storage and retrieval cost. See Figure 1(a).
  • Asymmetric: If Set Relation Type is specialized as "BOTH", entities and sets on a "both" side point to entities or sets on the other side, and vice versa. See Figure 1(b).

FIXME: insert figure
(a) Entity-Set Relation Type (b) Entity-Both Relation Type
Figure 1: Entity-Set/Both Relation Diagram

There are the two important features of relation type with Set.

First, the relation is unique; an entity or set on one side and an entity or set on the other side have unique relationship to each other.

Second, in case of Entity-Both relation type, the entity on Entity side doesn't point to entities on Both side; It access to entities on Both side only through a uniquely associated set. However, entitites on Both side maintain up-to-date relations to the entity on Entity side.

In case of Entity-Both relation type where an entity a currently related to set A of N entities, when entity a is related to another set B of M entities, the following are performed;

  • Remove relation of entity a and set A (a to A, A to a)
  • Remove relations from each entity in set A to entity a
  • Build relation of a and set B (a to B, B to a)
  • Each entity in set B points to entity a

For instance, for the entity a on Entity side is related to set A of content {x, y, z} on Both side, when a relation data of entity a and set B of content {l, m, n} is added, the following are performed

  • Remove relation (a to A) and (A to a)
  • Remove relation (x to a), (y to a), (z to a)
  • Build relation (a to B) and (B to a)
  • Build relation (l to a), (m to a), (n to a)

When a relation data of entity a and entity l is added, the following are performed

  • Find a set A related to entity a.
  • Add entity l to set A
  • Build relation (l to a)

When a relation data of entity b and entity x is added, the following are performed

  • Find a set B related to entity b. * If no set exists, create a new set B and create relation (b to B) and (B to b)
  • Remove entity x from set A and add x to set B
  • Replace relation (x to a) with (x to b)

iRel supports services for relating two independent interfaces where the relationships are constructed and managed fully by iRel. Set relation type is ideal for implementations where the component interfaces have no relationship information. iRel also supports access to relations that may already be inherent to component interfaces that naturally maintain relations. For example, a number of implementations store the classification (the association between a geometric model entity and mesh entities) in the mesh and geometry model implementation. In this case, the role of iRel is, instead of on-the-fly construction and maintenance of the relations between two interfaces, merely providing the access to existing relations (in other words, getting and setting existing relations).

As a Relation Type has two sides, one for each side of the relation, the following Relation Types are available:
  • Entity-Entity
  • Entity-Set
  • Set-Set
  • Entity-Both
  • Set-Both
  • Both-Both

In case if Entity-Entity, Entity-Set, Set-Set relations, entity or set in iface1 are related directly to entity or set in iface2; for those types of relations, it is assumed that, given an entity to be related, the relation has O(1) storage and retrieval costs.

Relation Pair

An iRel Relation Pair is an object in an iRel instance; it stores a relation of a specific Relation Type between one interface (iface1) and another (iface2). A Relation Pair is created and used analogous to a Tag in iGeom or iMesh, where it is first created, then given a value for various entities. A Relation Pair stores the interface handles it relates (in the order they were specified when the Relation Pair was created), and the Relation Type. A Relation Pair is passed through iRel in the form of a PairHandle.

Relation Pairs can be symmetric or asymmetric, depending on the type. They can be consistent or inconsistent, with the latter being used in coordination with lower-level functions in iRel, e.g. when a mesh is being adapted or generated.

Relation side

Used in query functions to denote the starting side of the query; side1 implies a query from iface1 to iface2, while side2 implies a query from iface2 to iface1.

API

The iRel API as currently specified can be found in the ITAPS repository, at iRel.h This section describes the API in general terms.

  • Create relation pair
  • Get relation
  • Set relation
  • Remove relation
  • Inferring relation and relation type
  • Changing relation type

Create

The function for creating a specific Relation

Get

Relations can be retrieved given a Relation handle, an entity, set, or arrays of them, and a side, which
specifies the starting side of the query. The six get functions are available.

  • iRel_getEntEntRelation
  • iRel_getEntEntArrRelation
  • iRel_getEntArrEntRelation
  • iRel_getEntSetRelation
  • iRel_getSetEntRelation
  • iRel_getSetSetRelation

Set

Functions are available for setting individual relations. These functions are somewhat low-level, and should be used with care, as they have the potential for invalidating the relation data with no way to recover. It is expected that at least one application will set relations at some point in the lifetime of
entities being related, and it is these relations that are inferred by later applications. The six set functions are available.

  • iRel_setEntEntRelation
  • iRel_setEntEntArrRelation
  • iRel_setEntArrEntRelation
  • iRel_setEntSetRelation
  • iRel_setSetEntRelation
  • iRel_setSetSetRelation

Since the relations are unique, the first call of set relation function sets an initial relationship. From the second call of set relation function, the existing relationship is reset (removing old relationship, adding the new one).

Remove

Given a relation handle, an entity, set, or arrays of them, and a relation side, the six rmv functions remove the the relation.

  • iRel_rmvEntEntRelation
  • iRel_rmvEntEntArrRelation
  • iRel_rmvEntArrEntRelation
  • iRel_rmvEntSetRelation
  • iRel_rmvSetEntRelation
  • iRel_rmvSetSetRelation

Infer

This function infers a Relation in the interfaces that Relation pertains to. Inference can be for
individual entities or sets, or for the entire database stored in the interfaces.

Change type*

Functions must be added for changing type; this flexibility can result in significant memory savings, e.g. when changing from a -Both to a -Set type after smoothing or mesh adaptation is finished. Change type function is not used for EntityArray relation type since relations are not created and maintained at the iRel level.

General discussion of issues and rationale

Specific issues have arisen in the development of iRel which are described further below.

Storage: In some implementation of iRel (e.g. Lasso), it is expected that relations are established when a mesh is generated, and inferred by later applications. That is, the implementation assumes that relations do not get stored with the data in a given interface when the save function is called on that interface. This is the case even though Lasso uses tags in the interfaces being related, and tags are usually stored during a save. The rationale for this is that relation data stored on a given entity refers to data in a different interface, and that data cannot be saved and restored reliably. This is in contrast to storing Entity Handle-type tags in an interface, where these tags refer to entities in the same interface. See footnote1 for further discussion.

Inference method: Since we assume iRel does not store its relations data directly with the interface data, we require that relations be inferred. The method used to infer relations depends on the data being related, which in turn can depend on the implementation of the interface that data is read from. It is an open issue how to specify criteria for how to relate entities between interfaces, in a way which is interoperable. One obvious requirement, or at least a recommended path forward, is that those criteria be specified in terms of the data model used in iBase. In that language, the criteria used by Lasso to relate entities between iGeom and iMesh can be described as:

Relate e(iGeom), s(iMesh) such that:
  1. getEntType(e) val(GEOM_DIMENSION)_s &&
  2. val(GLOBAL_ID)_e val(GLOBAL_ID)_s

Here, e and s denote entity and entity set; getEntType(e) is the unary result of a function in iGeom; val(xxx) is the value of tag xxx on the indicated entity set. Thus, the elements used to specify the relation criteria include entities, sets, tags and possibly values on those things, and unary function results for those things. We have delayed proposing an interface for that sort of specification until such time as another implementation of iRel emerges.

Note, we believe there is a place for implementation-specific iRel instances, which will probably have embedded relation criteria specific to particular data formats. These versions of iRel will probably not be interoperable with different implementations of the interfaces being related, but will still be useful to applications needing to query the interfaces for which these iRel instances are developed. The iRel API has been modified to allow the iRel implementation to determine the relation type during the infer function.

Interface-specific functionality and API: Another way to approach an iRel specification would be to write it in terms of the specific data being related. For example, there have been many requests for specific functions for relating mesh and geometry. We assert that this should not be the basis for iRel because:

  1. This would be shortsighted, as it would not address relations with other interfaces, planned (e.g. iField) and unplanned (e.g. materials). As a consequence, iRel would have to be modified before any new interface could be treated by iRel. This would go against the principle of versatility of interfaces. Also, given the difficulty of negotiating interfaces, it should not be assumed that this extension would be a trivial matter.
  2. Narrowing the scope of iRel to only mesh and geometry is actually a relatively minor issue; the deeper issues have to do with the data model and communication between iRel and other interfaces in terms of sets and tags. Choosing to narrow the scope would not address these other issues.
  3. Focusing specifically on geometry and mesh, rather than considering it as an abstract problem, would likely leave out functionality important to other interfaces. For example, the current implementation of iRel, Lasso, does not treat relating tags between interfaces; yet, that is one of the obvious uses of iRel in the context of iField. No matter what the resolution of this issue, a recommended follow-up would be to review iRel for completeness while considering other interfaces.

It is recommended that if an API specific to geometry-mesh relations is developed, it be offered as a service on top of iRel, rather than part of the iRel specification.

Serving and maintaining relations under mesh modification: Services performing mesh modification, e.g. AMR, have very specific requirements for a relations interface. Mesh to geometry relations need to be accessed from a mesh entity level with O(1) complexity, and frequent addition and removal of mesh makes it difficult to maintain sets efficiently. This could make serving the geometry-mesh relations in terms of sets inefficient, due to the difficulty of maintaining sets under modification. Looking at this situation from the AMR service point of view, though, it seems clear that one of the following will be true:

  1. The lists of mesh entities related to geometry entities become out of date as entities are created and destroyed during the adaptation process; these lists are updated after mesh adaptation is completed.
  2. The lists of mesh entities related to geometry entities are cleared before adaptation, and repopulated after adaptation is completed.
  3. The lists of mesh entities are updated as entities are created and destroyed during adaptation.

If 3 is true, then the implementation already has the basis of a set which performs efficient removal of entities. If 1 or 2 is true, then the implementation allows for the possibility of an inconsistent relation state between geometry and mesh; this could also be true of a relations interface phrased in terms of sets. In all cases, there is nothing which prevents the implementation from returning set objects which have constraints which are more strict than generic sets themselves. These constrained sets would return errors if unallowed operations were attempted on them by applications.

Entity array-based communication of relations: Set/Both relation types imply that entity sets are used to store relations. This may constrain the implementations that do not use sets to store the relations. To accommodate these implementations, iRel also provides Entity Array relation type with which convenient access to collections of existing relations is provided in the form of c-array (set, rmv) or iBase_Iterator (get). All iRel implementations are expected to support both Set and Entity Array relation types, while some implementations implement the corresponding set-based functions and some don't. The iRel_INVALID_TYPE error code is used when a setbased (resp. Entity Array) function is called on Entity Array (resp. Set/Both) relation type. (11/7/10)

The term “Relation” and type name iRel_RelationHandle is confusing: These terms are often confused with the iRel Instance, and the value of a given relation between specific entities. We will now refer to such things as “Relation Pairs”, which are handled through the interface using the type name iRel_PairHandle. The description of these things in the Data Model section of this document has been changed accordingly. (8/24/2010)

Discussion notes

1 Note 1

MCM: This problem exists in iField. There is a discussion about it at the bottom of this page [[http://redmine.scorec.rpi.edu/projects/itaps/wiki/Parallel_iField]]. We need to be able to store DOFs from fields and later read them back and re-build the associations of DOFs to mesh entities. In particular, one cannot assume the ordering of entities in iMesh remains same across save/loads. So, iField will need to come up with a way of maintaining the mapping explicitly across save/load.

Tim: Interesting. I've believed for a long time that specifying the criteria used for inference of relations between geometry and mesh, using a method described in the next paragraph, could be abstracted and applied more widely; here Mark implies something like that would be needed to relate DOFS too. Critical to solving this extensibly, and interoperably, will be the ability to specify the inference in terms of the data models of each interface. For example, I specify geometry-mesh inference in terms of matching iGeom/Entity-iMesh/EntitySet && iGeom/EntityType-iMesh/val(GEOM_DIMENSION) && iGeom/val(GLOBAL_ID)-iMesh/val(GLOBAL_ID).

Seegyoung: Isn't it the iMesh_save/load issue?

Tim: No, since in this case iField wants to save data that points into data in another interface. If it were pointing into its own data, that would be the same as the save/load issue.

Tim: I think the solution in this case is to embed the information using tags and possibly sets. That is, if you have dofs that need to point to mesh entities, come up with some dof numbering scheme, and save those numbers to both the iField data and the iMesh entities. Sets could be used to decrease the searching over mesh entities (though maybe getting entities that are set with a given tag would be just as efficient). Then, when iField and iMesh are restored later, you would match the dof to the mesh entity using a rule DOF/val(DOF_NUMBER) - ENTITY/val(DOF_NUMBER).

Seegyoung: For matching mesh entity and dof order between file I/O, in addition to tag/set, there can be two more options. #1 From our experience, regardless of iField, one of fundamental requirements in mesh I/O was maintaining mesh (at least) vertex order between mesh save/load or at a minimum, telling the mesh vertex order in loading, if the order preservation is not available. From that perspective, I see this is more about iMesh_save/load issue rather than iField_load/save issue so field users are free from handling dof/mesh entity by themselves using tag or whatever in-between file I/O. #2 (similar to the matching scheme between iGeom and iMesh), introducing some common matching scheme between iMesh/iField.

Tim: I think what I was suggesting was #2, matching DOF/val(DOF_NUMBER) to ENTITY/val(DOF_NUMBER); that way you're not sensitive to ordering changes.

Seegyoung: Ok, going down further, there are two methods in support for matching schemes; with or without tag/set. E.g. GMI/FMDB can supports iRel_infer (iGeom, iMesh) through iMesh/val(GEOM_DIMENSION) && iGeom/val(GLOBAL_ID)-iMesh/val(GLOBAL_ID) without tag/set. And I expect we can support matching DOF/val(DOF_NUMBER) to ENTITY/val(DOF_NUMBER) without tag/set, implying no tag file i/o incurred by entity-dof matching across file i/o.

Tim: The notation I was using here was Interface/Thing/Data matched to Interface/Thing/Data, where Thing can be Entity, Set, or DOF, and Data can be a tag value (notated with val(TagName), or the value returned by a function or enum, like EntityType. Saying that we're inferring things in terms of Interface/Thing/Data implies it's being done through the Interface APIs. So, if you're not using Tag to get something like a DOF number or a global id, there has to be something else in the interface to support getting that data. I don't see anything else in iMesh that can do that. Now, if you're doing this all below the interface, then that's fine, but then you're sacrificing interoperability (i.e. your iMesh implementation is interacting with your iField implementation through an interface other than iXxx).

Seegyoung: Yes, I don't see anything in iMesh that can do that either, so it seems tag is only way which satisfy interoperability for now. However, we may want to continue group-wide discussions for simpler way for matching scheme for various interfaces across file i/o. For instance, introducing iMesh_getVtxID which returns "locally" unique read order of vertices for given root set (iMesh) or part handle (iMeshP) will ease a lot of tag management burden across the file i/o from the users, and save i/o cost (this is what FMDB does).