Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 задачка: анаграммы на sql  [new]
--
Guest
Добрый день!

Озадачился такой задачкой: sql-запрос, возвращающий анаграммы заданного слова. Желательно, чтоб запрос не зависел от длины слова.
Оракл 9

Ваши варианты?)
25 янв 06, 10:25    [2284805]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18484
Переворот строки с помощью PL/SQL! Конкурс!
25 янв 06, 10:33    [2284845]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
Вячеслав Любомудров
Переворот строки
RTFM АНАГРАММА
25 янв 06, 10:36    [2284864]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18484
Упс...

А я ведь даже у сокамерников спросил :-(
25 янв 06, 10:38    [2284885]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
John.D
Member

Откуда: Северск
Сообщений: 991
SQL> desc anag;
 Имя                             Отсут.?  Ввод
 ------------------------------- -------- ----
 WORD                                     VARCHAR2(30)

SQL> select count(*) from anag;

 COUNT(*)
---------
      143

SQL> var :wr varchar2(30)
Недопустимое имя переменной ":wr".
SQL> var wr varchar2(30)
SQL> begin
  2  :wr := 'ЛОЗА';
  3  end;
  4  /

Процедура PL/SQL успешно завершена.

SQL> select word
  2  from anag, (select rownum rn from cat where rownum <= length(:wr))
  3  where length(word) = length(:wr)
  4  and nvl(length(replace(word, substr(:wr, rn, 1), NULL)), 0) =
  5  nvl(length(replace(:wr, substr(:wr, rn, 1), NULL)), 0) 
  6  group by word
  7  having count(*) = length(:wr);

WORD
------------------------------
ЗОЛА
ЛОЗА

SQL> 

В таблице все слова написаны ЗАГЛАВНЫМИ БУКВАМИ, чтобы не заморачиваться с регистром.
25 янв 06, 11:31    [2285248]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
--
Guest
Уточню условия)
хотелось бы получить без словаря список возможных перестановок.

пока придумал только такое решение, не удовлетворяющее условию независимости от длины:
with q as (
select level i, substr('name',level,1) c
from dual
connect by level <= length('name')
)
select distinct q1.c||q2.c||q3.c||q4.c
from q q1, q q2, q q3, q q4
where q1.i <> q2.i
  and q1.i <> q3.i
  and q1.i <> q4.i
  and q2.i <> q3.i
  and q2.i <> q4.i
  and q3.i <> q4.i
; 
25 янв 06, 11:50    [2285373]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
Запрос Ивана дополненный "автоматическим справочником последовательностей букв":
var word varchar2(30)
exec :word := 'рот'
col anagram for a30

select letters as anagram
  from
  ( select replace(sys_connect_by_path(ch, '\'), '\') as letters, level as lvl
      from 
      ( select substr(:word, rownum, 1) as ch from dual connect by level <= length(:word)
      )
      connect by level <= length(:word)
  ),
  ( select rownum as i from dual connect by level <= length(:word)
  )
  where length(replace(letters, substr(:word, i, 1))) = length(replace(:word, substr(:word, i, 1)))
    and lvl = length(:word)
  group by letters
  having count(*) = length(:word)
;

ANAGRAM
------------------------------
орт
отр
рот
рто
тор
тро

6 rows selected.
Для меня загадка, почему в объемлющем запросе нет "ORA-01436: CONNECT BY loop in user data" :)
25 янв 06, 12:28    [2285617]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
Так будет правильней:
Connected to:
Oracle9i Enterprise Edition Release 9.2.0.6.0 - Production


var word varchar2(30)
exec :word := 'арба'
col anagram for a30

select letters as anagram
  from
  ( select replace(sys_connect_by_path(ch, '\'), '\') as letters, level as lvl
      from
      ( select substr(:word, rownum, 1) as ch from dual connect by level <= length(:word)
      )
      connect by level <= length(:word)
  ),
  ( select rownum as i from dual connect by level <= length(:word)
  )
  where nvl(length(replace(letters, substr(:word, i, 1))), 0) = nvl(length(replace(:word, substr(:word, i, 1))), 0)
    and lvl = length(:word)
  group by letters
  having count(distinct i) = length(:word)
;

ANAGRAM
------------------------------
аабр
аарб
абар
абра
араб
арба
баар
бара
браа
рааб
раба
рбаа

12 rows selected.
25 янв 06, 12:41    [2285681]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
--
Guest
замечательно)
хороший "справочник последовательностей букв"
25 янв 06, 13:02    [2285793]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
Elic
Для меня загадка, почему в объемлющем запросе нет "ORA-01436: CONNECT BY loop in user data" :)


I do not know if it is a bug or a feature, but starting 9i Oracle considers "ORA-01436: CONNECT BY loop in user data" only if PRIOR is used:

SQL> select * from v$version;
Oracle8i Enterprise Edition Release 8.1.7.0.0 - Production
PL/SQL Release 8.1.7.0.0 - Production
CORE    8.1.7.0.0       Production
TNS for 32-bit Windows: Version 8.1.7.0.0 - Production
NLSRTL Version 3.4.1.0.0 - Production

SQL> select lpad(' ',2 * (level - 1)) || ename as ename
  2  from emp
  3  start with mgr is null
  4  connect by level < 3;
ERROR:
ORA-01436: CONNECT BY loop in user data



no rows selected

SQL> select * from v$version;
Oracle9i Enterprise Edition Release 9.2.0.1.0 - Production
PL/SQL Release 9.2.0.1.0 - Production
CORE    9.2.0.1.0       Production
TNS for 32-bit Windows: Version 9.2.0.1.0 - Production
NLSRTL Version 9.2.0.1.0 - Production

SQL> select lpad(' ',2 * (level - 1)) || ename as ename
  2  from emp
  3  start with mgr is null
  4  connect by level < 3;
KING
  SMITH
  ALLEN
  WARD
  JONES
  MARTIN
  BLAKE
  CLARK
  SCOTT
  KING
  TURNER
  ADAMS
  JAMES
  FORD
  MILLER

15 rows selected.

SQL> select lpad(' ',2 * (level - 1)) || ename as ename
  2  from emp
  3  start with mgr is null
  4  connect by level < 3 and 1 = prior 1;
ERROR:
ORA-01436: CONNECT BY loop in user data



no rows selected

SQL> select * from v$version;
Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Prod
PL/SQL Release 10.2.0.1.0 - Production
CORE    10.2.0.1.0      Production
TNS for 32-bit Windows: Version 10.2.0.1.0 - Production
NLSRTL Version 10.2.0.1.0 - Production

SQL> select lpad(' ',2 * (level - 1)) || ename as ename
  2  from emp
  3  start with mgr is null
  4  connect by level < 3;
KING
  SMITH
  ALLEN
  WARD
  JONES
  MARTIN
  BLAKE
  CLARK
  SCOTT
  KING
  TURNER
  ADAMS
  JAMES
  FORD
  MILLER

15 rows selected.

SQL> select lpad(' ',2 * (level - 1)) || ename as ename
  2  from emp
  3  start with mgr is null
  4  connect by level < 3 and 1 = prior 1;
ERROR:
ORA-01436: CONNECT BY loop in user data



no rows selected

SQL>

Now it 10g, there is CONNECT BY NOCYCLE:

SQL> var word varchar2(30)
SQL> exec :word := 'arba'

PL/SQL procedure successfully completed.

SQL> col anagram for a30
SQL> select  distinct replace(sys_connect_by_path(ch,'\'),'\')
  2    from (
  3          select  substr(:word, rownum, 1) as ch,
  4                  rownum as ch_position
  5            from  dual
  6            connect by level <= length(:word)
  7         )
  8    where level = length(:word)
  9    connect by nocycle ch_position != prior ch_position
 10  /
arba
braa
baar
raba
bara
abra
abar
aarb
aabr
arab
raab
rbaa

12 rows selected.

SQL> 

SY.
25 янв 06, 19:41    [2287818]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
SY
I do not know if it is a bug or a feature, but starting 9i Oracle considers "ORA-01436: CONNECT BY loop in user data" only if PRIOR is used:
Вот и приходится самим выводить подобные аксиомы из эмпирических данных :)

SY
Now it 10g, there is CONNECT BY NOCYCLE:
Собственно мой запрос есть неожиданный побочный эффект попытки подготовить костяк запроса для последующих намёков на его модификацию под 10g с использованием nocycle.
SY
  9    connect by nocycle ch_position != prior ch_position
10-ки не имею, чтобы проверить и пощупать новые конструкции.
Но судя по документации nocycle не исключает, а игнорирует циклы. И, IMHO, должны были бы быть ещё и строчки вроде 'baba'. Либо я чего-то не понимаю.
26 янв 06, 02:51    [2288375]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Падонак
Member [заблокирован]

Откуда: из лесу
Сообщений: 1775
Elic
SY
I do not know if it is a bug or a feature, but starting 9i Oracle considers "ORA-01436: CONNECT BY loop in user data" only if PRIOR is used:
Вот и приходится самим выводить подобные аксиомы из эмпирических данных :)

SY
Now it 10g, there is CONNECT BY NOCYCLE:
Собственно мой запрос есть неожиданный побочный эффект попытки подготовить костяк запроса для последующих намёков на его модификацию под 10g с использованием nocycle.
SY
  9    connect by nocycle ch_position != prior ch_position
10-ки не имею, чтобы проверить и пощупать новые конструкции.
Но судя по документации nocycle не исключает, а игнорирует циклы. И, IMHO, должны были бы быть ещё и строчки вроде 'baba'. Либо я чего-то не понимаю.

че ты ее не скачаешь?
26 янв 06, 03:25    [2288385]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
Elic
10-ки не имею, чтобы проверить и пощупать новые конструкции.
Но судя по документации nocycle не исключает, а игнорирует циклы. И, IMHO, должны были бы быть ещё и строчки вроде 'baba'. Либо я чего-то не понимаю.


That were my initial thoughts too. However after some testing things with NOCYCLE are quite confusing:

SQL> column ename format a30
SQL> select lpad(' ',2 * (level - 1)) || ename ename,empno
  2  from emp
  3  start with ename = 'KING'
  4  connect by mgr = prior empno;

ENAME                               EMPNO
------------------------------ ----------
KING                                 7839
  JONES                              7566
    SCOTT                            7788
      ADAMS                          7876
    FORD                             7902
      SMITH                          7369
  BLAKE                              7698
    ALLEN                            7499
    WARD                             7521
    MARTIN                           7654
    TURNER                           7844

ENAME                               EMPNO
------------------------------ ----------
    JAMES                            7900
  CLARK                              7782
    MILLER                           7934

14 rows selected.

SQL> update emp set mgr = 7934
  2  where ename = 'KING';

1 row updated.

SQL> select lpad(' ',2 * (level - 1)) || ename ename,empno
  2  from emp
  3  start with ename = 'KING'
  4  connect by mgr = prior empno;

ENAME                               EMPNO
------------------------------ ----------
KING                                 7839
  JONES                              7566
    SCOTT                            7788
      ADAMS                          7876
    FORD                             7902
      SMITH                          7369
  BLAKE                              7698
    ALLEN                            7499
    WARD                             7521
    MARTIN                           7654
    TURNER                           7844

ENAME                               EMPNO
------------------------------ ----------
    JAMES                            7900
  CLARK                              7782
    MILLER                           7934
      KING                           7839
ERROR:
ORA-01436: CONNECT BY loop in user data



15 rows selected.

SQL> select lpad(' ',2 * (level - 1)) || ename ename,empno,connect_by_iscycle
  2  from emp
  3  start with ename = 'KING'
  4  connect by nocycle mgr = prior empno;

ENAME                               EMPNO CONNECT_BY_ISCYCLE
------------------------------ ---------- ------------------
KING                                 7839                  0
  JONES                              7566                  0
    SCOTT                            7788                  0
      ADAMS                          7876                  0
    FORD                             7902                  0
      SMITH                          7369                  0
  BLAKE                              7698                  0
    ALLEN                            7499                  0
    WARD                             7521                  0
    MARTIN                           7654                  0
    TURNER                           7844                  0

ENAME                               EMPNO CONNECT_BY_ISCYCLE
------------------------------ ---------- ------------------
    JAMES                            7900                  0
  CLARK                              7782                  0
    MILLER                           7934                  1

14 rows selected.

SQL> 

As you can see, without NOCYCLE, "CONNECT BY loop in user data" a bit too late:

     KING                           7839

Should not be displayed since it is the first line in second iteration of the loop. Now NOCYCLE. It does not continue, even though docs state:

Oracle® Database SQL Reference
10g Release 2 (10.2)
Hierarchical Queries
The NOCYCLE parameter in the CONNECT BY condition causes Oracle to return the rows in spite of the loop. The CONNECT_BY_ISCYCLE pseudocolumn shows you which rows contain the cycle:

SELECT last_name "Employee", CONNECT_BY_ISCYCLE "Cycle",
   LEVEL, SYS_CONNECT_BY_PATH(last_name, '/') "Path"
   FROM employees
   WHERE level <= 3 AND department_id = 80
   START WITH last_name = 'King'
   CONNECT BY NOCYCLE PRIOR employee_id = manager_id AND LEVEL <= 4;

Employee                   Cycle  LEVEL Path
------------------------- ------ ------ -------------------------
Russell                        1      2 /King/Russell
Tucker                         0      3 /King/Russell/Tucker
Bernstein                      0      3 /King/Russell/Bernstein
Hall                           0      3 /King/Russell/Hall
Olsen                          0      3 /King/Russell/Olsen
Cambrault                      0      3 /King/Russell/Cambrault
Tuvault                        0      3 /King/Russell/Tuvault
Partners                       0      2 /King/Partners
King                           0      3 /King/Partners/King
Sully                          0      3 /King/Partners/Sully
McEwen                         0      3 /King/Partners/McEwen
...


And now CONNECT_BY_ISCYCLE:

same docs
The CONNECT_BY_ISCYCLE pseudocolumn returns 1 if the current row has a child which is also its ancestor. Otherwise it returns 0.


This proves to be not too usefull. Assume Oracle fixes NOCYCLE to specifications. How one would select first iteration of the loop. Not that easy:

WHERE  CONNECT_BY_ISCYCLE = 0

will not display first iteration last row. Wait a minute. While poking around with it I just realized something. It is same way as I said before:

SY
I do not know if it is a bug or a feature, but starting 9i Oracle considers "ORA-01436: CONNECT BY loop in user data" only if PRIOR is used:


It will cycle unless you use PRIOR, however look at CONNECT_BY_ISCYCLE. It is 0 everywhere. So it looks like cycle is determined based on PRIOR relationship, not on going through same row twice. Strange. I did not see Vladimir Begun on this forum lately. Maybe he can shed some light on newest theory behind hierarchical queries. Anyway, below is example without PRIOR:

SQL> set linesize 132
SQL> column ename format a40
SQL> select lpad(' ',2 * (level - 1)) || ename ename,empno,connect_by_iscycle,level
  2  from emp
  3  start with ename = 'KING'
  4  connect by nocycle level < 4;

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
KING                                           7839                  0          1
  SMITH                                        7369                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  ALLEN                                        7499                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  WARD                                         7521                  0          2
    SMITH                                      7369                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  JONES                                        7566                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  MARTIN                                       7654                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  BLAKE                                        7698                  0          2

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  CLARK                                        7782                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  SCOTT                                        7788                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
  KING                                         7839                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  TURNER                                       7844                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  ADAMS                                        7876                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    MILLER                                     7934                  0          3
  JAMES                                        7900                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  FORD                                         7902                  0          2
    SMITH                                      7369                  0          3
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3
  MILLER                                       7934                  0          2
    SMITH                                      7369                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    JONES                                      7566                  0          3
    MARTIN                                     7654                  0          3
    BLAKE                                      7698                  0          3
    CLARK                                      7782                  0          3
    SCOTT                                      7788                  0          3
    KING                                       7839                  0          3
    TURNER                                     7844                  0          3
    ADAMS                                      7876                  0          3
    JAMES                                      7900                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    FORD                                       7902                  0          3
    MILLER                                     7934                  0          3

211 rows selected.

SQL> 

SY.
26 янв 06, 15:54    [2290900]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
One more puzzle with CONNECT_BY_ISCYCLE:

SQL> set linesize 132
SQL> column ename format a40
SQL> select lpad(' ',2 * (level - 1)) || ename ename,empno,connect_by_iscycle,level
  2  from emp
  3  start with ename = 'KING'
  4  connect by nocycle connect_by_iscycle = 0 and mgr = prior empno;

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
KING                                           7839                  0          1
  JONES                                        7566                  0          2
    SCOTT                                      7788                  0          3
      ADAMS                                    7876                  0          4
    FORD                                       7902                  0          3
      SMITH                                    7369                  0          4
  BLAKE                                        7698                  0          2
    ALLEN                                      7499                  0          3
    WARD                                       7521                  0          3
    MARTIN                                     7654                  0          3
    TURNER                                     7844                  0          3

ENAME                                         EMPNO CONNECT_BY_ISCYCLE      LEVEL
---------------------------------------- ---------- ------------------ ----------
    JAMES                                      7900                  0          3
  CLARK                                        7782                  0          2
    MILLER                                     7934                  1          3

14 rows selected.

SQL> 

As you can see, CONNECT BY condition connect_by_iscycle = 0 is completely ignored.

SY.
26 янв 06, 15:59    [2290921]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
Соломон, спасибо за "раскопки". Правда в теоретическом плане ясности об этой интересной кляузе у меня прибивалось немного.
26 янв 06, 17:06    [2291308]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
Elic
Правда в теоретическом плане ясности об этой интересной кляузе у меня прибивалось немного


Same here. It looks like for each answer I get two more questions. That is why I mentioned Vladimir who might have some "inside" information. Also, I will post the question on MetaLink, just in case. MetaLink, in my experience, is not too good in answering theoretical questions.

SY.
26 янв 06, 17:22    [2291434]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
While posting messages on MetaLink, I think I finally got the logic of NOCYCLE. Clue was right there in the name itself. NOCYCLE means do not cycle. So if you have a hierarchical query without NOCYCLE and a cycle is detected Oracle does not know how to handle it and throws ORA-01436. If NOCYCLE is used Oracle simply cuts of part of a branch right at loop point without raising an error (another word it simply does not follow the loop). And that explains why CONNECT_BY_ISCYCLE is set to 1 for the last row in first iteration of the loop. Otherwise, we would not get 1 at all. Now next logical step would be to implement CYCLE.

SY.
26 янв 06, 19:08    [2291948]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
Elic
Member

Откуда:
Сообщений: 29979
SY
NOCYCLE means do not cycle. So if you have a hierarchical query without NOCYCLE and a cycle is detected Oracle does not know how to handle it and throws ORA-01436. If NOCYCLE is used Oracle simply cuts of part of a branch right at loop point without raising an error (another word it simply does not follow the loop). And that explains why CONNECT_BY_ISCYCLE is set to 1 for the last row in first iteration of the loop.
Действительно, всё получается логично. И даже моя первое интуитивное понимание этой клязы тоже было таким. Но чтение доки поставило первое впечатление под сомнение :(

Спасибо ещё раз.
26 янв 06, 19:29    [2292018]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
M_IV
Member

Откуда:
Сообщений: 1303
Elic

var word varchar2(30)
exec :word := 'арба'
col anagram for a30

select letters as anagram
from
( select replace(sys_connect_by_path(ch, '\'), '\') as letters, level as lvl
from
( select substr(:word, rownum, 1) as ch from dual connect by level <= length(:word)
)
connect by level <= length(:word)
),
( select rownum as i from dual connect by level <= length(:word)
)
where nvl(length(replace(letters, substr(:word, i, 1))), 0) = nvl(length(replace(:word, substr(:word, i, 1))), 0)
and lvl = length(:word)
group by letters
==> having count(distinct i) = length(:word)
;[/src]


Respekt!

P.S.: В избранное
26 янв 06, 20:43    [2292223]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
M_IV
Respekt!


No doubt about it.

M_IV
P.S.: В избранное


Yes & no. Yes, since it shows non-traditional possibilities of hierarchical queries. No, since it is not a practical solution. It will be fast if you are "anagraming", let's say Гена. Anagram for Крокодил will take long time. For example, on Sun-Fire-V440 with 4GIG RAM:

10080 rows selected.

Elapsed: 00:52:36.30
SQL> 

It will probably take a day to anagram Чебурашка. This is PL/SQL, not SQL task:

CREATE OR REPLACE
  TYPE string4000_tbl_type IS TABLE OF VARCHAR2(4000);
/
CREATE OR REPLACE
  PACKAGE text_pkg
    IS
        g_anagram_tbl string4000_tbl_type := string4000_tbl_type();
        FUNCTION anagram(
                         p_text VARCHAR2
                        )
          RETURN string4000_tbl_type;
END;
/
CREATE OR REPLACE
  PACKAGE BODY text_pkg
    IS
        PROCEDURE do_it(
                        p_text           VARCHAR2,
                        p_anagram_so_far VARCHAR2
                       )
          IS
              v_text_length NUMBER;
          BEGIN
              v_text_length := LENGTH(p_text);
              IF v_text_length = 1
                THEN
                  g_anagram_tbl.EXTEND;
                  g_anagram_tbl(g_anagram_tbl.COUNT) := p_anagram_so_far || p_text;
                ELSE
                  FOR v_I IN 1..v_text_length LOOP
                    do_it(
                          SUBSTR(p_text,1,v_I - 1) || SUBSTR(p_text,v_I + 1,v_text_length - v_I),
                          p_anagram_so_far || SUBSTR(p_text,v_I,1)
                         );
                  END LOOP;
              END IF;
        END;
        FUNCTION anagram(
                         p_text VARCHAR2
                        )
          RETURN string4000_tbl_type
          IS
          BEGIN
              IF p_text IS NOT NULL
                THEN
                  g_anagram_tbl.DELETE;
                  do_it(
                        p_text,
                        NULL
                       );
              END IF;
              RETURN g_anagram_tbl;
        END;
END;
/

Now

select distinct column_value as anagram
  from table(text_pkg.anagram(:word));

takes:

10080 rows selected.

Elapsed: 00:00:03.22

if :word is Крокодил, And it takes

181440 rows selected.

Elapsed: 00:02:43.94

to anagram Чебурашка.

Why PL/SQL is that faster. A big part of it is PL/SQL populates only N! elements into a collection since it is only interested in N letter combinations. Hierarcical query constructs all combination of 1, 2, ... N letters therefore it creates a tremendous number of rows, which puts a huge strain on GROUP BY. And only then it is then filtered through having count(distinct i) = length(:word).

SY.
P.S. Unfortunately, it looks like there is no way to create recursive pipelined function, or at least I do not know how to. Any attempt of a recursive call results in compilation error:

PLS-00653: aggregate/table functions are not allowed in PL/SQL scope
27 янв 06, 18:29    [2296328]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
evvcom
Member

Откуда: Домодедово
Сообщений: 12
SY
P.S. Unfortunately, it looks like there is no way to create recursive pipelined function, or at least I do not know how to. Any attempt of a recursive call results in compilation error:

PLS-00653: aggregate/table functions are not allowed in PL/SQL scope


А собственно и не надо рекурсивно вызывать pipelined-функцию, достаточно из нее вызвать рекурсивную, которая вернет результат, например, в ассоциативном массиве, а уже этот результат и пайпить.
11 окт 06, 12:27    [3246524]     Ответить | Цитировать Сообщить модератору
 Re: задачка: анаграммы на sql  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
evvcom
А собственно и не надо рекурсивно вызывать pipelined-функцию, достаточно из нее вызвать рекурсивную, которая вернет результат, например, в ассоциативном массиве, а уже этот результат и пайпить.


You made my day.

SY.
11 окт 06, 15:24    [3248170]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить