[SQL] Query om de best mogelijke oplossingen te vinden

[wolly_a]

Misschien is het voor de echte kenner een heel makkelijke vraag, maar ik zoek me al dagen rot. Ik probeer het volgende te bereiken.

Ik heb een database met audio, allemaal items met verschillende lengte. Nu wil ik met een SQL query maken waarmee ik 1 of meerdere items selecteer die samen even lang of langer zijn dan een gewenste waarde.

Stel, ik wil 120 seconden vullen. Dan wil ik bijvoorbeeld dat mijn SQL query een item van 60 seconden en 2 items van 30 seconden geeft. Of 4 items van elk 30 seconden. Eigenlijk alle/zoveel mogelijk combinaties die minimaal even lang zijn als mijn gewenste 120 seconden, maar ook weer niet onbeperkt lang, dus bijvoorbeeld minder lang dan 130 seconden.

Iemand enig idee of dit mogelijk is met een SQL query? Ik ben al enige tijd bezig geweest met bijvoorbeeld de SUM mogelijkheden, maar daarmee krijg ik het niet aan de praat.

Een andere optie is om een enorme hoeveelheid combinaties te laten maken en dan kijken welke combinatie het beste past, maar dat lijkt me veel omslachtiger.

[RobIII]

Is er een reden waarom je dit in een SQL query wil oplossen? Want dat is niet echt de plek ervoor...

[wolly_a]

Ik heb een database met al mijn beschikbare audiobestanden en hun speelduur, daar moet ik het mee doen. Daardoor kom ik vanzelf bij een SQL query uit.

Als er één query is waarmee ik een selectie kan maken waaruit een aantal items komen waarvan de lengte samen voldoen, lijkt me dat veel sneller werken dan op de gok allerlei combinaties gaan proberen.

[ Voor 40% gewijzigd door wolly_a op 07-10-2014 23:52 ]

[RobIII]

Ik zou een 'voorselectie' maken: select * from [myaudio] where [duration] < 130 ofzo (desnoods met een top/limit van 1000, 10.000 of whatever). Daarna zul je toch echt met wat code aan de slag moeten om daar zinnige combinaties mee te maken.

Oh, ja hoor. Het kan vast met een hele creatieve query en er komt geheid iemand m'n 'ongelijk' bewijzen. Maar SQL is niet de plek ervoor, hoe graag je 't ook wil

wolly_a schreef op dinsdag 07 oktober 2014 @ 23:51:
lijkt me dat veel sneller werken dan op de gok allerlei combinaties gaan proberen.

Wie zegt dat 't op de gok moet? Je kunt heel snel een nummer pakken dat < 130 seconden duurt (of zeg < 65) en dan op basis daarvan een ander nummer selecteren dat de resterende tijd (zo goed als mogelijk) benaderd. Of misschien wel 2 of drie. Maar dergelijke zaken bouw je in een algoritme, niet in een set-based taal als SQL. Die gebruik je hooguit om nummers te vinden die voldoen aan de criteria die uit je algoritme voortkomen o.i.d.

[ Voor 43% gewijzigd door RobIII op 08-10-2014 00:11 ]

[wolly_a]

Dat is de werkwijze die ik tot nu toe aanhield. De kans bestaat echter dat door je eerste of tweede keuze je in een situatie brengt waar je derde keus de totale tijd veel te groot maakt. Misschien was er een ander item voor de tweede keuze, waardoor je beter zou komen.

In mijn huidige constructie heb ik een aantal combinaties berekend en dan gekozen waarmee je het beste uitkomt.

[Gomez12]

Dat moet je idd echt in een zelf te schrijven algoritme zetten. Want hier hangen hele ritsen randvoorwaarden aan vermoed ik (wat is bijv beter 1 song van 120sec of 2 songs van 60 sec elk, of is het ipv 2 van 60 sec weer beter om 1 van 115 sec te hebben en 1 van 6 sec omdat die van 6 sec een jingle is die je vaker kan starten)

Maar je hebt waarschijnlijk ook te maken met frequentie van afspelen, stel je hebt elke 10 minuten een gat van 120 sec te vullen en je hebt 1 song van exact 120 sec dan wil je die vast niet elke 10 minuten gespeeld hebben.

En ik denk dat ik zo uit mijn blote hoofd nog wel 10 randvoorwaarden kan verzinnen die je anders allemaal in een set-based language moet wringen

[_js_]

Zoals RobIII al voorspelde is het goed mogelijk in SQL. Mijn voorbeeld is niet heel uitbreidbaar naar een groter maximum aantal geluidsfragmenten, dan wordt het kopiëren en plakken of de query automatisch laten genereren. De randvoorwaarden van Gomez12 zijn aan te hangen door te sorteren op laatst afgespeeld of op de afwijking van de gemiddelde fragmentlengte.

