How to create And / Or relations in a database?

Question

Hello,

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

You could treat individual items as their own group (1 member) and just implement pure logic to map coupons to groups.

Answer 2

You will need to group all your relationships together, define how they are grouped, and then assign coupons to those relationships. Essentially you need database entities to represent the parenthesis in your example, though you will need one more outer parenthesis:

(Pizza 12" AND (1L Pepsi OR French fries))

Coupon
    CouponId
    Name
    ...

Item
    ItemId
    Name
    ...

Group
    GroupId

GroupMembership
    GroupMembershipId
    GroupId
    ItemId

ItemAssociation
    ItemAssociationId
    Item1Id
    Item2Id
    IsOr : bit -- (default 0 means and)

GroupAssociation
    GroupAssociationId
    Group1Id
    Group2Id
    IsOr : bit -- (default 0 means and)

After brainstorming that structure out it looks like something that could be solved with a nodal parent/child relationship hierarchy. The ItemAssociation/GroupAssociation tables smell to me, I think a general Association table that could handle either may be desirable so you could write general purpose code to handle all relationships (though you'd lose referential integrity unless you also generalize Item and Group into a single entity).

Note: also naming an entity Group can create problems. :)

Answer 3

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.

Answer 4

My suggestion:

Table
  primary key
= = = = =
COUPONS
  coupon_id

PRODUCT_GROUPS
  group_id

ITEM_LIST
  item_id

ITEM_GROUP_ASSOC
  item_id, group_id

COUPON_GROUP_ASSOC
  coupon_id, group_id 

COUPON_ITEM_ASSOC
  coupon_id, item_id

In the COUPON_ITEM_ASSOC table, have a field indicating how many items the coupon may apply to at once, with some special value indicating "infinite".

Answer 5

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.