1

Given a set of rules which are a logical intersection of some known values (groups, types, properties) that combine to give some value as follows:

group1 AND type1 AND property1 = value1
group1 AND type1 AND property2 = value2
group1 AND type1 AND property3 = value3
group1 AND type2 AND property1 = value1
group1 AND type2 AND property4 = value1
group2 AND type1 AND property2 = value2

And that the following hold true:

  • The sets of group/type/property are finite and known
  • A given rule in unique by the combination of group/type/property
  • Many rules may reference a single value

How might I best approach finding an optimal solution for 'collapsing' these rules into a format where multiple values of the same group are combined (below) whilst maintaining the same logical interpretation of the original lookup?

(group1) AND (type1 OR type2) AND (property1) = value1
(group1 OR group2) AND (type1) AND (property2) = value2
(group1) AND (type1) AND (property3) = value3
(group1) AND (type2) AND (property4) = value1

Aim: the least number of rules which contain the same logical information as the original lookup.

An approach could be taking the original lookup 'keys', grouping by first value then two keys and collapsing on the distinct instances of the remaining key could be repeated for each combination of the keys. The results are headed in the right direction, but are not guaranteed to be optimal with the multi step approach.

Would appreciate any thoughts on a better approach, or pointers to reading if this is actually a generalised problem.

Happy to provide any clarification if required.

*Apologies for the clunky title - hopefully that describes the general problem

EDIT: I think this question (no concrete answer) expresses the problem as finding the Union of all intersecting sets.

EDIT 2: I should have said, the target form is actually a requirement, rather than the logically optimal solution from @timrau. The form is (groups) AND (types) AND (properties) => value, where the groups/types/properties are represented with an OR only.

Community
  • 1
  • 1
Kyle
  • 1,366
  • 2
  • 16
  • 28
  • What language are you talking about here? Are you saying "group1, type1, and property1 are all equal to value1" for example? – jimmyfever Jan 21 '14 at 01:35
  • So you're trying to express a union of intersections as a union of (intersections of union)s – Eric Jan 21 '14 at 01:37
  • @jimmyfever In english I would say a record means "the defined group, type and property belong to the value". No specific language, dealing with a *huge* configuration source that I'd like to express differently. To implement I'd prefer C# or similar but am open minded :) – Kyle Jan 21 '14 at 01:41

1 Answers1

2

For each possible value, form a Boolean formula in sum-of-product form. (for simplicity, I use g1 to represent group1, t1 to represent type1, p1 to represent property1 and v1 to represent value1)

v1 = g1 t1 p1 + g1 t2 p1 + g1 t2 p4
v2 = g1 t1 p2 + g2 t1 p2
v3 = g1 t1 p3

Then, you could apply any logic minimization algorithm / system such as Quine-McCluskey, Espresso, ABC, Logic Friday or even Karnaugh map if you actually plan to minimize them by hand.

After minimzation, we get

v1 = g1 (t1+t2) p1 + g1 t2 p4
v2 = (g1+g2) t1 p2
v3 = g1 t1 p3

They could then be translated back to your original logic formulation.

timrau
  • 22,578
  • 4
  • 51
  • 64