Rekursīvie vaicājumi

Veidojot datu modeli mēdz būt situācijas, kad nākas sastapties ar rekursijām (entītijai saite pašai uz sevi). Tipiskākie piemēri iz dzīves – organizācijas struktūra, kur ir viena virsiestāde un zem tās dažādos līmeņos pakļautās iestādes. Līdzīgi arī darbinieku pakļautība, ir galvenais boss, tam pakļautie un tā tālāk līdz pat katrai apkopējai. Vispārīgā gadījumā rekursija, protams, nav bezgalīga (vismaz datubāzu pasaulē), bet tai arī nav zināms maksimālais dziļums vai arī tas ir mainīgs un/vai pārāk liels, lai veidotu fiksētu hierarhisku datu struktūru, kurā datus glabāt. Rekursija, protams, vispārīgā gadījumā var būt arī vizuāla, kā tas redzams nākošajā fotogrāfijā.

Vizuāla rekursija
Vizuāla rekursija

Konceptuālais datu modelis jau iepriekšminētajam, piemēram, par darbinieku pakļautību izskatās šāds. Ir entītija darbinieks. Katram darbiniekam var būt viens boss (kas atkal savukārt ir darbinieks). Katram darbiniekam var būt viens vai vairāki pakļautie, kas, savukārt, ir darbinieki.

Rekursija konceptuālajā datu modelī
Rekursija konceptuālajā datu modelī

Savukārt loģiskais datu modelis šai pašā situācijā izskatās šāds. Ir tabula DARBINIEKI. Ir naturālā primārā atslēga uz PERSONAS KODU. Ir ārējā atslēga BOSA_PERSONAS_KODS pašai tabulai uz sevi, kas norāda priekšnieku.

Rekursija loģiskajā datu modelī
Rekursija loģiskajā datu modelī

Šo tabulu arī tad izmantosim turpmāko vaicājumu veidošanā. Vispirms izveidojam un aizpildam ar datiem.

CREATE TABLE DARBINIEKI (
  PERSONAS_KODS VARCHAR2 (11)  NOT NULL,
  BOSA_PERSONAS_KODS VARCHAR2 (11),
  VARDS VARCHAR2 (50),
  UZVARDS VARCHAR2 (50));
ALTER TABLE DARBINIEKI
  ADD CONSTRAINT PK_DARBINIEKS PRIMARY KEY (PERSONAS_KODS) ;
ALTER TABLE DARBINIEKI
  ADD CONSTRAINT BOSS_DARBINIEKS_FK FOREIGN KEY
  (BOSA_PERSONAS_KODS)
  REFERENCES DARBINIEKI (PERSONAS_KODS);
INSERT INTO darbinieki VALUES (
  '11111111111', NULL, 'BOSU', 'BOSS');
INSERT INTO darbinieki VALUES (
  '22222222222', '11111111111', 'PIRMAIS', 'VIETNIEKS');
INSERT INTO darbinieki VALUES (
  '33333333333', '11111111111', 'OTRAIS', 'VIETNIEKS');
INSERT INTO darbinieki VALUES (
  '44444444444', '11111111111', 'RAŽOŠANAS', 'VADĪTĀJS');
INSERT INTO darbinieki VALUES (
  '55555555555', '44444444444', 'PIRMAIS', 'STRĀDNIEKS');
INSERT INTO darbinieki VALUES (
  '66666666666', '44444444444', 'OTRAIS', 'STRĀDNIEKS');
INSERT INTO darbinieki VALUES (
  '77777777777', '55555555555', 'PIRMĀ', 'STRĀDNIEKA PALĪGS');
INSERT INTO darbinieki VALUES (
  '8888888888', '77777777777', 'PIRMĀ', 'STRĀDNIEKA PALĪGA PALĪGS');
COMMIT;

Kā redzams pēc vārda uzvārda jau viss ir skaidrs un vizuāli darbinieku hierarhija izskatās šādi:

Darbinieku hierarhija
Darbinieku hierarhija

 Fiksēta skaita līmeņu atlase

Ja rekursijas maksimālais dziļums ir zināms un tas nav liels (3,4 nu varbūt arī vairāk), tad bērnus, mazbērnus, maz..mazbērnus un vecākus, vecvecākus, vec..vecākus var iegūt vienkārši – izmantojot pašsavienojumus.

Piemērs 1. Atlasa visus darbiniekus un to tieši pakļautos izmantojot ārējo savienojumu.
SQL> SELECT prieksn.vards, prieksn.uzvards, pakl.vards, pakl.uzvards
  2  FROM darbinieki prieksn
  3  LEFT OUTER JOIN darbinieki pakl
  4  ON (prieksn.personas_kods = pakl.bosa_personas_kods);

VARDS     UZVARDS                  VARDS     UZVARDS
--------- ------------------------ --------- ----------------------
BOSU      BOSS                     PIRMAIS   VIETNIEKS
BOSU      BOSS                     OTRAIS    VIETNIEKS
BOSU      BOSS                     RAŽOŠANAS VADĪTĀJS
RAŽOŠANAS VADĪTĀJS                 PIRMAIS   STRĀDNIEKS
RAŽOŠANAS VADĪTĀJS                 OTRAIS    STRĀDNIEKS
PIRMAIS   STRĀDNIEKS               PIRMĀ     STRĀDNIEKA PALĪGS
PIRMĀ     STRĀDNIEKA PALĪGS        PIRMĀ     STRĀDN.. PALĪGA PALĪGS
OTRAIS    STRĀDNIEKS
OTRAIS    VIETNIEKS
PIRMAIS   VIETNIEKS
PIRMĀ     STRĀDNIEKA PALĪGA PALĪGS

11 rows selected.

Kā redzams, iepriekšējā piemērā, ne visiem bija pakļautie darbinieki. Lai atlasītu tikai tos, kam ir pakļautie, ir jāpielieto iekšējais savienojums.

Piemērs 2. Atlasa tikai tos darbiniekus, kam ir pakļautie, un to tieši pakļautos izmantojot iekšējo savienojumu.
SQL> SELECT prieksn.vards, prieksn.uzvards, pakl.vards, pakl.uzvards
  2  FROM darbinieki prieksn
  3  INNER JOIN darbinieki pakl
  4  ON (prieksn.personas_kods = pakl.bosa_personas_kods);
VARDS        UZVARDS            VARDS        UZVARDS
------------ ------------------ ------------ ------------------------
BOSU         BOSS               PIRMAIS      VIETNIEKS
BOSU         BOSS               OTRAIS       VIETNIEKS
BOSU         BOSS               RAŽOŠANAS    VADĪTĀJS
RAŽOŠANAS    VADĪTĀJS           PIRMAIS      STRĀDNIEKS
RAŽOŠANAS    VADĪTĀJS           OTRAIS       STRĀDNIEKS
PIRMAIS      STRĀDNIEKS         PIRMĀ        STRĀDNIEKA PALĪGS
PIRMĀ        STRĀDNIEKA PALĪGS  PIRMĀ        STRĀDNIEKA PALĪGA PALĪGS
7 rows selected.

Ja nu gadījumā mēs gribam nevis tieši pakļautos, bet vienu līmeni izlaižot, tad jāpievieno vēl viens savienojums. 

Piemērs 3. Atlasa darbiniekus un tiem pakļautos vienu līmeni izlaižot.
SQL> SELECT prieksn.vards, prieksn.uzvards, pakl2.vards, pakl2.uzvards
  2  FROM darbinieki prieksn
  3  INNER JOIN darbinieki pakl
  4  ON (prieksn.personas_kods = pakl.bosa_personas_kods)
  5  INNER JOIN darbinieki pakl2
  6  ON (pakl.personas_kods = pakl2.bosa_personas_kods);
VARDS        UZVARDS       VARDS        UZVARDS
------------ ------------- ------------ ------------------------
BOSU         BOSS          OTRAIS       STRĀDNIEKS
BOSU         BOSS          PIRMAIS      STRĀDNIEKS
RAŽOŠANAS    VADĪTĀJS      PIRMĀ        STRĀDNIEKA PALĪGS
PIRMAIS      STRĀDNIEKS    PIRMĀ        STRĀDNIEKA PALĪGA PALĪGS 

Piemērs 4. Atlasa pakļauto skaitu katrā līmenī.
SQL> SELECT prieksn.vards, prieksn.uzvards,
  2    count(distinct pakl.personas_kods) pakl1_sk,
  3    count(distinct pakl2.personas_kods) pakl2_sk,
  4    count(distinct pakl3.personas_kods) pakl3_sk,
  5    count(distinct pakl4.personas_kods) pakl4_sk
  6  FROM darbinieki prieksn
  7  LEFT JOIN darbinieki pakl
  8  ON (prieksn.personas_kods = pakl.bosa_personas_kods)
  9  LEFT JOIN darbinieki pakl2
 10  ON (pakl.personas_kods = pakl2.bosa_personas_kods)
 11  LEFT JOIN darbinieki pakl3
 12  ON (pakl2.personas_kods = pakl3.bosa_personas_kods)
 13  LEFT JOIN darbinieki pakl4
 14  ON (pakl3.personas_kods = pakl4.bosa_personas_kods)
 15  WHERE prieksn.personas_kods = '11111111111'
 16  GROUP BY prieksn.vards, prieksn.uzvards;
VARDS   UZVARDS     PAKL1_SK   PAKL2_SK   PAKL3_SK   PAKL4_SK
------- --------- ---------- ---------- ---------- ----------
BOSU    BOSS               3          2          1          1 

Līdz šim visi piemēri bija izejot no priekšnieka un meklējot tam padotos. Protams, var skatīties arī no otras puses – atlasot padoto un skatoties tam visus priekšniekus. Ja gribam dabūt tiešo priekšnieku, tikai tiem, kam tādi ir, tad 2. piemērā tas jau bija izdarīts. Ja gribam darbiniekus, neskatoties uz to vai tiem priekšnieki ir, vai nē, tad ņemam pirmo piemēru, kreiso savienojumu nomainam ar labo (left ->right) un esam vajadzīgo ieguvuši. Tiesa gan, aizstājējvārdi mums ir palikuši tieši otrādi, kā tagad esam datus ieguvuši, jo kreisajā pusē ir priekšnieki un labajā pusē padotie.

Piemērs 5. Atlasa visus darbiniekus (pat, ja priekšnieku nav) un to priekšniekus.
SQL> SELECT prieksn.vards, prieksn.uzvards, pakl.vards, pakl.uzvards
  2  FROM darbinieki prieksn
  3  RIGHT OUTER JOIN darbinieki pakl
  4  ON (prieksn.personas_kods = pakl.bosa_personas_kods);
VARDS     UZVARDS           VARDS        UZVARDS
--------- ----------------- ------------ ------------------------
BOSU      BOSS              RAŽOŠANAS    VADĪTĀJS
BOSU      BOSS              OTRAIS       VIETNIEKS
BOSU      BOSS              PIRMAIS      VIETNIEKS
RAŽOŠANAS VADĪTĀJS          OTRAIS       STRĀDNIEKS
RAŽOŠANAS VADĪTĀJS          PIRMAIS      STRĀDNIEKS
PIRMAIS   STRĀDNIEKS        PIRMĀ        STRĀDNIEKA PALĪGS
PIRMĀ     STRĀDNIEKA PALĪGS PIRMĀ        STRĀDNIEKA PALĪGA PALĪGS
                            BOSU         BOSS
8 rows selected.

Piemērs 6. Atlasa visus darbiniekus, kam nav bosu (kas ir hierarhijas pašā augšā).
SQL> SELECT * FROM darbinieki
  2  WHERE bosa_personas_kods IS NULL;
PERSONAS_KO BOSA_PERSON VARDS        UZVARDS
----------- ----------- ------------ --------
11111111111             BOSU         BOSS

Piemērs 7. Atlasa visus darbiniekus, kam nav pakļauto (kas ir hierarhijas pašā apakšā).
SQL> SELECT * FROM darbinieki d
  2  WHERE NOT EXISTS (
  3    SELECT 1 FROM darbinieki p
  4    WHERE p.bosa_personas_kods = d.personas_kods);
PERSONAS_KO BOSA_PERSON VARDS        UZVARDS
----------- ----------- ------------ ------------------------
22222222222 11111111111 PIRMAIS      VIETNIEKS
33333333333 11111111111 OTRAIS       VIETNIEKS
66666666666 44444444444 OTRAIS       STRĀDNIEKS
8888888888  77777777777 PIRMĀ        STRĀDNIEKA PALĪGA PALĪGS

Visi līdz šim minētie vaicājumu piemēri patiesībā tā īsti rekursīvi nav, jo rekursija ir fiksētā skaitā un pie iepriekš nezināma rekursiju skaita šie vaicājumi un izmantotā metode nestrādās. Tādēļ dažas DBVS ir izveidojušas speciālus paņēmienus un vaicājumu (SELECT) paplašinājumus, kā ar tikt galā ar patvaļīgu skaitu rekursijas iterācijām.

Rekursīvie vaicājumi Oraclē

Oraclē tiek izmantotas speciālas klauzas START WITH .. CONNECT BY. Šeit būs saite uz atsevišķu rakstu par to.

Rekursīvie vaicājumi SQL Serverī

SQL Server rekursīviem vaicājumiem izmanto kopējās tabulas izteiksmes (common table expression) klauzu. Šeit būs saite uz atsevišķu rakstu par to.

Rekursīvie vaicājumi MySQLā

MySQL nav nekādu speciālu veidu kā tikt galā ar rekursīviem vaicājumiem. Lai tomēr kaut kādā veidā varētu to simulēt, ir nepieciešamas datu modeļa izmaiņas un tad izmantojot neekvivalentos savienojumus un grupēšanu var vairumu problēmu atrisināt. Šeit ir labs raksts angliski par to kā uzturēt hierarhiskus datus MySQL, kādas datu modeļa izmaiņas jāveic un kādi vaicājumi jāraksta. Protams, ka tas tādā gadījumā attiecas uz visām DBVS, jo izmantotie vaicājumu veidi ir vispārlietojami un nav nekas specifisks tieši MySQL. Šo tēmu (vismaz pagaidām) es netaisos izvērst latviski – tā kā, ja kāds MySQL guru gribētu ko darīt šai jomā, – lūdzu, laipni aicināti!🙂 Būtu arī interesanti zināt, kādus vairāk vai mazāk reālus piemērus, piemēram, stāsta, ka draugiem.lv esot uz MySQLa un tur nu rekursija (iespējams fiksētā līmenī, draugi, draugu draugi) spiežas ārā pa visām vīlēm, rakājoties pa interneta plašumiem, var pat atrast šādas tādas aizvēsturiskas ar to saistītas problēmas :)

5 Responses to Rekursīvie vaicājumi

  1. Kaitnieks says:

    Es tikai atceros, ka LU kursā Oracle DBVS man teorētiskajā jautājumā bija jāpastāsta par CONNECT BY. Varēju tikai noplātīt rokas, jo tobrīd par tādu nebiju pat dzirdējis.

  2. Grrr says:

    Es atceros, ka kaut kad man bija jāimplementē līdzīga struktūra MySQLā.

    Godīgi sakot, neatceros precīzi kā, bet risinājums bija izmantot grafu algoritmus, ja nemaldos – sakārtotu koku.

    Proti, katram darbiniekam, lai nodefinētu, piemēram, viņa vietu organizācijā, tiek piešķirts nevis “bossa ID”, bet skaitlis, kas raksturo viņa atrašanās vietu grafā.

    teiksim, bosu bosam tiek piešķirts skaitlis “5”, viņa 1. vietniekam “4”, otrajam “6”, 3ajam “7” utt.

    Tur bija jāseko precīzai shēmai, kā izvēlēties skaitļus, kad tu ievieto datus tabulā. Taču pēc tam tādi vaicājumi, kā piemēram: kas ir šī cilvēka padotie bija vienkārši salīdzinot viņa atrašanās pozīciju ar pārējām: position < PERSON_position

    Diemžēl matemātiku uz to brīdi nesapratu (patlaban to tikai mācos), bet realizācija izdevās arī pusakli sekojot instrukcijām.

  3. Gints Plivna says:

    @Kaitnieks
    Njā man laikam tik sarežģītus jautājumus tur neuzdeva, vai arī es tos zināju, katrā ziņā vismaz šāda veida priekšmetos nekādu līdzīgu sāpi neatceros. Satrp citu pie kā tas bija?
    @Grrr
    Jā iespējams kaut kas līdzīgs kā saitē, ko devu es. Katrā ziņā, ja nejauši izdodas atrast saiti, kur tas aprakstīts, neesi skops, iemet šeit!😉 Šiem algoritmiem ir viens baiss mīnuss – katra izmaiņa prasa arī visu pārējo ierakstu koriģēšanu (iespējams, ka gan var atstāt caurumus, lai dažu ierakstu pievienošana nerada šādas problēmas).

  4. Edgars says:

    He, man ar pirms mēneša bija darīšana ar CONNECT BY klauzu (https://datubazes.wordpress.com/2008/03/20/non-equi-self-join/#comment-311), patiesībā ļoti efektīva iespēja.

  5. Kaitnieks says:

    @Gints
    Tas bija pie Aivara Niedrīša. Priekšmets saucās (precīzi neatceros) DBVS Oracle.

Komentēt

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Mainīt )

Twitter picture

You are commenting using your Twitter account. Log Out / Mainīt )

Facebook photo

You are commenting using your Facebook account. Log Out / Mainīt )

Google+ photo

You are commenting using your Google+ account. Log Out / Mainīt )

Connecting to %s

%d bloggers like this: