Algebra of Modular Systems: Containment and Equivalence

Andrei Bulatov, Eugenia TernovskaAAAI 2021 · DOI

Introduction

Modern software engineering increasingly relies on the integration of heterogeneous, knowledge-intensive components. In declarative computing, it is common to combine diverse technologies—such as Answer Set Programming (ASP), Integer Linear Programming (ILP), and Constraint Satisfaction Problem (CSP) solvers—into a single, cohesive system. However, formally describing the interactions between these disparate modules and verifying their properties remains a significant challenge.

The "Algebra of Modular Systems" (AMS) addresses this by providing a formal framework to compose these components. A central question in this framework is the problem of containment and equivalence: how can we mathematically determine if one configuration of modules is logically contained within, or equivalent to, another? This paper explores the complexity of these relationships, identifying both the theoretical limits and practical subsets of the algebra.

The Algebra of Modular Systems (AMS)

The AMS framework "lifts" the principles of Codd’s relational algebra—the mathematical foundation of SQL—from operations on individual data tables to operations on classes of structures. This allows for a language-independent method of composing modules.

Abstract vs. Concrete Modules

The framework distinguishes between two layers:

  1. Abstract Modules: These serve as the algebraic "blueprints," defining the logic and structure of the system.
  2. Concrete Modules: These represent the actual implementations or solvers that execute the logic.

To bridge the gap between these algebraic expressions and concrete model theory, the authors introduce the Power Structure construction. This construction represents all possible interpretations of a module, allowing the algebra to treat complex logic solvers as relational entities.

Conjunctive Compound Modules (CCM)

While the full AMS is highly expressive, the authors identify a restricted but practical subset known as Conjunctive Compound Modules (CCM). This fragment utilizes a limited set of operations: projection, intersection, and selection.

CCMs are analogous to "conjunctive queries" in database theory. The core technical contribution of this research is the Homomorphism Theorem, which proves that checking containment between two CCMs can be reduced to finding a homomorphism between two specific relational structures. This effectively generalizes Chandra and Merlin’s "Magic Lemma" from database theory to a higher level of abstraction, treating interconnected solvers as a single relational structure.

Complexity and Results

The paper provides the first rigorous complexity analysis for checking relationships between compound modular systems. The results vary significantly based on the scope of the algebra used:

  • Undecidability of the Full Algebra: For the unrestricted algebra, checking if two modular systems are equivalent is proven to be undecidable. This is demonstrated by reducing the problem to the Finite Satisfiability problem of first-order logic.
  • NP-Completeness for CCMs: For the CCM fragment, the containment problem is shown to be NP-complete. While NP-complete problems are computationally difficult, this is a positive result in this context because it allows the problem to be offloaded to modern, high-performance SAT solvers.
  • Tractable Subsets: The authors further identify specific structural conditions, such as bounded treewidth or acyclicity, under which checking containment becomes solvable in polynomial time.

Practical Implications: Substitutability

By formalizing containment ($M_1 \sqsubseteq M_2$), the paper establishes a mathematical basis for substitutability. This allows engineers to determine when one module or sub-system can be swapped for another without altering the overall logic of the system. This is critical for optimizing modular systems and ensuring that updates or solver changes do not introduce regressions.

Limitations and Future Work

Despite these advancements, the current AMS framework is primarily "static," viewing modules as sets of structures. Future research is needed to develop a "dynamic" version of the algebra that explicitly handles input/output flows, similar to information flow logic.

Additionally, while the complexity bounds for CCMs are established, the authors suggest extending this analysis to "Unions of CCMs," mirroring the "Union of Conjunctive Queries" (UCQ) class in database optimization. Finally, the transition from theoretical complexity to practical application will require the development of compilers and reference implementations for these algebraic expressions.

Summary updated

BibTeX
@inproceedings{bulatov2021algebra,
  author = {Andrei Bulatov and Eugenia Ternovska},
  title = {{Algebra of Modular Systems: Containment and Equivalence}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16775},
}
Figure