Puzzelen met SQL (1) – Politiek Correct?

0

Dit artikel is de on-line tegenhanger van de rubriek Puzzelen met SQL die komende maand voor de eerste maal verschijnt in de Optimize, het vakblad voor Oracle ontwikkelaars in Nederland. In dit on-line artikel kunnen alle scripts worden gedownload, zowel de DDL en data-load scripts, als scripts met mogelijke oplossingen. Ook bevat dit on-line artikel enkele extra uitdagingen en verdere uitwerkingen. Bijdragen aan dit artikel zijn geleverd door Alex Nuijten en Anton Scheffer, vaste medewerkers aan de rubriek Puzzelen met SQL.

Politiek Correct?

"Code schrijven is leuk", hoorde ik laatst iemand zeggen. In eerste instantie was ik het daar helemaal mee eens. Toen ik er wat meer over na ging denken kwam ik tot de conclusie dat die stelling helemaal niet waar is. Het schrijven van code is niet leuk, het oplossen van een vraagstuk is leuk. Het puzzelen, het uitdokteren, het komen tot de meest efficiënte manier van de oplossing, dat is hetgene wat het werk zo leuk maakt.

De lol van deze nieuwe rubriek in Optimize is dan ook voor een belangrijk deel dat puzzelen, de zoektocht naar de creatieve oplossing. Tegelijkertijd zullen in deze rubriek allerlei waardevolle, deels nieuwe en geavanceerde en deels al langer bestaande maar toch onbekende mogelijkheden van Oracle SQL de revue passeren. Er kan zoveel meer met SQL in Oracle dan we vaak denken. Het gebruik van Oracle 9i en 10g SQL syntax en functies biedt mogelijkheden die eerder slechts bestonden door gebruik te maken van PL/SQL.Hopelijk inspireren de puzzels je die functionaliteit ook in de praktijk te gaan brengen!

Voor de eerste SQL puzzel kijken we naar het kabinet Balkenende IV.
Na de verkiezingen van 22 november 2006 werd er alom gemopperd dat het zo vreselijk moeilijk zou zijn om op basis van de uitslag een stabiel kabinet te vormen. Maar zijn alle mogelijkheden wel goed onderzocht? We gaan eens kijken aan de hand van enkele SQL Queries wat nou precies de uitslag was op 22 november, wat zoal de mogelijkheden voor een drie-partijen kabinet waren en wat kleine verschuivingen in de verkiezingsuitslag aan nieuwe mogelijkheden zouden hebben opgeleverd.....

Het datamodel dat we voor deze puzzel gebruiken staat hieronder afgebeeld. Je vindt de uitslagen van zowel de Tweede Kamer-verkiezingen van 2003 als die van 22 november 2006 in deze tabellen.
 

Eerste Uitdaging – Presenteer de verkiezingsuitslag inclusief de verschuivingen

Het eerste vraagstuk: Toon de uitslag van 22 november en geef aan welke winst of welk verlies in zetels iedere partij heeft gemaakt ten opzichte van de uitslag van 2003.

Natuurlijk zijn er verschillende mogelijkheden om dit op te lossen, wij hebben hier gekozen voor toepassing van Analytische Functies – geïntroduceerd in Oracle 8i. Ze bieden ondermeer de mogelijkheid om data op te halen uit andere records zonder een self-join uit te voeren:

lead (zetel_aantal) over ( partition by pty.naam<br />                           order by vkg.datum desc<br />                         )<br />

 

dit fragment bepaalt de waarde van zetel_aantal in de eerstvolgende rij voor dezelfde partij (partition by pty.naam), met rijen gesorteerd op op verkiezingsdatum (order by vkg.datum desc) van nieuw naar oud.

Deze expressie geeft ons de kern van het gevraagde resultaat:

 

NAAM                      DATUM       ZETEL_AANTAL         LD<br />------------------------- ----------- ------------ ----------<br />CDA                       22-11-2006            41         44<br />CDA                       20-1-2002             44 <br />Christenunie              22-11-2006             6          3<br />Christenunie              20-1-2002              3 <br />D'66                      22-11-2006             3          6<br />D'66                      20-1-2002              6<br /><br />