SQL:

select
  a.titel atitel, a.lengte alengte,
  b.titel btitel, b.lengte blengte,
  c.titel ctitel, c.lengte clengte,
  d.titel dtitel, d.lengte dlengte
from liedjes a
left join liedjes b on a.lengte + b.lengte < 130 and b.lengte <= a.lengte and b.titel not in (a.titel)
left join liedjes c on a.lengte + b.lengte + c.lengte < 130 and c.lengte <= b.lengte and c.titel not in (b.titel,a.titel)
left join liedjes d on a.lengte + b.lengte + c.lengte + d.lengte < 130 and d.lengte <= c.lengte and d.titel not in (c.titel,b.titel,a.titel)
where a.lengte + coalesce(b.lengte,0) + coalesce(c.lengte,0) + coalesce(d.lengte,0) between 120 and 130

http://sqlfiddle.com/#!2/2c1dbb/17

[JJ93]

wolly_a schreef op dinsdag 07 oktober 2014 @ 23:51:
Ik heb een database met al mijn beschikbare audiobestanden en hun speelduur, daar moet ik het mee doen. Daardoor kom ik vanzelf bij een SQL query uit.

Als er één query is waarmee ik een selectie kan maken waaruit een aantal items komen waarvan de lengte samen voldoen, lijkt me dat veel sneller werken dan op de gok allerlei combinaties gaan proberen.

En zo'n query vindt alles wel ineens op één of andere magische wijze? Onderwater gebeuren er nog steeds allemaal combinaties op de "gok". Je kan een extreem lange query genereren als je echt via een query de best mogelijke oplossingen wilt vinden.

[Gomez12]

_js_ schreef op woensdag 08 oktober 2014 @ 03:39:
Zoals RobIII al voorspelde is het goed mogelijk in SQL.

Technisch is het mogelijk in SQL, of het goed mogelijk is dat laat ik even ter discussie.

Ik denk dat jouw query wel technisch de gestelde vraag beantwoord, maar ik vraag me af of die het probleem wel oplost.
Als er bijv geen liedje is wat korter is dan 130 sec maar er is er wel 1 van 131 sec dan geeft jouw query geen resultaat, terwijl je in een algoritme bij geen geschikt resultaat met recursie verder kan gaan met bijv 10 sec erbij.
Ik vraag me ten zeerste af of het wel gewenst is dat liedje a altijd het langste en dat de volgende liedjes steeds korter moeten zijn.
Je zal er nog iets van een sortering in moeten zetten om "de best" mogelijke naar boven te krijgen ipv een simpel ongeordend lijstje.
Etc. etc.

