[MySQL] Productselector adhv checkboxes

[Matis]

Deze vraag heeft wat raakvlakken met [Java] Efficienter varianten bitmap genereren (winkelmand)
TL;DR
Beste DEVvers,

momenteel zit ik met de volgende uitdaging in mijn maag.
Wij hebben een (zogenaamde) megamatrix van producten en hun functionaliteit.
Dit zit verdeeld over twee tabellen (product en functionaliteit) en een koppeltabel.

Ieder product heeft een uniek id en iedere functionaliteit heeft ook zijn unieke id.
Het koppeltabel heeft dus drie kolommen, id, prod_id en func_id. Wanneer een product bepaalde functionaliteit niet heeft, komt de koppeling ook niet voor in de koppeltabel.

We hebben momenteel een productselector, daarop kan een (potentiële) klant aangeven welke functionaliteit hij zoekt. Hij krijgt dus alle mogelijke functies voorgeschoteld, daarin kan hij vinkjes zetten.

Nu is het aan mij de taak om een product te zoeken dat hier zo dicht mogelijk bij in de buurt komt qua functionaliteit.

Er zijn een aantal eisen:
Een klant mag NOOIT een productadvies krijgen met minder functionaliteit dan gewenst.
Wanneer er geen producten zijn die aan de wensen van de klant voldoen, moeten er meerdere producten terugkomen die de gewenste functionaliteit wel bieden. Er moet dan het product met de meeste functionaliteit voorkomen en een product dat de overige functionaliteit vervult (of weer meerdere producten).

We hebben momenteel 320 producten en ongeveer 150 functionaliteiten.

Ik heb hier al een aantal dagen over nagedacht, maar ik wil deze "berekening" op de volgende manier uitvoeren.

Voor elk product maken we een 150-bits grote hash, dit doen we voor ieder product. De 150 bits worden dus samengesteld uit de functionaliteit (func_id ASC). Wanneer een functionaliteit wel voorkomt kan er een 1 worden gezet, anders een 0 (of precies andersom, ik weet niet wat performancewise het gunstigste is).
Omdat dit volgens mij initieel al veel rekenkracht kost, kan deze hash middels een cronjob eenmaal daags berekend worden.

Wanneer een klant een aantal vinkjes heeft gezet, dan maken we aan de hand van zijn wensen ook eenzelfde hash. Deze hash wil ik dan met de product-hash vergelijken.

Door de eis dat een product tenminste de gestelde eisen moet hebben, kan ik niet domweg de hamming distance berekenen. Omdat ik dan niet kan zien of het bitverschil in het voordeel of in het nadeel van de wensen van de klant is.
Om dat probleem te omzeilen, kan ik natuurlijk kijken hoeveel bits er in het product aanstaan en hoeveel bits er in de productwens aanstaan (eventueel een extra kolom in de hash-tabel). Het aantal bits in de productwens mag nooit hoger zijn dan het aantal in het bestaande product.
Dit mag natuurlijk wel indien er geen enkel product is dat aan de wensen van de klant voldoet, dan moet er dus een productselectie gegeven worden. Dit is echter een zorg voor later.

Ik kwam op SO wel het volgende topic tegen: http://stackoverflow.com/...-on-binary-strings-in-sql
Ik snap echter niet goed wat er staat, te meer omdat ik niet thuis ben in de Data Types van MySQL.
Om binnen de mooie abstracte getallen van de 2^n te blijven, is het misschien een goed idee om 256-bits grootte hash te maken, waar de bovenste bitjes dont care zijn, zolang er geen functionaliteit is.

TL;DR:
Ik zoek dus eigenlijk twee dingen
1. Een manier om die hashes (150bits+) zo efficiënt mogelijk op te slaan.
2. Een manier om die hashes zo efficiënt mogelijk te vergelijken met de hash die voortvloeit uit de wensen van de klant.

Alvast bedankt voor jullie meedenken

