Data Provenance Prototype Challenges

How to structure built-in meta-data schema for midPoint? The metadata that we had in midPoint 4.0 (MetadataType) evolved quite spontaneously over the years. It has to be improved. We need better structure. But it looks like there is no standard for meta data. There is some work in progress (http://www.metadata2020.org/), but nothing that is ready to use.

It looks like there is almost no scholarly literature on identity provenance. Designing provenance data structures proved to be a challenge. It was more difficult than expected, several iterations were needed to get usable design draft. We need just right amount of provenance metadata to store. We cannot store everything, otherwise the data storage requirements would be unreasonable. It was also difficult to align provenance with other planned data protection features, notably lawful basis management.

Axiom was motivated by a lot of challenges with XSD, documented in blog post.

There are established ways how to update the data. There are also mechanisms for data consistency, such as pessimistic and optimistic locking. However, metadata complicate those things as well. There are cases where metadata from a new value need to be combined with existing metadata. There may be cases when metadata change while the data value does not.

MidPoint is not relying on optimistic/pessimistic locking for data consistency. It cannot rely on such mechanism, as identity management system is essentially a "distributed" integration system. Systems that are data sources usually do not provide transaction or data consistency guarantees. Target systems may be even worse in this aspect. In addition to that, midPoint often combines values from many source systems that is distributed to many target systems. This could create a massively distributed transaction. It would be a nightmare to coordinate that. Such system will not work in practice.

Therefore midPoint is using an alternative mechanism based on a concept of relative changes. Modifications are specified in form of additions and deletions that do not affect original value of an item. Such modifications are referred to as deltas. Deltas have a very nice property that they can be merged and applied in any order. The result will still be correct. This concept is very suitable for data integration and it worked for midPoint for almost a decade.

However, it is difficult to extend that concept to metadata. If the data value does not change, we have no way how to express metadata change. Yet another challenge is combination of metadata from several sources. It looks like the ideal solution would be to apply the relativistic change model to the metadata. However, that creates additional dimension inside the delta. This may be a feasible solution eventually. But it is too complex for this (prototype) phase of the project. Therefore the decision was to always replace the metadata when a value is changed. The problem with metadata-only modifications will be solved by sending a "redundant" modification of existing value to the same value, just to convey metadata modification. The "always replace" approach is opening up some possibility od metadata inconsistencies. However, chances of that happening are very small and the impact is almost negligible. Even if metadata get corrupted, midPoint reconciliation mechanism could be used to correct them.

Yet another complication is related to concept of data equality. Let’s have two values that both contain string foo, but they have different metadata. Are those values the same or are they different? It looks like the answer to this question varies according to situation. Such values are the same when we are concerned just with the data. For example presenting two values of full name to the user will be very confusing. But the values are different when we care about the metadata. For example midPoint consolidation process has to distinguish between them in order to correctly process the metadata. Overall, seeming simple concept of data equality is in fact very complex and multi-faceted problem.

Integrating meta-data mappings in midPoint proven to be more challenging than we have expected. One part of the problem was specification of metadata mappings (i.e. where to set up the mappings), but that was resolved with a relative ease. There was another and slightly unexpected aspect of the problem: value consolidation.

MidPoint is designed to work in a very generic way. It assumes that there may be many values, originating from many sources, transformed by many mappings stored in multi-value data items. The same value may originate from several sources, some values may be conditional (such as "initial" value that are set only wne no other value is set), some values may be overidden by others and so on. This creates quite a complicated system which is at the heart of midPoint’s flexibility. However, all the values must "collapse" to become an ordinary data item at the end. This final step is referred to as value consolidation.

Value consolidation is a complex process, but metadata adds additional dimension of complexity. The same value may come from several sources. While the (data) value is the same, metadata may be completely different for each source. As values are merged together in a consolidation process, metadata need to be merged too. And this is not always easy to do.

We had to adjust the design of provenance metadata to reflect the consolidation process. Provenance metadata are built into midPoint core schema. However, other metadata structures may be completely custom and there is no generic way how to consolidate them. For example, assurance metadata are likely to choose the highest assurance level to get a single-value assurance metadata for consolidated value. While other metadata types may merge values from all the sources into a multi-value metadata item, to keep track of all the sources. There is no generic way. Therefore we had to specify custom consolidation mappings for metadata types.

It was also challenging to fit this concept into existing midPoint code base. MidPoint computation engine (known as Projector) conducts the computation is several phases. Each phase had its specifics and special behavior, mostly due to historical reasons. Existing code had to be explored in depth, documented and improved before metadata consolidation code could be added.

One of the hardest and least expected challenges was certainly metadata multiplicity. It looks like metadata are inherently multi-valued, as a single data value may come from several places.

See Metadata Multiplicity Problem for detailed explanation of the issue.

We have not suspected this issues at the beginning of the project. There was nothing in the initial research that would suggest this kind of issues. We have observed first signs of this issue approximately in the middle of the project, but at that time we have thought that the issues is limited to provenance metadata. It was only quite late in the project that we have realized that this multiplicity is an inherent property of all metadata. The metadata multiplicity, the concept of yields and its relation to data protection is perhaps the most surprising discoveries in this project.

How do we display the meta-data in a way that is understandable for users? When to display meta-data at all? Provenance data can be complex and they are maintained for every value. We certainly cannot display them all the time, this would make the user interface very complicated.