De waarde in de laatste kolom is gelijk aan het zetel_aantal van de volgende rij. Voor het CDA staat er in de laatste kolom 44, dit is het aantal zetel welke behaald was bij de vorige Tweede Kamer verkiezingen. Voor de tweede regel is er geen volgende uitslag voor het CDA – de volgende rij hoort immers bij de Christenunie, een andere "partition" dan het CDA en dus staat er in de laatste kolom NULL.

Een eenvoudige rekensommetje geeft het verschil in zetels ten opzichtte van de vorige keer weer:

zetel_aantal - <br />        lead (zetel_aantal,1,0) over (partition by pty.naam<br />                                    order by vkg.datum desc<br />                                 ) as zetel_verschuiving<br />

NB: de twee extra argumenten in de aanroep van lead Р1 en 0 Рgeven respectievelijk aan hoeveel rijen we verder willen kijken (̩̩n in dit geval) en welke waarde moet worden aangenomen als de gevraagde rij niet beschikbaar is.

Door het tussentijdse resultaat in een subquery te plaatsen kunnen we in de buitenste query verder filteren tot we het beoogde resultaat hebben:

select *<br />from   ( select vkg.democratisch_orgaan||' op '||vkg.datum titel<br />         ,      pty.naam partij<br />         ,      usg.zetel_aantal zetelaantal<br />         ,      usg.zetel_aantal - <br />                    lead (zetel_aantal, 1,0) over ( partition by pty.naam<br />                                                    order by vkg.datum desc<br />                                                  ) zetel_verschuiving<br />         ,      vkg.datum<br />         from   verkiezingen vkg<br />         ,      partijen     pty<br />         ,      uitslag      usg<br />         where  vkg.id = usg.vkg_id<br />         and    pty.id = usg.pty_id<br />         and    vkg.democratisch_orgaan ='Tweede Kamer'<br />       )<br />where  extract(year from datum) = 2006<br />order <br />by     zetelaantal desc<br /><br />

 

TITEL                     PARTIJ          ZETELAANTAL ZETEL_VERSCHUIVING DATUM<br />------------------------- --------------- ----------- ------------------ -----------<br />Tweede Kamer op 22-NOV-06 CDA                      41                 -3 22-11-2006<br />Tweede Kamer op 22-NOV-06 PVDA                     33                 -9 22-11-2006<br />Tweede Kamer op 22-NOV-06 SP                       25                 16 22-11-2006<br />Tweede Kamer op 22-NOV-06 VVD                      22                 -6 22-11-2006<br />Tweede Kamer op 22-NOV-06 PVDV                      9                  9 22-11-2006<br />… <br />

Tweede uitdaging – zoek de mogelijke coalities

De tweede uitdaging vraagt je om op basis van de uitslag van 22 november op zoek te gaan naar alle mogelijke coalities. Meer specifiek: alle coalities bestaande uit drie partijen (met twee lukt het niet en vier kan nooit stabiel worden is de aanname) met tenminste 76 zetels.

Er zijn verschillende mogelijkheden om alle unieke combinaties van drie partijen af te gaan en het resultaat te filteren op de som van drie zetelaantallen. Een redelijk rechtlijnige en goed leesbare aanpak maakt gebruik van de With clause voor het ‘voor-definiëren’ van een In Line View. Dit is een krachtige methode om een complex probleem in deelstappen op te lossen, binnen één SQL query. Voor veel lezers wellicht wennen dat een SQL query niet met SELECT hoeft te beginnen… Overigens biedt de With clause definitie nog enkele voordelen: de in-line view kan meerdere malen gerefereerd worden elders in de query en in-line views kunnen op elkaar worden gebaseerd.

De query die ons de mogelijke coalities presenteert:

 

with fracties as -- alle 2e Kamer fr
acties met hun zetelaantallen<br /
>(<br />select pty.naam<br />,      usg.zetel_aantal<br />,      row_number () over (order by zetel_aantal) rn<br />from   verkiezingen vkg<br />,      partijen     pty<br />,      uitslag      usg<br />where  vkg.id = usg.vkg_id<br />and    pty.id = usg.pty_id<br />and    extract (year from vkg.datum) = 2006<br />order<br />by     zetel_aantal<br />)<br />select f1.naam||'/'||f2.naam||'/'||f3.naam coalitie<br />,      f1.zetel_aantal + f2.zetel_aantal + f3.zetel_aantal zetel_aantal<br />from   fracties f1<br />       join<br />       fracties f2<br />on     (f1.rn &gt; f2.rn)  -- join alleen met een andere, kleinere fractie     <br />       join<br />       fracties f3<br />on     (f2.rn &gt; f3.rn)  -- join alleen met een andere, kleinere fractie<br />where  f1.zetel_aantal + f2.zetel_aantal + f3.zetel_aantal &gt; 75<br />order<br />by     zetel_aantal -- sorteer de coalities op hun zetel-aantal<br /><br />

In deze query wordt allereerst een in-line view opgezet die ons de nieuwe 2e Kamer-fracties oplevert, met hun zetelaantallen. In een eenvoudige join worden alle fracties gekoppeld aan alle andere fracties die kleiner zijn – een simpele methode om combinaties niet dubbel te onderzoeken – en aangezien we naar drie-partij coalities zoeken voeren we nogmaals zo’n join uit. Vervolgens wordt gefilterd op de combinaties waarvoor geldt dat het gezamenlijke zetelaantal hoger is dan 75.

Het resultaat van deze query begint met:

COALITIE     ZETEL_AANTAL<br />------------ ------------<br />CDA/PVDA/SGP           76<br />CDA/PVDA/PvdD          76<br />CDA/PVDA/D'66          77<br />PVDA/SP/VVD            80<br />CDA/PVDA/Christenunie  80<br />...&nbsp;

En geeft maar liefst tien mogelijke combinaties voor rekenkundig verantwoorde coalities. Er viel dus voldoende te formeren…

De verliezer past bescheidenheid

Als de eis is dat er niet meer dan één verliezer (een partij die bij de verkiezingen zetels heeft verloren ten opzichte van drie jaar geleden) in de coalitie mag plaatsnemen, wat zijn dan nog de mogelijkheden? We hebben gezien hoe ondermeer GroenLinks zich met een beroep op het verliezerschap erg bescheiden opstelde in de formatie…

Alle coalities bestaande uit drie partijen, met tenminste 76 zetels, en met hooguit één verliezer:

 

with partij_uitslagen as<br />( select pty.naam partij<br />  ,      usg.zetel_aantal zetel_aantal<br />  ,      usg.zetel_aantal - first_value( zetel_aantal) over (partition by pty.naam order by vkg.datum ) zetel_verschuiving<br />  ,      vkg.datum<br />  from   verkiezingen vkg<br />  ,      partijen     pty<br />  ,      uitslag      usg<br />  where  vkg.id = usg.vkg_id<br />  and    pty.id = usg.pty_id<br />  and    vkg.democratisch_orgaan ='Tweede Kamer'<br />)<br />,      fracties as<br />( select partij naam<br />  ,      zetel_aantal<br />  ,      case <br />         when zetel_verschuiving &lt; 0<br />         then -1<br />         else 0<br />         end      verliezer<br />  ,      row_number () over (order by zetel_aantal) rn<br />  from   partij_uitslagen<br />  where  extract (year from datum) = 2006<br />  order<br />  by     zetel_aantal<br />)<br />select f1.naam||'/'||f2.naam||'/'||f3.naam coalitie<br />,      f1.zetel_aantal + f2.zetel_aantal + f3.zetel_aantal zetel_aantal<br />, f1.verliezer<br />, f2.verliezer<br />, f3.verliezer<br />from   fracties f1<br />       join<br />       fracties f2<br />on     (f1.rn &gt; f2.rn)<br />       join<br />       fracties f3<br />on     (f2.rn &gt; f3.rn)<br />where  f1.zetel_aantal + f2.zetel_aantal + f3.zetel_aantal &gt; 75<br />and    f1.verliezer + f2.verliezer + f3.verliezer &gt; -2<br />order<br />by     zetel_aantal<br />/<br /><br />

Het resultaat is mager: er is geen enkele drie-partij coalitie mogelijk die een meerderheid haalt en toch maar één verliezer bevat.

De Swing’o'meter

We willen Ferry (Mingele) en consorten graag een beetje tegemoet komen, door ze een instrument in handen te geven waarmee snel het effect van kleine schommelingen in de verkiezingsuitslag op de mogelijke coalitievorming kan worden onderzocht. Stel dat het CDA drie zetels minder had gehaald, de PVDA 5 meer en de SP twee minder. Wat waren dan de mogelijke coalities geweest? 

Deze uitdaging pakken we op in drie stappen.

a) Allereerst willen we een ‘tokenizer’ maken, die een string als "CDA-3,PVDA+5,SP-2" of "CDA+8,D’66-2,SGP+10,SP-16" omzet in rijen per partij en kolommen met partijnaam en zetelschommeling. Zie voor inspiratie: http://technology.amis.nl/blog/?p=1631 .

with  variatie as<br />( select 'CDA+1,PVDA+4,D''66+3,SP+0' variatie_string<br />  ,      ','  delimiter<br />  from   dual<br />)<br />, string_tokenizer as<br />( select substr ( string_to_tokenize <br />                , decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                , instr(string_to_tokenize, delimiter, 1, level) <br />                  - decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                ) token <br />   from ( select variatie_string||delimiter as string_to_tokenize <br />          ,      delimiter <br />          from   variatie<br />     )    <br />   connect <br />   by     instr(string_to_tokenize, delimiter, 1, level) &gt; 0 <br />)<br />select * <br />from   string_tokenizer<br />/<br />&nbsp;

 

b) Met de String Tokenizer in de hand, laten we enkele variaties op de uitslag analyseren. Laat Ferry in een SQL*Plus variabele op de hiervoor geschetste manier zijn te onderzoeken variatie opgeven. Toon de fictieve uitslag met die variatie over de werkelijke uitslag heengelegd. Kan je controleren of Ferry’s schommeling correct is? (dat wil zeggen dat alle plussen en minnen elkaar opheffen zodat we nog steeds precies 150 zetels uitdelen?)

 

De variaties die via de SQL*Plus variabele worden doorgegeven losgelaten op de werkelijke uitslag om een fictieve uitslag te construeren:<br /><br />bijvoorbeeld:<br /><br />Enter value for variaties_in_uitslag: CDA-9,PVDA+4,SP+5<br />old   2: ( select '&amp;variaties_in_uitslag' variatie_string<br />new   2: ( select 'CDA-9,PVDA+4,SP+5' variatie_string<br /><br />with  variatie as<br />( select '&amp;variaties_in_uitslag' variatie_string<br />  ,      ','  delimiter<br />  from   dual<br />)<br />, schommelingen as<br />( select substr ( string_to_tokenize<br />                , decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                , instr(string_to_tokenize, delimiter, 1, level)<br />                  - decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                ) token<br />   from ( select variatie_string||delimiter as string_to_tokenize<br />          ,      delimiter<br />          from   variatie<br />     )<br />   connect<br />   by     instr(string_to_tokenize, delimiter, 1, level) &gt; 0<br />)<br />, partij_schommelingen as<br />(<br />  select pty.id pty_id<br />  ,      pty.naam partij<br />  ,      case substr( smg.token, length(pty.naam)+1,1)<br />         when '+' then 1<br />         when '-' then -1<br />         end<br />         * to_number(substr( smg.token, length(pty.naam)+2)) zetel_delta<br />  from   schommelingen smg<br />         join<br />         partijen pty<br />  on     (naam = substr( smg.token, 1, length(naam)))<br />)<br />, fracties as<br />( select pty.naam<br />  ,      usg.zetel_aantal + nvl(psg.zetel_delta,0) zetels<br />  ,      row_number () over (order by usg.zetel_aantal + nvl(psg.zetel_delta,0)) rn<br />  from   verkiezingen vkg<br />         join<br />         uitslag      usg<br />  on     (vkg.id = usg.vkg_id)<br />         join<br />         partijen     pty<br />  on     (pty.id = usg.pty_id)<br />         left outer join<br />

      partij_schommelingen psg<br />  on     (pty.id = psg.pty_id)<br />  where  extract (year from datum) = 2006<br />  order<br />  by     zetel_aantal<br />)<br />select naam partij<br />,      zetels<br />from   fracties<br />order<br />by     rn desc<br />/<br /><br />

c) Laat nu bij zo’n fictieve – op de SQL*Plus variabele gebaseerde schommeling gebaseerde – uitslag de mogelijke coalities zien. Met de fictieve uitslagen die door de te analyseren schommelingen worden gerealiseerd kan opnieuw bekeken worden welke coalties er mogelijk zijn. De query daarvoor zou er als volgt uit kunnen zien:

 

with  variatie as<br />( select '&amp;variaties_in_uitslag' variatie_string<br />  ,      ','  delimiter<br />  from   dual<br />)<br />, schommelingen as<br />( select substr ( string_to_tokenize<br />                , decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                , instr(string_to_tokenize, delimiter, 1, level)<br />                  - decode( level, 1, 1, instr(string_to_tokenize, delimiter, 1, level-1)+1)<br />                ) token<br />   from ( select variatie_string||delimiter as string_to_tokenize<br />          ,      delimiter<br />          from   variatie<br />     )<br />   connect<br />   by     instr(string_to_tokenize, delimiter, 1, level) &gt; 0<br />)<br />, partij_schommelingen as<br />(<br />  select pty.id pty_id<br />  ,      pty.naam partij<br />  ,      case substr( smg.token, length(pty.naam)+1,1)<br />         when '+' then 1<br />         when '-' then -1<br />         end<br />         * to_number(substr( smg.token, length(pty.naam)+2)) zetel_delta<br />  from   schommelingen smg<br />         join<br />         partijen pty<br />  on     (naam = substr( smg.token, 1, length(naam)))<br />)<br />, fracties as<br />( select pty.naam<br />  ,      usg.zetel_aantal + nvl(psg.zetel_delta,0) zetels<br />  ,      row_number () over (order by usg.zetel_aantal + nvl(psg.zetel_delta,0)) rn<br />  from   verkiezingen vkg<br />         join<br />         uitslag      usg<br />  on     (vkg.id = usg.vkg_id)<br />         join<br />         partijen     pty<br />  on     (pty.id = usg.pty_id)<br />         left outer join<br />         partij_schommelingen psg<br />  on     (pty.id = psg.pty_id)<br />  where  extract (year from datum) = 2006<br />  order<br />  by     zetel_aantal<br />)<br />select f1.naam||'/'||f2.naam||'/'||f3.naam coalitie<br />,      f1.zetels + f2.zetels + f3.zetels zetel_aantal<br />from   fracties f1<br />       join<br />       fracties f2<br />on     (f1.rn &gt; f2.rn)       <br />       join<br />       fracties f3<br />on     (f2.rn &gt; f3.rn)       <br />where  f1.zetels + f2.zetels + f3.zetels &gt; 75<br />order<br />by     zetel_aantal<br />/<br /><br />

 

De volgende aflevering

In de volgende aflevering van Puzzelen met SQL gaan we het programma-aanbod op de Nederlandse televisie doorlichten en op grond van vooraf opgegeven voorkeuren voor kijkers ideale televisieavonden samenstellen.
 

Resources

Download de scripts voor het creëren van de tabellen en het laden van de data alsmede de mogelijke SQL oplossingen van de puzzel-uitdagingen: KabinetsFormatieDDLenDATAenUitwerkingen.zip

Share.

About Author

Lucas Jellema, active in IT (and with Oracle) since 1994. Oracle ACE Director for Fusion Middleware. Consultant, trainer and instructor on diverse areas including Oracle Database (SQL & PLSQL), Service Oriented Architecture, BPM, ADF, Java in various shapes and forms and many other things. Author of the Oracle Press book: Oracle SOA Suite 11g Handbook. Frequent presenter on conferences such as JavaOne, Oracle OpenWorld, ODTUG Kaleidoscope, Devoxx and OBUG. Presenter for Oracle University Celebrity specials.

Comments are closed.