.. _DexExplosion:

Combinatorial Explosion
-----------------------

Consider an :ref:`aggregation function <DexAggregation>` f that maps the
values of the attributes X\ :sub:`1`, X\ :sub:`2`,..., X\ :sub:`n` to
values of aggregate attribute Y.

.. image:: images/FunctXnY.png
   :alt: Function Y=f(X1,X2,...Xn)

In :ref:`DEX <DexMethod>`, an aggregation function maps all the *combinations*
of the lower-level attribute values into the values of Y. Suppose that
each X\ :sub:`i` has a :ref:`qualitative scale <DexQualitative>` consisting of
s\ :sub:`i` values. Then, the number of combinations and thus the size
of the corresponding decision table is equal to

S = s\ :sub:`1` × s\ :sub:`2` × ... × s\ :sub:`n`

Example
~~~~~~~

Let all the n lower-level attributes have s-valued scales. In this case,
the size of f equals to

S =s\ :sup:`n`

The following table shows how fast S grows with the increasing n and s.

.. image:: images/TabSize.png
   :alt: S=s^n

Recommendations
~~~~~~~~~~~~~~~

Experience indicates that aggregation functions of size up to 25 are small and
usually quite easy to define. The difficulty grows towards the size of
about 100, which is already quite difficult. Everything above 100 is
very difficult, and everything above 500 is extremely hard if not
impossible to define.

Also, it is not only the size that matters. The more the attributes, the
more difficult the function to define, even if the size of the functions
is comparable. Combining four attributes usually appears harder than combining three.

For these reasons, the DEXi method strongly advises to limit the number
of aggregate attributes' descendants to three, and to
:ref:`restructure <DexRestructure>` the :ref:`tree of attributes <DexTree>`
whenever this condition has not been met. Or alternatively, the number of
decision rules in a single decision table should be kept below 100.

.. _DexRestructure:

Restructuring Tree of Attributes
--------------------------------

In order to avoid :ref:`combinatorial explosion <DexExplosion>`,
it is strongly advised to structure the :ref:`tree of attributes <DexTree>` so
that each aggregate :ref:`attribute <DexAttribute>` has only two or
three immediate descendants. Whenever you encounter an aggregate
attribute with four descendants, you may want to consider restructuring
the tree below that attribute. Usually, there are several ways to do
that:

.. image:: images/4to3.png
   :alt: Restructuring Tree of Attributes

In all cases, you should regroup the lower-level attributes and
introduce one or two new aggregate attributes.
Usually, the 'right' structure is the one that appears the most
'logical', so that:

-  it groups together similar or related attributes, and
-  it is easy to give names to the newly created attributes.