EntArr Proposal (v1 1)¶
iRel 1.0 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 needs to support 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).
- We propose Entity Array as a third kind of data that iRel supports for efficient access to existing relations with multiple data on a side. Contrary to Set, Entity Array is not an actual data object maintained in iRel, but a conceptual method to avail the application of access to the relations stored in underlying interfaces without a extra cost to maintain relation data in iRel. As depicted in Figure 2, each entity in Entity Array side has an access to an entity on the other side uniquely as one-to-one mapping and an entity on Entity side has access to multiple entities on Entity Array side (symmetric).
Entity Array merely provides a way to access an iterable collection of entities stored in the underlying interfaces without maintaining relationship or status in iRel. See footnote2 for discussion.
Since Entity-Entity Array relation type doesn't maintain relationship or status in iRel,
FIXME: insert figure
Figure 2. Entity-Entity Array Relation Diagram
This implies that, unlike Set, for an entity a, which is related to the M entities, setting relations of entity a with N entities in an array doesn't mean replacing the current relations of (a and M entities) with relations of (a and N entities). Instead, relations of (a and M entities) and relations of (a and N entities)
are merged so entity a will have relations with total M+N entities and each of M+N entities will point to entity a.
For some implementations where memory efficiency is crucial or information of both directions (a to b and b to a) is not required for specific application, storing and maintaining the relation up-to-date for both directions is not desirable. Therefore, some implementations chose to store only one-way information (e.g. a to b) and maintain it up-to-date then the other way information (b to a) is constructed on-the-fly when requested.
For example, up-to-date classification should be tracked during the swapping operations. However, maintaining up-to-date reverse classification during this process is not needed. Up-to-date reverse classification can easily built after all mesh modifications by a single traversal of the mesh which is much faster than updating on the fly when using a compact representation of reverse classification.
To account for various implementations in term of storing relation data (two directional information or one directional information) and level of up-to-date information maintenance during the data modification, and to be consistent with Entity-Both relation type where entity on Entity side doesn’t directly maintain relationship with entities on Both side, Entity-EntityArray relation type requires maintaining up-to-date relations only from entities on EntityArray side to entity on Entity side.
Figure 2 depicted the Entity-EntityArray relation type where the relation from an entity to entities is illustrated with dotted line meaning that maintaining up-to-date information from entity to entities is optional in underlying implementation. Even though maintaining up-to-date "entity to entities" relation is not required, the interrogation of relation information of entity on Entity side should return the up-to-date information on entities related to.
Suppose the entity a on Entity side is related to entity array [x, y, z] on Entity Array side, such that there are three one-to-one relationships (x to a, y to a, z to a) and one one-to-many relationship (a to [x, y, z]).When a relation data (a, [l, m, n]) is added, the following are performed
- Build relation (l to a), (m to a), (n to a)
- [OPTIONAL] Add relation (a to l), (a to m), (a to n) to existing relationships of a so now a has
relations to six entities, x, y, z, l, m, and n (See footnote3)
- Build relation (l to a)
- [OPTIONAL] Add relation (a to l) to existing relations of a so now a has relations to [x, y, z, l]
- Replace relation (x to a) with (x to b)
- [OPTIONAL] Remove relation (a to x) from the relations of a so now a has relations to [y, z].
- [OPTIONAL] Add relation (b to x) to existing relations of b
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.
The Relation Type with EntityArray and Set/Both are not allowed since they are defined to support different interface designs in terms of relation management; EntityArray for interface which stores relation data inherently and Set/Both for interface which doesn’t maintain relation data inside the interface. (See footnote4 for further discussion)
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.
In case of Ent-EntityArray relation type, if iRel_getEntEntArrRelation uses temporarily created C-array for returning entities, when any entity in C-array is deleted or modified, C-array will contain invalidated entity handle. To avoid invalidated entity handle in entity array while accessing/iterating the entity array through index and avoid memory allocation for temporary array in iRel, iRel_getEntEntArrRelation uses iBase_EntityIterator instead of temporary c-array of entities, where
iBase_EntityIterator is a wrapper of iterator implemented in underlying interfaces with "no invalidation with entity removal".
iRel_getEntEntArrRelation and iRel_getEntArrEntRelation are available only for a relation handle with Entity Array. iRel_INVALID_TYPE error is got if those two functions are called with a relation handle with Set.
iRel_getEntSetRelation, iRel_getSetEntRelation, and iRel_getSetSetRelation are available only for the relation handle with Set/Both. iRel_INVALID_TYPE error is got if those three functions are called with a relation handle with Entity Array. See footnote5 for further discussion.
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_setEntEntArrRelation and iRel_setEntArrEntRelation are available only for a relation handle with EntityArray. iRel_INVALID_TYPE error is returned if these functions are called with Set/Both relation type.
iRel_setEntSetRelation, iRel_setSetEntRelation, and iRel_setSetSetRelation are available only with Set/Both relation type. iRel_INVALID_TYPE error is returned if these three functions are called with Entity Array relation type.
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).
Given a relation handle, an entity, set, or arrays of them, and a relation side, the six rmv functions remove the the relation.
iRel_rmvEntEntArrRelation and iRel_rmvEntArrEntRelation are available only with Entity Array relation type. An error is returned if these two functions are called with Set/Both relation type.
iRel_rmvEntSetRelation, iRel_rmvSetEntRelation, and iRel_rmvSetSetRelation are available only with Set/Both relation type. An error is returned if those three functions are called with Entity Array relation 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¶
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)
2 Note 2
Tim EntArr-based relations incur a storage cost per model entity of O(N), where N is the number of mesh entities classified on that model entity. This is true because the entities on the EntArr side of a relation are passed back to the application in the form of a C-based array of entities, and by definition those arrays do not have state that the application can query. Thus, the only way to query relations from the mesh side is on individual entities. Furthermore, the retrieval cost for these relations is required to be O(1), which implies no searching.
- avoid extra memory allocation for temporary array in iRel
Seegyoung: I did wording for clarity. The proposed EntArr doesn't require extra c-array at the iRel level; iRel_getEntEntArrRelation returns iBase_EntityIterator instead of extra c-array to
- avoid invalidated entity handle in entity array during traversal due to entity addition/removal
Tim Ok, thanks for clarifying. Then, if we return iterators for EntArr-based relations, how does this compare to last major change, where we added functions to return relation data in the form of iterators? In that case, is it still assumed that there is still a "real" set represented in iMesh? Where "real" means one that can be queried using the normal set query functions in iMesh? I thought that that change was for the purpose of allowing the implementation to not represent a real set down in iMesh. Mark Beall, when you started implementing after that last major change, I thought that's what you were doing.
Mark Beall: Yes, that's the intent of what we are planning to do (haven't done it yet since I'm not sure all of those changes made it into iRel and I think there were still some small issues that needed to be cleared up - don't remember what those are at this time).
3 Note 3
Tim In the discussion about adding the relation (a, [l, m, n]), another step must be added at the front, to check whether l is related to b, and removing it if so. Checking is guaranteed to be O(1); the cost of removing will depend on the implementation, but at best can be O(1) (because the implementation is not required to store the Ent->EntArr relation, there will be no cost for updating it).
Seegyoung: Similary to Ent-Both relation, relation from entity on EntArr side to entity on Ent side is unique. Therefore, setting relation (l to a) will update existing relation of l, if any.
Tim: Ok, yes.
4 Note 4
Tim The document contradicts itself on whether entities on the Ent side of an Ent-EntArr relation are required to store relations. On the one hand, it is stated that the implementation is not guaranteed to store this information. On the other hand, queries from either side of the relation can be satisfied in O(1) time. If the relation isn't stored on the Ent side, a search over entities on the EntArr side is required, which will have time complexity O(inf), where inf is the total number of mesh entities in the mesh database (assuming that's what's on the EntArr side). Because applications cannot assume that these relations are stored on the Ent side, they need to assume the worst to avoid O(inf) scaling on every query from the Ent side of the relation. That will add a great deal of management responsibility on the application side, possibly (e.g. under mesh modification) amounting to a re-implementation of iRel in the application.
Seegyoung: You were right. I fixed the contradiction. Ent-EntArr cannot satisfy O(1) time for getting relation from entity to entities since its storage is optional.
Tim: Ok, thanks. We should state somewhere, besides in this discussion thread, that the query cost from the Ent side will be O(inf). I'm open to suggestion on where that should be; maybe in the section just above this comment?
Seegyoung: Don't we also need to specify the query cost #1 for entity in Ent side for Ent-Set/Both? #2 for entity in Set/Both side for Ent-Set/Both
Tim The proposed addition to iRel will result in two non-interacting versions of an iRel interface, one that supports Ent, Both, and Set, and the other that supports Ent and EntArr.
By definition, EntArr-type relations cannot interact with Sets, and there is no functionality supported for switching between EntArr-based relations and other types. This will result in either non-interoperable solutions, or double the effort on the application side to work with iRel.
Tim: Note that this last comment is a very important point, and not having a response to it makes your proposal a non-starter. One way to reconcile the problem would be to support functionality to change from Ent/Set/Both to EntArr; this doesn't seem like it would negatively affect the rest of the EntArr proposal, either.
Seegyoung: The concern of "lack of interoperability" should be discussed regardless of "Set/Both" or "EntArr". I don't expect iRel Set/Both even would work for CGM and FMDB pair as long as getEntSetRelation returns iBase_EntitySetHandle (entity set doesn't reflect the up-to-date status of relations stored in underlying implementations so mesh adaptivity code cannot rely on iRel). It's not clear why the functionality supported for switching between EntArr-based relations and other type is important or necessary even though interchangeable "Entity Array" and "Set" result in the following issues.
Tim: I'm not sure it even makes sense to discuss "relations stored in underlying implementations" in the context of CGM + FMDB, since neither is coded to work with the other. But anyway...
Being able to switch between Ent/Set and EntArr would be crucial, for the following reason. Say your adaptivity service is implemented to use EntArr-type relations, and I want to use that service on my existing database, which has Ent/Set relations. I have two choices. Either I re-implement your service to also handle Ent/Set relations (which would to me indicate a failure to achieve interoperability). Or, I would insert a single call to change the relation type of the data from Ent/Set to EntArr, then use your service as-is (interoperably).
Seegyoung: EntArr type with non-interoperable EntArr/Set does not mean two parallel iRel interfaces because Lasso and GRM have to support both Set/Both and EntArr functions by tweaking its own favored type a bit. This means application program implemented with EntArr-type (resp. Set/Both) relations will be running with Lasso's iRel (resp. GRM's iRel). Based on this fact, interoperability between EntArr and Set is not needed and using EntArr or Set is at user's choice. And this approach is consistent with what's taken in iMesh in terms of providing interoperability between various implementations; using entity set or not in iMesh is at user's choice and application written with entity set runs on top of FMDB.
Tim: Ok, so consider the following. A MeshAdapt service picks up a geometry/mesh/relations collection of data through iGeom/iMesh/iRel. The MeshAdapt service is implemented in terms of EntArr relation type. MeshAdapt tells iRel to infer the relations, and iRel comes back with a relation of type Ent/Set. What does MeshAdapt do with that? There's no change function that tells iRel to convert it to EntArr, so it's stuck.
Seegyoung: It's not clear how "inference & change" method works (helpful) for interoperability and being truly generic relation managers of various implementations. For instance, iGeom-iMesh relation is known to be entity-entities and iField dof-iMesh vertex is known to be entity-entity. Why do we need to infer the relations between two (or more) interfaces although desirable or needed relation type is known on user's end? Alternatively, instead of inference/change, "set" seems to be more general approach so when setAllRelations(iGeom, iMesh, desirable relation type) is called upon, iRel implementation does whatsoever infer or build from scratch to meet user's request. To be truly general iRel, the iRel users don't have to know if the underlying interface is based on set, or both or non-set (EntArr). All they may want is to set/get relations with desirable type (set or array) between multiple interfaces where the relations are either entity-entities, entity-entity or entities-entity; using itaps set or no for entities is at users' choice similarly to we can use either "stl vector" or "c-array". I will spend some more time on all "infer" functions to clearly understand their necessity and your explanation will help me save my time since it's not stated any where.
Tim: See the section above starting with "Inference method" for an example of how inference criteria can be specified in terms of our current iMesh/iGeom data model. A iGeom-iMesh relation isn't "known to be" anything right now; some represent it only as entity-entities, while others represent it as entity-set or entity-both, depending on application requirements (see the original discussion of the Change Type requirements for details).
[Issue #1] "iRel_getEntEntArrRelation is identical to calling iRel_getEntSetRelation and iMesh/iGeom_getEntities". Currently, when iRel_getEntEntArr is called on CGM/MOAB data, the entity array returned is the content of the set related to the entity. Correspondingly, iRel_setEntEntArrRelation is defined to update the content of the related set to contain new entities. The specification is ambiguous if there's no set associated with the entity; return an error or create a new set.
Tim: Actually, this is quite untrue. By definition, iRel_getEntEntArrRelation is O(inf), as discussed before, because Ents on the Ent side do not store the collection, while iRel_getEntSetRelation is O(1) + O(getEntities) (which, if you're using vector-based sets, is O(1) total). I'll go back and address the ambiguity in my next modification.
Seegyoung: The issues 1-4 are based on iRel v1.0 which support interoperable EntArr and Set while there's no EntArr relation type.
Tim: Ok, I see. Then this issue is addressed by Jim's suggested change too. This is another example of why we need to separate discussion of v1.0 from that of 1.1.
[Issue #2] Relating one entity to many sets can be done by relating one entity to one set and have that set contain other sets. The problem arises on getting multiple sets related with the entity; it can be either by calling * iRel_getEntSetRelation and iMesh/iGeom_getEntSets OR * iRel_getEntEntArrRelation and iMesh/iGeom_getEntSets (INCONSISTENCY)
Tim: Two comments. First, I believe Jim brought this issue up awhile back too; I think his suggested fix was to not support iRel_getEntEntArrRelation for ENT/SET and ENT/BOTH relations, and I agree with that approach (the cost is one extra call, to iMesh/iGeom_getEntSets or iMesh/iGeom_getEntities). Second, iRel_getEntEntArrRelation wouldn't work here, since that wouldn't return any sets. So, I think this ambiguity (rather than inconsistency) is pretty easy to fix too. Recall that we were told to wait with those suggested fixes until we resolved this discussion, but maybe we should incorporate those into this one, to resolve some of these issues.
[Issue #3] For Entity-Both relation type, iRel implementation should support twelve possible combinations of two set functions, three get functions and two remove functions seamlessly. If get/set/rmv are not matching functions (e.g. calling iRel_getEntArrRelation, iRel_rmvEntSetRelation, and iRel_setEntEntArrRelation), the data conversions in-between get/rmv/set operations are inevitable.
Tim: When you say the 12 possible combinations, is this the argument you've raised about needing e.g. getEntSetRelation and getSetEntRelation? If so, please go back and review the switch_order argument to the various functions. That reduces by half the number of functions you need (and why I think it's the right way to go, despite the fact that it's a bit confusing). That said, I think this issue is resolved the same way as #3 is, as proposed by Jim awhile back. That is, we propose that for Ent/Set and Ent/BOTH relations, that getEntEntArr and getEntSetArr not be allowed (i.e. generate error). The cost of this is an extra call to iMesh/iGeom_getEntities or _getEntSets, but I think that's acceptable.
[Issue #4] iRel relations are unique. In case of Set/Both relation type, iRel_setEntSetRelation resets a relationship (removing old relationship, adding the new one). Therefore, when we set the classification of newly created mesh entities during the mesh modification with set, mesh entity set to be related to the model entity shall contain all other mesh entities classified on the model entity as well as newly created entities and this way, reverse classification is always maintained up-to-date.
Tim: I'm not sure what your point is here. However, you should probably use a term other than unique here, at least for EntArr-type relations, since in that case relations aren't unique (i.e. Ents are related to more than one Ent on the EntArr side). Note that this example is why something like EntArr has merit, or, as another solution, motivates the need for inconsistent or non-up-to-date relations on the model side.
Seegyoung: In summary, the iRel api is supposed to be a complete set of functions necessary for being relation-managing component for relating implementations with various designs. Between two iRel approaches, using Set/Both or EntArr is at user's discretion. Our responsibility as for the implementation provider is to make our relation s/w (e.g. Lasso, GRM-Generic Relation Manager) to work in either case (Set/Both or EntArr). In case of iMesh, FMDB provides all iMesh entity set functionalities even though we do not expect any of our adaptivity application codes won't rely on iMesh entity set. By the same token GRM would support both Set/Both and EntArr even though it favors EntArr.
Tim: But wait a minute... according to your description, it's not at the user's discretion, because relations are "a conceptual method to avail the application of access to the relations stored in underlying interfaces without a extra cost to maintain relation data in iRel." And, again, as currently proposed, adding EntArr would in effect result in two parallel interfaces to relations, corresponding to exactly two implementations. That's not interoperable; we might as well call them iRel1 and iRel2 (or maybe just Lasso and GRM?).
5 Note 5
Tim There is a contradiction in what is returned when querying an Ent for the related EntArr. In one place it is stated that this communication is in the form of C arrays, which have no state, while in another it states that EntArr-based iterators are used (which do have state). Furthermore, these iterators are required to implement "no invalidation with entity removal" semantics. Since iRel does not have functions for deleting entities, this has the effect of either a) binding the implementation of iRel to that of iMesh, so that the iRel-based iterator can be updated upon entity deletion; or b) imposing extra constraints on the implementation of these iterators, such that they can be notified by the iMesh implementation when enities are deleted.
[Clarification: a subsequent read of Seegyoung's document seems to indicate that the iterators returned are implemented in the underlying interface (e.g. iMesh). But, as specified, iMesh does not have iterators over anything other than sets (with a special case of iterators over the root set). Thus, I don't see any way to support these iterators unless the underlying thing being iterated is an iMesh set, or unless we expand the functionality of an iterator.]
Seegyoung In setting/removing the relations of entity-entities, c-array is used to holding input entities on EntArr side. However, in getting the relations of entity-entities, iBase_EntityIterator is used and it's not presumed that Entity iterator is either iMesh root set or ent set iterator; it is a wrapper of any iterator which can be type casted to "iBase_EntityIterator". In case of CGM-MOAB, it is supposedly entity set iterator. In case of GMI-FMDB, it is a root set iterator. I think we need further discussions on issues of invalidated entity set handle with mesh modification. FMDB's iterator is designed to be valid even with mesh modification.
Tim: While I have reservations about calling these things iBase_EntityIterator's, a quick review of iMesh and iMeshP indicates that there's some precedent for this kind of thing (e.g. they're used to iterate over entities in Parts in iMeshP).
Tim: Also, if a c-array is used to pass in entities from the EntArr side for which we're setting/removing relations, we don't place any constraints on those entities having to be from the same (collection?) over which a given iterator iterates, right? That is, we're not requiring those entities to be classified on the same entity from the Ent side?
Tim: I agree we need further discussions on stability of iterators through mesh modification. I'm preparing some information on that, and will log it when it's ready.