Задача: Хранение иерархических деревьев
Исходник: Хранимые процедуры для анализа деревьев, язык: sql [code #162, hits: 9425]
автор: - [добавлен: 17.06.2006]
  1. /*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
  2. /*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
  3. /*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
  4. /*!40101 SET NAMES cp1251 */;
  5.  
  6. SET FOREIGN_KEY_CHECKS=0;
  7.  
  8. DROP DATABASE IF EXISTS `recurs`;
  9.  
  10. CREATE DATABASE `recurs`
  11. CHARACTER SET 'cp1251'
  12. COLLATE 'cp1251_general_ci';
  13.  
  14. USE `recurs`;
  15.  
  16. #
  17. # Structure for the `t_s_komplektnaya_edinitsa` table :
  18. #
  19.  
  20. DROP TABLE IF EXISTS `t_s_komplektnaya_edinitsa`;
  21.  
  22. CREATE TABLE `t_s_komplektnaya_edinitsa` (
  23. `id` int(11) UNSIGNED NOT NULL AUTO_INCREMENT,
  24. `opisanie_reliza` char(100) DEFAULT NULL,
  25. PRIMARY KEY (`id`)
  26. ) ENGINE=InnoDB DEFAULT CHARSET=cp1251;
  27.  
  28. #
  29. # Data for the `t_s_komplektnaya_edinitsa` table (LIMIT 0,500)
  30. #
  31.  
  32. INSERT INTO `t_s_komplektnaya_edinitsa` (`id`, `opisanie_reliza`) VALUES
  33. (1,'1'),
  34. (2,'2'),
  35. (3,'3'),
  36. (4,'4'),
  37. (5,'5'),
  38. (6,'5'),
  39. (7,'7'),
  40. (8,'8'),
  41. (9,'9'),
  42. (10,'10'),
  43. (11,'11'),
  44. (12,'12'),
  45. (13,'13'),
  46. (14,'14'),
  47. (15,'15'),
  48. (16,'16'),
  49. (17,'17'),
  50. (18,'18');
  51.  
  52. COMMIT;
  53.  
  54. #
  55. # Structure for the `t_s_komplektatsiya_sborok` table :
  56. #
  57.  
  58. DROP TABLE IF EXISTS `t_s_komplektatsiya_sborok`;
  59.  
  60. CREATE TABLE `t_s_komplektatsiya_sborok` (
  61. `id` bigint(15) UNSIGNED NOT NULL AUTO_INCREMENT,
  62. `sborka` int(11) UNSIGNED DEFAULT NULL,
  63. `sub_sborka_detal` int(11) UNSIGNED DEFAULT NULL,
  64. `k_vo` tinyint(1) UNSIGNED NOT NULL,
  65. `tst` int(11) DEFAULT NULL,
  66. `tst1` int(11) DEFAULT NULL,
  67. PRIMARY KEY (`id`),
  68. UNIQUE KEY `uissd` (`sborka`,`sub_sborka_detal`),
  69. KEY `sborka` (`sborka`),
  70. KEY `sub_sborka_detal` (`sub_sborka_detal`),
  71. CONSTRAINT `komplektatsiya_sborok_fk` FOREIGN KEY (`sborka`) REFERENCES `t_s_komplektnaya_edinitsa` (`id`) ON DELETE SET NULL ON UPDATE CASCADE,
  72. CONSTRAINT `komplektatsiya_sborok_fk1` FOREIGN KEY (`sub_sborka_detal`) REFERENCES `t_s_komplektnaya_edinitsa` (`id`) ON DELETE SET NULL ON UPDATE CASCADE
  73. ) ENGINE=InnoDB DEFAULT CHARSET=cp1251;
  74.  
  75.  
  76.  
  77. #
  78. # Data for the `t_s_komplektatsiya_sborok` table (LIMIT 0,500)
  79. #
  80.  
  81. INSERT INTO `t_s_komplektatsiya_sborok` (`id`, `sborka`, `sub_sborka_detal`, `k_vo`, `tst`, `tst1`) VALUES
  82. (1,7,11,1,0,0),
  83. (2,7,3,2,NULL,NULL),
  84. (3,3,9,8,NULL,NULL),
  85. (4,3,10,7,NULL,NULL),
  86. (5,6,3,3,NULL,NULL),
  87. (6,6,12,4,NULL,NULL),
  88. (7,6,13,1,NULL,NULL),
  89. (8,6,16,3,NULL,NULL),
  90. (9,16,14,2,NULL,NULL),
  91. (10,16,15,1,NULL,NULL),
  92. (11,3,5,1,NULL,NULL),
  93. (12,5,1,2,NULL,NULL),
  94. (13,5,2,2,NULL,NULL),
  95. (14,3,17,1,NULL,NULL),
  96. (15,6,17,1,0,0);
  97.  
  98. COMMIT;
  99.  
  100. #
  101. # Definition for the `find_in_all_tree` procedure :
  102. #
  103.  
  104. DROP PROCEDURE IF EXISTS `find_in_all_tree`;
  105.  
  106. CREATE PROCEDURE `find_in_all_tree`(OUT pa INTEGER(11), OUT ch INTEGER(11), rooten BIGINT(20), testing BIGINT(20))
  107. NOT DETERMINISTIC
  108. SQL SECURITY DEFINER
  109. COMMENT 'Проверка на число вхождений'
  110. BEGIN
  111. DECLARE buf INTEGER(11);
  112. SET pa:=-1;
  113. SET ch:=-1;
  114. IF -- проверка параметров на правильность
  115. (`rooten`<1) OR (`testing`<1)
  116. OR (rooten = testing)
  117. OR (IFNULL(rooten, 0) = 0)
  118. OR (IFNULL(testing , 0) = 0)
  119. THEN -- если ошибка
  120. SET pa:=-1;
  121. SET ch:=-1;
  122. ELSE -- выполняем поиск
  123.  
  124.  
  125. CALL `getSubtree`(`rooten` ,'1','child');
  126. SELECT COUNT(*) INTO pa FROM test02 WHERE i_am = rooten;
  127. DELETE FROM test02;
  128. CALL `getSubtree`(`testing` ,'1','parent');
  129. SELECT COUNT(*) INTO ch FROM test02 WHERE child = testing;
  130. DROP TABLE IF EXISTS test02;
  131.  
  132. END IF;
  133. END;
  134.  
  135. #
  136. # Definition for the `find_in_tree` procedure :
  137. #
  138.  
  139. DROP PROCEDURE IF EXISTS `find_in_tree`;
  140.  
  141. CREATE PROCEDURE `find_in_tree`(OUT find INTEGER(11), rooten INTEGER(11), testing INTEGER(11), type_analyze ENUM('parent','child'))
  142. NOT DETERMINISTIC
  143. SQL SECURITY DEFINER
  144. COMMENT 'Проверка на число вхождений'
  145. BEGIN
  146. /* ОПИСАНИЕ
  147. Эта процедура нужна для проверки члена testing
  148. на связь с rooten . Это нужно для избежания зацикливания дерева.
  149. В триггере перед вставкой с помощью нее можно проверить
  150. не будет ли вводимое значение зацикливать дерево.
  151. Возвращает количество вхождений по линии потомков или родителей.
  152. Если вернет 0 , то вставка допустима
  153. (в этом случае элемент нигде не состоит или состоит в этом же направлении).
  154. Если не 0, то это зависит от условий.
  155. Если testing планируется вставлять в rooten как потомок,
  156. то testing не должен числиться в родителях и наоборот.
  157. переменная type_analyze влияет на это.
  158. */
  159. DECLARE buf INTEGER(11);
  160. IF -- проверка параметров на правильность
  161. (IFNULL(type_analyze,1) = 1) OR ((type_analyze != 'child') AND (type_analyze != 'parent'))
  162. OR (`rooten`<1) OR (`testing`<1)
  163. OR (IFNULL(rooten ,1) = 1)
  164. OR (IFNULL(testing,1) = 1)
  165. THEN -- если ошибка
  166. SET find:=-1;
  167. SELECT 'НЕВЕРНЫЕ ПАРАМЕТРЫ!' AS `ОШИБКА`;
  168. ELSE -- выполняем поиск
  169. CALL `getSubtree`(`rooten` ,'1',`type_analyze`);
  170. IF type_analyze = 'parent' THEN
  171. SELECT COUNT(i_am) INTO buf FROM test02 WHERE i_am = testing;
  172. ELSE
  173. SELECT COUNT(child) INTO buf FROM test02 WHERE child = testing;
  174. END IF;
  175. DROP TABLE IF EXISTS test02;
  176. SET find:=buf;
  177. END IF;
  178. END;
  179.  
  180. #
  181. # Definition for the `getAllTree` procedure :
  182. #
  183.  
  184. DROP PROCEDURE IF EXISTS `getAllTree`;
  185.  
  186. CREATE PROCEDURE `getAllTree`(INOUT `comp_num` INTEGER(11), INOUT `type_analyze` ENUM('parent','child'))
  187. NOT DETERMINISTIC
  188. SQL SECURITY INVOKER
  189. COMMENT 'Выводит анализ(статистику) дерева деталей'
  190. BEGIN
  191. /*
  192. Возвращает статистику по выбраному дереву(поддереву)
  193. или элементу. Находит всех родителей или детей компонента.
  194. Пользуется базовой процедурой `getSubtree`
  195. Первая колонка содержит номер объекта
  196. Вторая число таких объектов в дереве
  197. Третья строка - применяемость, входимость
  198. Показывает сколько отдельных применений имеет этот элемент.
  199. Или перефразируя, во сколько различных(независимых) поддеревьев
  200. входит элемент с этим идентификатором
  201. */
  202. DECLARE cbuf,bef, aft , que ,cbuf1 , tmp_table_name VARCHAR(50);
  203. DECLARE ibuf, i INTEGER(11);
  204. DECLARE t BIGINT(20);
  205. -- СТУПЕНЬ ПРОВЕРКИ ПАРАМЕТРОВ
  206. IF
  207. (IFNULL(type_analyze,1) = 1) OR ((type_analyze != 'child') AND (type_analyze != 'parent'))
  208. OR (comp_num<1) OR (IFNULL(comp_num ,0) = 0)
  209. THEN
  210. SELECT 'УКАЗАНЫ НЕДОПУСТИМЫЕ ПАРАМЕТРЫ' AS `ОШИБКА_ПЕРЕДАНЫХ_ПАРАМЕТРОВ`;
  211. ELSE
  212. -- рекурсия , где все происходит
  213. CALL `getSubtree`( `comp_num` , '1', `type_analyze`);
  214. -- выборка по результатам действия процедуры
  215. IF (type_analyze = 'parent') THEN
  216. SELECT i_am AS `komponent`,
  217. SUM(k_vo) AS `count`,
  218. COUNT(i_am) AS `entering`
  219. FROM test02 GROUP BY (i_am);
  220. ELSE
  221. SELECT child AS `komponent`,
  222. SUM(k_vo) AS `count`,
  223. COUNT(child) AS `entering`
  224. FROM test02 GROUP BY (child);
  225. END IF;
  226. DROP TABLE test02;
  227. END IF;
  228. END;
  229.  
  230. #
  231. # Definition for the `getSubtree` procedure :
  232. #
  233.  
  234. DROP PROCEDURE IF EXISTS `getSubtree`;
  235.  
  236. CREATE PROCEDURE `getSubtree`(comp_num INTEGER(11), count_comp INTEGER(11), type_analyze ENUM('parent','child'))
  237. NOT DETERMINISTIC
  238. SQL SECURITY INVOKER
  239. COMMENT 'Базовая процедура'
  240. BEGIN
  241. /*
  242. Используя эту процедуру, можно написать любую функцию или процедуру
  243. Рекурсивная составляющая getAllTree.
  244. Анализ всего дерева происходит именно в этой процедуре.
  245. В теле проход по всем веточкам текущего узла.
  246. При рекурсивном вызове происходит переход к следующему узлу.
  247. В качестве параметров получает
  248. Номер узла(comp_num) по чему проводить анализ,
  249. Счет узла(count_num) для подсчета точного числа компонентов,
  250. тип анализа(type_analyze) - режим анализирования.
  251. */
  252. DECLARE `iter`, `cnt1` , `cnt2` INT(4) UNSIGNED; -- счетчик итераций для каждой рекурсии
  253. DECLARE `buf` INTEGER(11);
  254. DECLARE ibuf, i INTEGER(11);
  255. DECLARE t BIGINT(20);
  256. -- Это курсоры для рекурсий
  257. DECLARE `curCNT2` CURSOR FOR SELECT COUNT(*)
  258. FROM `t_s_komplektatsiya_sborok`
  259. WHERE( `t_s_komplektatsiya_sborok`.`sub_sborka_detal` = `comp_num`);
  260. DECLARE `curCNT1` CURSOR FOR SELECT COUNT(*)
  261. FROM `t_s_komplektatsiya_sborok`
  262. WHERE( `t_s_komplektatsiya_sborok`.`sborka` = comp_num);
  263. DECLARE `cur2` CURSOR FOR
  264. SELECT `t_s_komplektatsiya_sborok`.`sborka`
  265. FROM `t_s_komplektatsiya_sborok`
  266. WHERE( `t_s_komplektatsiya_sborok`.`sub_sborka_detal` = `comp_num`);
  267. DECLARE `cur1` CURSOR FOR
  268. SELECT t_s_komplektatsiya_sborok.`sub_sborka_detal`
  269. FROM `t_s_komplektatsiya_sborok`
  270. WHERE( `t_s_komplektatsiya_sborok`.`sborka` = comp_num);
  271. -- Действие
  272. -- Проверка входящих данных на корректность.
  273. -- ПРОВЕРКИА ПАРАМЕТРОВ
  274. IF
  275. (IFNULL(type_analyze,1) = 1) OR ((type_analyze != 'child') AND (type_analyze != 'parent'))
  276. OR (comp_num<1) OR (IFNULL(comp_num ,0) = 0)
  277. THEN
  278. SET t=-9;
  279. -- SELECT 'УКАЗАНЫ НЕДОПУСТИМЫЕ ПАРАМЕТРЫ +' AS `ОШИБКА_ПЕРЕДАНЫХ_ПАРАМЕТРОВ`;
  280. ELSE
  281. CREATE TEMPORARY TABLE IF NOT EXISTS test02
  282. (-- создание с проверкой временной таблицы
  283. i_am INTEGER(11) UNSIGNED NOT NULL,
  284. child INTEGER(11) UNSIGNED NOT NULL,
  285. k_vo INTEGER(11) UNSIGNED NOT NULL
  286. );
  287. IF type_analyze = 'parent' THEN -- ее заполнение
  288. INSERT INTO test02 -- по предкам
  289. SELECT
  290. t_s_komplektatsiya_sborok.sborka,
  291. t_s_komplektatsiya_sborok.sub_sborka_detal,
  292. t_s_komplektatsiya_sborok.k_vo * count_comp
  293. FROM t_s_komplektatsiya_sborok
  294. WHERE t_s_komplektatsiya_sborok.sub_sborka_detal = comp_num;
  295. ELSE
  296. INSERT INTO test02 -- по потомкам
  297. SELECT
  298. t_s_komplektatsiya_sborok.sborka,
  299. t_s_komplektatsiya_sborok.sub_sborka_detal,
  300. t_s_komplektatsiya_sborok.k_vo * count_comp
  301. FROM t_s_komplektatsiya_sborok
  302. WHERE t_s_komplektatsiya_sborok.sborka = comp_num;
  303. END IF;
  304. -- Ищем путем перебора по курсору все подуровни
  305. -- при нахождении оного самовызов с новым сборочным элементом
  306. -- остальные параметры без изменений
  307. SET @iter := 1;
  308. SET @sbuf1 := `type_analyze`;
  309. IF(`type_analyze` = 'child') THEN -- анализируем сборку
  310. -- находим число детей
  311. OPEN `curCNT1`;
  312. FETCH `curCNT1` INTO `cnt1`;
  313. CLOSE `curCNT1`;
  314. IF `cnt1` >0 THEN -- если есть дети
  315. OPEN `cur1`;
  316. SET iter := 0;
  317. WHILE iter < cnt1 DO
  318. FETCH cur1 INTO buf; -- получаем номер очередного элемента
  319. SET @i:= count_comp*`count_this_component`(comp_num, buf);
  320. CALL `getSubtree`(buf , @i, @sbuf1);
  321. SET iter := iter + 1;
  322. END WHILE;
  323. CLOSE `cur1`;
  324. END IF;
  325. ELSE -- анализируем деталь
  326. -- находим число родителей
  327. OPEN `curCNT2`;
  328. FETCH `curCNT2` INTO cnt2;
  329. CLOSE `curCNT2`;
  330. OPEN `cur2`;
  331. SET iter := 0;
  332. WHILE iter < cnt2 DO
  333. -- Ищем по родителям (сборки)
  334. FETCH `cur2` INTO `buf`; -- получаем номер очередного элемента
  335. -- вызываем сами себя для анализа родительской ветви
  336. SET @i:= count_comp * `count_this_component`(buf,comp_num);
  337. CALL `getSubtree`(buf, @i , @sbuf1);
  338. SET iter := iter + 1;
  339. END WHILE;
  340. CLOSE `cur2`;
  341. END IF;
  342. END IF;
  343. END;
  344.  
  345. #
  346. # Definition for the `count_this_component` function :
  347. #
  348.  
  349. DROP FUNCTION IF EXISTS `count_this_component`;
  350.  
  351. CREATE FUNCTION `count_this_component`(iam INTEGER(11), child INTEGER(11))
  352. RETURNS tinyint(4)
  353. NOT DETERMINISTIC
  354. SQL SECURITY INVOKER
  355. COMMENT 'Определяет вхождение заданного компонента'
  356. BEGIN
  357. -- Служебная функция
  358. DECLARE i INT(1);
  359. DECLARE CREC CURSOR FOR SELECT COUNT(*) FROM `t_s_komplektatsiya_sborok`
  360. WHERE `t_s_komplektatsiya_sborok`.`sborka`=iam
  361. AND `t_s_komplektatsiya_sborok`.`sub_sborka_detal` = child;
  362. DECLARE CNT CURSOR FOR SELECT `t_s_komplektatsiya_sborok`.`k_vo`
  363. FROM `t_s_komplektatsiya_sborok`
  364. WHERE `t_s_komplektatsiya_sborok`.`sborka`=iam
  365. AND `t_s_komplektatsiya_sborok`.`sub_sborka_detal` = child;
  366. OPEN CREC;
  367. FETCH CREC INTO i;
  368. CLOSE CREC;
  369. IF i!=1 THEN
  370. RETURN 0;
  371. END IF;
  372. OPEN CNT;
  373. FETCH CNT INTO i;
  374. CLOSE CNT;
  375. RETURN i;
  376. END;
  377.  
  378. CREATE TRIGGER `t_s_komplektatsiya_sborok_before_ins_tr` BEFORE INSERT ON `t_s_komplektatsiya_sborok`
  379. FOR EACH ROW
  380. BEGIN
  381. DECLARE buf, pa, ch INTEGER(11);
  382. SET pa:=-1;
  383. SET ch:=-1;
  384. IF NEW.sborka = NEW.sub_sborka_detal THEN
  385. SET NEW.sborka = 0;
  386. SET NEW.sub_sborka_detal = 0;
  387. ELSE
  388. CREATE TEMPORARY TABLE IF NOT EXISTS test02
  389. (
  390. i_am INTEGER(11) UNSIGNED NOT NULL,
  391. child INTEGER(11) UNSIGNED NOT NULL,
  392. k_vo INTEGER(11) UNSIGNED NOT NULL
  393. );
  394. CALL `getSubtree`(NEW.sborka ,'1','parent');
  395. SELECT COUNT(*) INTO pa FROM test02 WHERE i_am = NEW.sub_sborka_detal;
  396. DELETE FROM test02;
  397. CALL `getSubtree`(NEW.sub_sborka_detal ,'1','child');
  398. SELECT COUNT(*) INTO ch FROM test02 WHERE child = NEW.sborka;
  399. DROP TEMPORARY TABLE IF EXISTS test02;
  400. IF ch != 0 AND pa!=0 THEN
  401. SET NEW.sborka = 0;
  402. SET NEW.sub_sborka_detal = 0;
  403. END IF;
  404. END IF;
  405. END;
  406.  
  407. /*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
  408. /*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */;
  409. /*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */;
Хранимые SQL процедуры для анализа деревьев.
Прямое и обратное направление анализа.
Ищет как общее количество, так и входимость.

>> для MySQL 5.0.18

+добавить реализацию