How to create And / Or relations in a database?

Question

I have a Coupon table. A Coupon can be applicable to certain items only or to a whole category of items.

For example: a 5$ coupon for a Pizza 12" AND (1L Pepsi OR French fries)

The best I could come up with is to make a CouponMenuItems table containing a coupon_id and bit fields such as IsOr and IsAnd. It doesn't work because I have 2 groups of items in this example. The second one being a OR relation between 2 items.

Any idea of how I could do it so the logic to implement is as simple as possible?

Any help or cue appreciated!

Thanks,

Teebot

Answer 1

Often, you can simplify this kind of thing by using Disjunctive Normal Form.

You normalize your logic into a series disjunctions -- "or clauses". Each disjunct is set of "and clauses".

So your rules become the following long disjunction.

• Pizza AND Pepsi

OR

• Pizza AND french fries

(You can always do this, BTW, with any logic. The problem is that some things can be really complicated. The good news is that no marketing person will try bafflingly hard logic on you. Further, the rewrite from any-old-form to disjunctive normal form is an easy piece of algebra.)

This, you'll note, is always two layers deep: always a top-level list of the disjunctions (any one of which could be true) and a a lower-level list of conjuncts (all of which must be true).

So, you have a "Conditions" table with columns like id and product name. This defines a simple comparison between line item and product.

You have a Conjuncts ("mid-level and clause") table with columns like conjunct ID and condition ID. A join between conjunct and condition will produce all conditions for the conjunct. If all of these conditions are true, the conjunct is true.

The have a Disjuncts ("top-level or clause") table with columns like disjunct Id and conjunct ID. If one of these disjuncts is true, the disjunction is true.

A join between disjuncts, conjuncts and conditions produces the complete set of conditions you need to test.

Answer 2

One possible approach to consider. Assuming you created the following classes:

+----------+        1 +---------------+ *
| Coupon   |<#>------>| <<interface>> |<--------------+
+----------+          |   CouponItem  |               |
| +value   |          +---------------+               |
+----------+          | +cost()       |               |
                      +---------------+               |
                             /|\                      |
                              |                       |
           +--------------------------------+         |
           |                  |             |         |
      LeafCouponItem   AndCouponItem  OrCouponItem    |
                             <#>           <#>        |
                              |             |         |
                              +-------------+---------+

And:

class Coupon {
    Money value;
    CouponItem item;
}

interface CouponItem {
    Money cost();
}

class AndCouponItem implements CouponItem {
    List<CouponItem> items;
    Money cost() {
        Money cost = new Money(0);
        for (CouponItem item : items) {
           cost = cost.add(item.cost());
        }
        return cost;
    }
}

class OrCouponItem implements CouponItem {
    List<CouponItem> items;
    Money cost() {
        Money max = new Money(0);
        for (CouponItem item : items) {
            max = Money.max(max, item.cost);
        }
        return max;
    }
}

class LeafCouponItem implements CouponItem {
    Money cost;
    Money cost() {
        return cost;
    }
}

And map to 2 tables:

COUPON            COUPON_ITEM
------            -----------
ID                ID
VALUE             COUPON_ID       (FK to COUPON.ID)
                  DISCRIMINATOR   (AND, OR, or LEAF)
                  COUPON_ITEM_ID  (FK to COUPON_ITEM.ID)
                  DESCRIPTION
                  COST            

So for your example you would have:

> SELECT * FROM COUPON

ID              100
VALUE           5

And

> SELECT * FROM COUPON_ITEM

ID      COUPON_ID   DISCRIMINATOR    COUPON_ITEM_ID    DESCRIPTION    COST
200     100         AND              NULL              NULL           NULL
201     100         LEAF             200               PIZZA          10
202     100         OR               200               NULL           NULL
203     100         LEAF             202               PEPSI          2
204     100         LEAF             202               FRIES          3

This single table approach is highly denormalised, and some would prefer to have separate tables for each CouponItem implementation.

Most ORM frameworks will be able to take care of the persitence of such a domain of classes.