[RobIII]

Ik post van een iPhone dus 't is kort en krachtig: hash laten varen, gewoon (inner) join* per gewenste/geselecteerde functie gebruiken. Het id in je koppeltabel is overbodig want de andere 2 id's in de tabel vormen samen een compound key (zie wikipedia).

* want, volgens jou, elke gekozen functionaliteit moet voorkomen.

[ Voor 16% gewijzigd door RobIII op 22-10-2011 19:49 ]

[Matis]

RobIII schreef op zaterdag 22 oktober 2011 @ 19:47:
Ik post van een iPhone dus 't is kort en krachtig:

Kort en krachtig, daar houd ik wel van

hash laten varen, gewoon (inner) join* per gewenste/geselecteerde functie gebruiken.

Duidelijk, omdat elke functionaliteit MOET voorkomen op een kaart, kan ik dus joinen op de koppeltabel.

Het id in je koppeltabel is overbodig want de andere 2 id's in de tabel vormen samen een compound key (zie wikipedia).

Ohja, dom van mij, eens kijken of ik er nog dependancies naar het koppel_id-veld zijn. Anders zal ik hem wegpoetsen

Wanneer ik meerdere resultaten terug krijg, dan kan ik altijd nog oplopend sorteren op de count(*) van het aantal keren dat een product functionaliteit heeft.
Vaak is het zo, hoe minder functionaliteit, hoe goedkoper. Dit is niet altijd waar, maar wel een goede stelregel.
Aangezien wij met MySQL babbelen via een PHP-pagina, moet ik dus in PHP de query dynamisch opbouwen aan de hand van de geselecteerde functionaliteit van de klant.

Ik heb dus drie tables, product function en matrix
matrix is de koppeltabel, welke de product.id en de function.id koppelt.

Ik kan alleen niet bedenken hoe en welke tabel ik moet joinen.

SQL:

SELECT
   category.name,
   category.id,
   product.product_id
FROM
   category 
      INNER JOIN product 
         ON(category.id=product.category_id)
   ;

Dat wordt in het voorbeeld op de FAQ-pagina genoemd.
De klant geeft een aantal wensen op, deze wensen worden aan het query gevoerd en zullen dus uit een aantal function.id's bestaan, welke altijd voorkomen in de function-tabel.

Wordt de query dan zoiets?

SQL:

SELECT
   product.name,
   product.id,
   matrix.product_id
FROM
   product 
      INNER JOIN function 
         ON(product.id=matrix.function_id)
   ;

Echter zie ik hier ook niet hoe ik in deze query de gewenste function.id's kan onderbrengen

Ik moet dan alleen nog een manier verzinnen om productwensen te ondervangen die niet binnen één product vallen.
Dat moet natuurlijk gebeuren wanneer het eerste query geen resultaten teruggeeft.

[P_de_B]

Onderstaand geeft je een lijstje met producten die voldoen aan geselecteerde functies. De laatste kolom geeft aan hoeveel van de gevraagde functies ondersteund worden.

SQL:

SELECT P.ProductId, P.ProductName, COUNT(F.FUnctionId) as AantalOndersteundeFuncties
FROM Product P
INNER JOIN Matrix M ON P.ProductId = M.ProductId
INNER JOIN Functions F ON M.FunctionId = F.FunctionId
WHERE F.FunctionID IN (1,2,3) --lijstje met gewenste functionId's
GROUP BY P.ProductId, P.ProductName
ORDER BY AantalOndersteundeFuncties DESC

Wil je alleen records terug die aan alle voldoen dan moet je nog een HAVING toevoegen:

SQL:

HAVING COUNT(F.FunctionID) = 3 -- COUNT Moet gelijk zijn aan aantal waardes in de IN clausule

Het is denk ik even de vraag hoe je een mismatch gaat verwerken. Op het moment dat uit de query met de having geen resultaten komen moet je hem nog een keer uitvoeren zonder de having, eventueel met een TOP 1 (of LIMIT 1 bij MySQL) zodat je het product met de meeste functies terugkrijgt. Je moet dan bekijken welke functies ondersteund worden, en met de missende opnieuw gaan kijken of je een product kunt vinden.

Het wordt ingewikkelder als je wat meer logica wilt aanbrengen denk ik. Stel dat je functies 1 t/m 6 zoekt. Product A heeft 1,2,3,4 en 5 en kost 100 euro. Product C heeft functie 6 en kost 50 euro. Product D heeft ook functie 6 en kost 20 euro. Als je rekening houdt met de prijs zouden dus A en D er uit komen. Het kan echter best zijn (kan ik me voorstellen) dat Product B 1,2,3 ondersteund en 50 euro kost en product E 4,5,6 en ook 50 euro kost. Je zou dus dan beter D en E kunnen kiezen terwijl je startpunt A was omdat deze initieel de meeste ondersteund. In hoeverre dit speelt zul je moeten beoordelen.

[Matis]

P_de_B schreef op zondag 23 oktober 2011 @ 10:22:
*snip*

Hartelijk dank voor je toelichting

De query doet inderdaad precies wat ik wens / verwacht. Wat ik nu dus nog moet uitzoeken is het volgende:
Wanneer één product niet kan leveren wat de klant wenst, draai ik dus het query zonder de HAVING clausule.
Voor alle producten die dan terugkomen met de hoogste AantalOndersteundeFuncties moet ik dus proberen uit te zoeken welke functies ze ondersteunen, het liefste in dezelfde query, maar dat wil nog niet helemaal lukken.
Als ik weet welke functies elke kaart biedt, dan haal ik die van het lijstje met gewenste functionId's af en draai ik de query nog een keer. Die kaarten vallen dan samen. Dit doe ik net zo lang totdat ik (tenminste) één product uit de query met de HAVING clausule terug heb.

Het laatste punt dat je aandraagt is valide. Immers wil een klant een zo'n goedkoop mogelijke oplossing, maar we hebben er initieel voor gekozen om prijs niet mee te nemen in de berekening / bepaling. Te meer omdat elke klant andere (kwantum) kortingen krijgt.
Wel ben ik het met je eens dat deze "weging" het veel ingewikkelder maakt.

[P_de_B]

Als je het echt in één query wilt kunnen doen kan ik op dit moment even niets anders bedenken dan een comma seperated list te genereren. Daar zul je aan de client zelf iets mee moeten doen (in een array frutsen of zo). Ik ben geen MySQL held, maar het moet met GROUP_CONCAT kunnen.

SQL:

SELECT P.ProductId, P.ProductName, GROUP_CONCAT(f.FunctionId, ',') as ListOfSupportedFunctions FROM Product P 
INNER JOIN Matrix M ON P.ProductId = M.ProductId 
INNER JOIN Functions F ON M.FunctionId = F.FunctionId 
WHERE F.FunctionID IN (1,2,3) --lijstje met gewenste functionId's 
GROUP BY P.ProductId, P.ProductName 
ORDER BY AantalOndersteundeFuncties DESC

edit:

Je kunt natuurlijk ook een subquery gebruiken:

SQL:

SELECT P.ProductId, P.ProductName, F.FunctionId
FROM Product P 
INNER JOIN Matrix M ON P.ProductId = M.ProductId 
INNER JOIN Functions F ON M.FunctionId = F.FunctionId 
WHERE P.ProductID IN 
(SELECT P.ProductId FROM Product P 
INNER JOIN Matrix M ON P.ProductId = M.ProductId 
INNER JOIN Functions F ON M.FunctionId = F.FunctionId 
WHERE F.FunctionID IN (1,2,3)) --lijstje met gewenste functionId's 

[ Voor 24% gewijzigd door P_de_B op 24-10-2011 22:38 ]