Wat ik wel denk dat een overweging / probeersel waard is is om deze query te gebruiken als input voor het algoritme, maar dat is weer afhankelijk van data-grootte en trial and error etc (ik werk vaak met data-verzamelingen van xxx miljoen records, dan grijp je niet zo vlug naar 4 self-joins om input voor een algoritme te creeeren, dan liever binnen het algoritme de input ophalen die dan benodigd is via veel simpeler query's)

JJ93 schreef op woensdag 08 oktober 2014 @ 07:46:
[...]
En zo'n query vindt alles wel ineens op één of andere magische wijze? Onderwater gebeuren er nog steeds allemaal combinaties op de "gok". Je kan een extreem lange query genereren als je echt via een query de best mogelijke oplossingen wilt vinden.

De magische wijze heet joins en het magische toverwoord is indexen.
Het is niet op de gok, het is gewoon de vraag zo omschrijven in sql dat de server gebruik kan maken van indexen en razendsnel mogelijkheden af kan gaan.

Ik denk niet dat je de daadwerkelijk bedoelde vraag in een sql-statement gepropt krijgt, ik denk dat vanwege allerlei redenen er een vervolg algoritme achter moet zitten. Echter kan je wel met sql een groffe voorselectie maken die je algoritme dan kan gaan bruteforcen (op de gok).

Zie de query van _js_, hooguit gaat a verkregen worden "op de gok" maar voor b hoeft er nog maar een subset van a gepakt te worden en voor c weer een subset van b en voor d weer een subset van c
Je kan dat op de gok noemen, maar via indexen etc worden de goks wel over een steeds kleinere subset gedaan waardoor het snel kan blijven.

[wolly_a]

Kijk, dat brengt mogelijkheden. Ik ga aan de slag met de query van _js_. Ik ben niet zo super thuis in de wereld van queries en de mogelijkheden van joins. Ik weet van het bestaan, maar heb tot nu toe alleen maar eenvoudigere queries gemaakt.

Je kan het aantal randvoorwaarden enorm maken, maar dat is in dit geval niet overal nodig. Frequentie van afspelen is deels een ding. Het programmaatje moet eens in de 2 weken 4 blokjes genereren met items die een bepaalde variabele tijd vullen. Ik dacht dit op te vangen met een veld 'laatst gespeeld' en daarmee de items te selecteren die niet onlangs (x dagen) zijn gespeeld.

Ik ga kijken of ik zoveel mogelijk in een SQL query kan krijgen, eventueel aangevuld met een verdere selectie in een algoritme.

[Joostje123]

Ik ben wel altijd voorstander van om zoveel mogelijk data te filteren via Queries en een "lastiger" query uit te voeren. Zodat je alleen de data ophaalt die je ook daadwerkelijk gebruikt.

Maar er zijn zeker grenzen wat met SQL moet, denk dat dit een stapje te ver is.

[Grijze Vos]

Het helpt altijd als je weet waar je op moet zoeken. Dit probleem staat bekend onder de naam 'knapsack problem'. Er zijn ook mensen die dat in sql hebben proberen op te lossen. Google your heart out.

[HansvDr]

Denk dat het in applicatiecode makkelijker is, maar in bijvoorbeeld een Stored Procedure zou je het volgende kunnen doen:

- Creëer een tijdelijke tabel met relevante velden
- Zoek een random bestand die korter is dan de max lengte.
- Zet dit record in de tijdelijke tabel .
- Voeg een nieuw random record die korter is dan (max lengte - de som van alle records) in de tijdelijke tabel toe aan je tijdelijke tabel .
- Doe dit net zo lang totdat er niks meer gevonden wordt.
- Selecteer alle records uit temptabel.

[Verwijderd]

Zoals Grijze Vos al aangaf is dit een typisch knapsack probleem ... wat vrij eenvoudig op te lossen is met een genetisch algoritme.

Hierbij kun je zelfs een fitness functie loslaten op de aantal gevonden fragmenten, hoeveel seconden de oplossing boven het doel uitkomt etc.

best een leuke case waar ik eventueel wel mee zou willen helpen qua code

[RJeee]

Is dit niet goed op te lossen met een recursieve query om de combinaties te vinden met een max van de lengte?

[mhaket]

offtopic:
Dit roept om een functionele taal (Scala bijvoorbeeld). In de cursus die ik voor fucntioneel programmeren heb gedaan kwamen dit soort vraagstukken vaak aanbod en was dat zeer elegant en met weinig code op te lossen. Kost wel ff wat werk om je in een functionele taal te verdiepen, da's dan wel weer een nadeel...

[ Voor 5% gewijzigd door mhaket op 08-10-2014 21:36 . Reden: typo ]

[marcovo]

Gomez12 schreef op woensdag 08 oktober 2014 @ 07:57:
[...]

Ik vraag me ten zeerste af of het wel gewenst is dat liedje a altijd het langste en dat de volgende liedjes steeds korter moeten zijn.

In principe is dit niet nodig, maar het zou de query wel sneller kunnen maken. Je zoekt namelijk naar een verzameling liedjes, de volgorde ervan maakt niet uit voor de totale tijdsduur. Effectief krijg je dus een data-set terug die dezelfde combinaties bevat als zonder de eis, echter zonder alle permutaties (kan veel schelen!) Na het selecteren moet je ze gewoon even husselen om een willekeurige volgorde te krijgen.

Grijze Vos schreef op woensdag 08 oktober 2014 @ 10:51:
Het helpt altijd als je weet waar je op moet zoeken. Dit probleem staat bekend onder de naam 'knapsack problem'. Er zijn ook mensen die dat in sql hebben proberen op te lossen. Google your heart out.

Verwijderd schreef op woensdag 08 oktober 2014 @ 14:01:
Zoals Grijze Vos al aangaf is dit een typisch knapsack probleem ... wat vrij eenvoudig op te lossen is met een genetisch algoritme.

Precies dat; dit is een vrij bekend en goed bestudeerd probleem. Als je hierop zoekt moet je wel iets bruikbaars vinden, en hoef je niet het wiel opnieuw uit te vinden.

In principe kan het in SQL (zoals je gezien hebt), maar als je een snel algoritme wilt is het wellicht niet de beste optie. De vraag wordt dan inderdaad; wil je een snelle oplossing, of vind je het best dat het even kan duren op een grote database?

[ Voor 8% gewijzigd door marcovo op 09-10-2014 12:20 ]