Modeling and Reasoning with Multirelations, and their encoding in Alloy

Peiyuan Sun, Zinovy Diskin, Michal Antkiewicz, Krzysztof CzarneckiOCL@MoDELS 2016 · OpenReview

Abstract

Standard formal modeling tools like Alloy are grounded in set theory, which inherently simplifies multiple links between the same objects into a single relation. This paper introduces a category-theoretic framework that uses spans to represent multisets and multirelations. By reifying links as unique indices, the authors enable Alloy to reason about repeated associations and complex counts without losing information during relational composition.

Introduction

In software engineering, graphical notations like UML frequently employ "non-unique" associations to model real-world constraints. For example, a retail "bundle" might contain multiple units of the same item. Standard relational logic, however, treats these as simple reachability: either an item is in a bundle or it is not. This simplification fails when business rules depend on exact counts, such as "a bundle must contain at least two dairy products."

The Multirelation Problem

When relations are composed—for instance, linking a Bundle to an Item and then to a Category—the result is often a multirelation. In standard Alloy, a "join" operation would collapse multiple paths between a bundle and a category into a single boolean connection.

UML schema for a bundle-item-category model with non-unique associations.

As shown in the schema above, the contains association is marked as "non-unique." If a bundle contains two different dairy items, a standard join only reports a single link to the "Dairy" category, losing the provenance and count required for complex business logic.

Proposed Framework: Reification and Spans

To solve this, the authors propose an index-based approach borrowed from category theory. Instead of mapping pairs to integers (a common but clunky workaround), they "reify" every link as a unique object.

In this framework, a multirelation is modeled as a Span $(A \leftarrow H \rightarrow B)$, where $H$ is a set of unique indices representing the links. Two functions, or "legs," map each link in $H$ to its source in $A$ and its target in $B$.

Instance-level representation of multirelations using unique indices for links.

In the instance diagram above, the bundle $B1$ is linked to $Bread$ via two distinct indices, $c_{11}$ and $c_{12}$. Composition of these relations is handled via the category-theoretic pullback operation, ensuring every unique path is preserved as a distinct entry in the resulting span.

Implementation in Alloy

The authors developed a library of parametric modules (mset for multisets and mrel for multirelations). These allow users to "lift" standard relations into the multirelation framework and "drop" them back when only reachability is needed. This approach is "conservative," meaning it can be integrated into existing Alloy models without disrupting standard relational logic. Furthermore, the framework provides inherent null safety; composing any relation with an empty multiset simply results in an empty multiset, avoiding common navigation errors.

Evaluation and Results

The framework was evaluated using a "Seasonal Sales" model and synthetic benchmarks to measure performance as the "scope" (the number of potential links) increases.

  • Correctness: A test suite verified the encoding against manually computed results, confirming the mathematical soundness of the pullback-based composition.
  • Performance: Analysis time scales linearly with the scope. For a scope of up to 20 unique links, analysis remains near-instantaneous (under 100ms on a standard laptop).
  • Usability: The library hides the underlying category-theoretic complexity, requiring only a single open statement to use.

Conclusion

This work provides a robust way to handle multiplicities in Alloy by staying within the "world of sets," making the logic compatible with Alloy’s core engine. While reification increases the search space for the SAT solver, it remains practical for typical software modeling tasks. Future work includes integrating this framework into the Clafer modeling language to provide native, first-class support for multirelations.

Summary updated

BibTeX
@inproceedings{sun2016modeling,
  author = {Peiyuan Sun and Zinovy Diskin and Michal Antkiewicz and Krzysztof Czarnecki},
  title = {{Modeling and Reasoning with Multirelations, and their encoding in Alloy}},
  booktitle = {OCL@MoDELS},
  year = {2016},
  url = {https://openreview.net/forum?id=cNA2dSo9jU},
}

Loading related content...

Figure