Message-ID: <47F0C2A8.9010008@postnewspapers.com.au>
Date: Mon, 31 Mar 2008 18:53:28 +0800
From: Craig Ringer <craig@postnewspapers.com.au>
User-Agent: Icedove 1.5.0.12 (X11/20070607)
MIME-Version: 1.0
To: Allan Kamau <allank@sanbi.ac.za>
Cc: pgsql-sql@postgresql.org
Subject: Re: Removing redundant itemsets
References: <47F09DD1.1080905@sanbi.ac.za>
In-Reply-To: <47F09DD1.1080905@sanbi.ac.za>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Allan Kamau wrote:
> Hi all,
> I have a list of purchases (market basket) and I would like to select
> non redundant longest possible patterns by eliminating
> (creating/populating other table to contain only non redandant itemsets)
> purchases having item lists which are fully included in at least one
> other purchase.

Here's a possibly slow and surely ugly solution (I think it's right,
though I haven't done more than passing testing):


CREATE VIEW togo_as_arr AS
  SELECT a.tid,
    ARRAY(SELECT item FROM togo b WHERE b.tid = a.tid ORDER BY item)
    AS items
  FROM togo a GROUP BY tid;

SELECT arr_a.tid AS redundant_tid, arr_b.tid AS contained_by
FROM togo_as_arr arr_a CROSS JOIN togo_as_arr arr_b
WHERE arr_a.tid <> arr_b.tid AND arr_a.items <@ arr_b.items;


(the view isn't necessary, but does improve the readability of the query).

It groups the purchases up with item lists as arrays, then finds any
purchases with items arrays wholly contained by other item arrays from
other purchases.

I'm *sure* there's a smarter way to do this that avoids the use of
arrays, but I don't seem to be able to come up with one right now. It's
interesting, though, so I might keep fiddling.

--
Craig Ringer