From: Allan Kamau <allank@sanbi.ac.za>
To: Craig Ringer <craig@postnewspapers.com.au>
Cc: pgsql-sql@postgresql.org
Subject: Re: Removing redundant itemsets
Date: Mon, 31 Mar 2008 11:58:50 +0200
Message-ID: <47F0B5DA.7020101@sanbi.ac.za> (raw)
In-Reply-To: <47F0C2A8.9010008@postnewspapers.com.au>
References: <47F09DD1.1080905@sanbi.ac.za>
<47F0C2A8.9010008@postnewspapers.com.au>
Craig,
Thank you so much for the solution. I have spent many hours since
Thursday last week including the weekend (and it took you just a few
minutes) trying to figure out a solution not involving procedural
programming and looping (as the size of the items and even the number of
"purchases" in the datasets I may be working with may be large), I was
looking for a solution that may take (almost) polynomial time (and
resources) and also make use of Postgresql refined and efficient engine.
Your solution satisfies these requirements. Thanks.
Allan.
Craig Ringer wrote:
> 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
>
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: allank@sanbi.ac.za, craig@postnewspapers.com.au
Subject: Re: Removing redundant itemsets
In-Reply-To: <47F0B5DA.7020101@sanbi.ac.za>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox