GoldenLine
Zaloguj się
Adam Woźniak

Adam Woźniak software architect
and developer

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Witam

Mam pytanie, czy (jak? :) w Oracle mozna napisac constraint, który zagwarantuje, że w naszej tabeli przechowującej strukturę drzewiastą, nie będzie ścieżek tworzących cykle?
Constraint?
Materialized view?

Dokładniej:
Mamy tabelę TABELA z dwiema kolumnami:



parent_id child_id

------------------

        1       11

        1       12

       11       21

       11       22


Czyli mamy takie drzewko:



     1

  11    12

21  22


Chodzi o napisanie ograniczenia, aby nie było możliwe stworzenie w tych drzewkach cyklu.

Np. próba dodania następujących wierszy stworzyłoby cykl (którego chcę uniknąć):
[22, 1]
[22, 11]
[22, 12]

Pozdrawiam,
Adam
Link do wypowiedziLink
Jakub Fila

Jakub Fila Inżynieria / finanse
/ zarządzanie

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Nic mi nie wiadomo o jakiejkolwiek funkcji wykrywającej cykle w drzewie, która pozwoliłaby na zastosowanie jej dla takiej tabeli. Musiałbyś więc sam zaimplementować taki algorytm, a następnie stworzyć trigger, który sprawdzałby, czy dla dodanej pary (rodzic, potomek) wygenerowany został cykl.

Moje ew. sugestie, tzn. jak bym się zabrał do tego:
1. W ogólności, to masz graf, nie drzewo, więc należałoby zaimplementować np. algorytm Kruskala i:
- wywołać go na początku i przechować drzewo rozpinające
- po każdym udanym insercie zmodyfikować drzewo rozpinające (to w zasadzie można już zrobić przyrostowo)
2. Przy każdym update sprawdzić, czy nie ma cyklu, napisaną uprzednio funkcją. Teraz, wydaje mi się, że naiwny algorytm szukający cykli miałby złożoność co najmniej N^2, ale dodawany jest jeden węzeł/krawędź, więc przeglądasz tylko te ścieżki, w które wpada nowy wierzchołek/krawędź.
3. Jeśli funkcja wywołana przez trigger zwróci wartość true (niech to znaczy, że jest cykl), to wycofujesz inserta.

Teraz - jeśli masz drzewo rozpinające, to o ile się nie mylę (zweryfikuj pls), starczy sprawdzić, czy w którejś ze ścieżek korzeń->liść drzewa rozpinającego nie pojawia się powtórzenie.

Trochę to zawiłe, ale mam nadzieję, że tok myślenia zrozumiały.

A tu ktoś się podzielił iplementacją algorytmu Kruskala w C++:
http://www.daniweb.com/software-development/cpp/thread...

Pozdr.
Link do wypowiedziLink
Krzysztof Bielecki

Krzysztof Bielecki Senior consultant,
Capgemini Polska

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Tu jest opis funkcji sprawdzającej. Jednak implementacja tego w triggerze :) niesie za sobą obniżenie wydajności. Wszystko zależy od tego jak ma być wykorzystywana tabela.

http://download.oracle.com/docs/cd/E11882_01/server.11...
Link do wypowiedziLink
Adam Woźniak

Adam Woźniak software architect
and developer

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Powinienem wczesniej napisać, że wydajność nie jest tu dla mnie istotna, ponieważ ten constraint chce załozyć na małej tabeli konfiguracyjnej (kilkadziesiąt tys. rekordów), gdzie ilość operacji insert+update będzie bardzo mała (kilkaset operacji miesięcznie).

Jako, że nie zależy mi na wydajności, to mialem nadzieję, że jest jakieś proste i zwięzłe zaklęcie Oraclowe, które takie coś wymusi :)

Zgadzam się również, że jeśli takiego zaklęcia nie ma, to postawione przeze mnie pytanie sprowadza się do klasycznego problemu grafowego niezwiązanego z bazami danych :)

Dziękuję Panowie za Wasze odpowiedzi!
Pozdrawiam,
Adam
Link do wypowiedziLink
Jakub Fila

Jakub Fila Inżynieria / finanse
/ zarządzanie

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Krzysztof Bielecki:
Tu jest opis funkcji sprawdzającej. Jednak implementacja tego w triggerze :) niesie za sobą obniżenie wydajności. Wszystko zależy od tego jak ma być wykorzystywana tabela.

http://download.oracle.com/docs/cd/E11882_01/server.11...

Ale jest możliwość napisania procedury w C i wywołania jej w runtime'a z poziomu trigger'a? Pisanie algorytmu Kruskala w SQL'u, nawet jeśli to oraclowy PL/SQL jest średnim pomysłem :-)

Edit:
http://download.oracle.com/docs/cd/E11882_01/server.11...

Ale to w zasadzie jest to "magiczne zaklęcie", którego przyznam, nie znałem. Pod spodem na pewno siedzi właśnie wspomniany algorytm, który zawsze trochę kosztuje, więc dla dużych tabel i częstych update'ów nie będzie to najwydajniejsze, jednak skoro wydajność nie jest kluczem, to może to być rozwiązanie. Podana przeze mnie droga to na pewno więcej roboty bez uzysku na wydajności.Jakub Fila edytował(a) ten post dnia 25.10.11 o godzinie 14:12
Link do wypowiedziLink
Kamil Stawiarski

Kamil Stawiarski Oracle Certified
Master | Oracle ACE

Temat: Oracle: jak zagwarantować brak cykli w drzewie?

Rozwiązanie na szybko, zakładające że korzeniem drzewa jest child_id=1



SQL> select *

  2  from drzewo;



  PARENT_ID   CHILD_ID

---------- ----------

		    1

	 1	   11

	 1	   12

	11	   21

	11	   22








create or replace trigger trg_cycle

    after insert or update on drzewo

    declare

      v_check number;

    begin

    with v_tree as

    (

    select level, parent_id, child_id, connect_by_iscycle

    from drzewo

    where connect_by_iscycle=1

   start with child_id=1

   connect by nocycle prior child_id=parent_id

   )

   select count(1) into v_check

   from v_tree;

   if v_check>0 then

   	raise_application_error(-20001,'Wykryto cykl');

   end if;

  end;

/






SQL> insert into drzewo values(22,1);

insert into drzewo values(22,1)

            *

ERROR at line 1:

ORA-20001: Wykryto cykl

ORA-06512: at "SH.TRG_CYCLE", line 14

ORA-04088: error during execution of trigger 'SH.TRG_CYCLE'


Ale UWAGA!!! Zdecydowanie nie jest to optymalne wyjście. Ale jeśli koledze nie zależy na wydajności ..... :)Kamil Stawiarski edytował(a) ten post dnia 25.10.11 o godzinie 23:19
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj