Untitled
unknown
plain_text
2 years ago
24 kB
3
Indexable
create schema people;
DROP TABLE IF EXISTS people.colleges;
create table people.colleges(id INT primary key, parent_id INT, name TEXT);
COPY people.colleges FROM PROGRAM 'curl "https://raw.githubusercontent.com/kostja/shad/main/homework/graph.csv"' WITH (FORMAT csv);
----------------------------------------------------------------------------------------------
-- 1. Добавить сотрудника.--------------------------------------------------------------------
----------------------------------------------------------------------------------------------
insert into people.colleges(id, parent_id, name)
values (1240604, 1240603, 'test_name');
----------------------------------------------------------------------------------------------
-- 2. Перевести сотрудника из отдела в отдел. В случае перевода руководителя,
-- переводятся все его подчинённые.
----------------------------------------------------------------------------------------------
-- Create Table For Testing
create table people.test(id INT primary key, parent_id INT, name TEXT);
-- Create function for inserting new instances
create or replace function test_table_insert_worker(entry_id int, entry_name TEXT, parent_id int)
returns boolean
language plpgsql as
$func$
begin
insert into people.test(id, parent_id, name)
values (entry_id, parent_id, entry_name);
return FOUND;
end
$func$;
-- Fill test table
select test_table_insert_worker(1, '1', -1);
select test_table_insert_worker(2, '2', 1);
select test_table_insert_worker(3, '3', 2);
select test_table_insert_worker(4, '4', 2);
select test_table_insert_worker(5, '5', 4);
select test_table_insert_worker(6, '6', 4);
select test_table_insert_worker(7, '7', 1);
select test_table_insert_worker(8, '8', 7);
select test_table_insert_worker(9, '9', 7);
select test_table_insert_worker(10, '10', 9);
-- Create transfer function for testing table
create or replace function test_transfer_worker_to_another_department(worker_id int, new_boss_id int)
returns boolean
language plpgsql as
$func$
begin
update people.test
set parent_id = new_boss_id
where id = worker_id;
return FOUND;
end
$func$;
-- Test function for test database
select test_transfer_worker_to_another_department(4, 8); -- works fine!
/* test graph looks like:
1
/ \
2 7
/ / \
3 8 9
/ /
4 10
/ \
5 6
*/
-- Create transfer function for initial data
create or replace function transfer_worker_to_another_department(worker_id int, new_boss_id int)
returns boolean
language plpgsql as
$func$
begin
update people.colleges
set parent_id = new_boss_id
where id = worker_id;
return FOUND;
end
$func$;
----------------------------------------------------------------------------------------------
-- 3. Вывести отдел - начальник, все непосредственные подчинённые
----------------------------------------------------------------------------------------------
-- Create selecting department function for test data
create or replace function test_select_department(boss_id int)
returns table (name text)
language plpgsql as
$func$
#variable_conflict use_column
begin
return QUERY
select name from people.test
where id = boss_id or parent_id = boss_id;
end
$func$;
-- Test test_select_department
select * from test_select_department(1); -- works fine
-- Create selecting department function for initial data
create or replace function select_department(boss_id int)
returns table (name text)
language plpgsql as
$func$
#variable_conflict use_column
begin
return QUERY
select name from people.colleges
where id = boss_id or parent_id = boss_id;
end
$func$;
-- Test test_select_department
select * from select_department(1); -- works fine:
-- Amanda Allen
-- Linda Schulz
-- Ronald Mckinley
-- Tyler Le
-- Von Poole
-- Andrea Weilbacher
----------------------------------------------------------------------------------------------
-- 4. Вывести список всех "листовых" узлов дерева (сотрудники не имеющие
-- подчинённых)
----------------------------------------------------------------------------------------------
-- Create selecting leaves function for test data
create or replace function test_select_leaves()
returns table (workers_name text)
language plpgsql as
$func$
begin
return QUERY
select name from people.test as current_entry
where not exists (select * from people.test as iterative_entry
where iterative_entry.parent_id = current_entry.id);
end
$func$;
-- Test test_select_leaves
select * from test_select_leaves(); -- works fine: 3, 5, 6, 10
-- Create selecting leaves function for initial data
create or replace function select_leaves()
returns table (workers_name text)
language plpgsql as
$func$
begin
return QUERY
select name from people.colleges as current_entry
where not exists (select * from people.colleges as iterative_entry
where iterative_entry.parent_id = current_entry.id);
end
$func$;
-- Test select_leaves
select * from select_leaves(); -- works fine: 3, 5, 6, 10
----------------------------------------------------------------------------------------------
-- 5. Вывести список подчинения - руководитель, руководитель руководителя,
-- и т.д. до вершины иерархии
----------------------------------------------------------------------------------------------
-- Create selecting all bosses function for test data
create or replace function test_select_all_bosses(start_worker_id int)
returns table (worker_name text)
language plpgsql as
$func$
begin
return QUERY
with recursive recursion as (
select id, parent_id, name
from people.test
where id = start_worker_id
union all
select people.test.id, people.test.parent_id, people.test.name
from people.test
join recursion
on
people.test.id = recursion.parent_id
) select name from recursion;
end
$func$;
-- Test test_select_all_bosses
select * from test_select_all_bosses(6); -- works fine: 6, 4, 8, 7, 1
-- Create selecting all bosses function for initial data
create or replace function select_all_bosses(start_worker_id int)
returns table (worker_name text)
language plpgsql as
$func$
begin
return QUERY
with recursive recursion as (
select id, parent_id, name
from people.colleges
where id = start_worker_id
union all
select people.colleges.id, people.colleges.parent_id, people.colleges.name
from people.colleges
join recursion
on
people.colleges.id = recursion.parent_id
) select name from recursion;
end
$func$;
-- Test select_all_bosses
select * from select_all_bosses(3); -- works fine:
-- Julie Mcduffy
-- Linda Schulz
-- Amanda Allen
-- Create another function which returns the same but ids instead of names.
-- We will need this function in task 10.
-- For test data:
create or replace function test_select_all_bosses_ids(start_worker_id int)
returns table (worker_id integer)
language plpgsql as
$func$
begin
return QUERY
with recursive recursion as (
select id, parent_id, name
from people.test
where id = start_worker_id
union all
select people.test.id, people.test.parent_id, people.test.name
from people.test
join recursion
on
people.test.id = recursion.parent_id
) select id from recursion;
end
$func$;
select * from test_select_all_bosses_ids(6); -- works fine:
/*
6
4
8
7
1
*/
-- Fore initial data:
create or replace function select_all_bosses_ids(start_worker_id int)
returns table (worker_id integer)
language plpgsql as
$func$
begin
return QUERY
with recursive recursion as (
select id, parent_id, name
from people.colleges
where id = start_worker_id
union all
select people.colleges.id, people.colleges.parent_id, people.colleges.name
from people.colleges
join recursion
on
people.colleges.id = recursion.parent_id
) select id from recursion;
end
$func$;
-- Test select_all_bosses_ids
select * from select_all_bosses_ids(3); -- works fine:
/*
3
2
1
*/
----------------------------------------------------------------------------------------------
-- 6. Вывести количество сотрудников в отделе, *включая подотделы*
----------------------------------------------------------------------------------------------
-- Create counting number of worker in subtree function for test data:
create or replace function test_count_number_of_workers_in_subtree(worker_id int)
returns integer
language plpgsql as
$func$
declare
result integer;
begin
with recursive recursion as (
select id, parent_id
from people.test
where id = worker_id
union all
select people.test.id, people.test.parent_id
from people.test
join recursion
on
people.test.parent_id = recursion.id
) select count(*) into result from recursion;
return result;
end
$func$;
-- Test test_count_number_of_workers_in_subtree
select * from test_count_number_of_workers_in_subtree(4); -- works fine: 3
-- Create counting number of worker in subtree function for initial data:
create or replace function count_number_of_workers_in_subtree(worker_id int)
returns integer
language plpgsql as
$func$
declare
result integer;
begin
with recursive recursion as (
select id, parent_id
from people.colleges
where id = worker_id
union all
select people.colleges.id, people.colleges.parent_id
from people.colleges
join recursion
on
people.colleges.parent_id = recursion.id
) select count(*) into result from recursion;
return result;
end
$func$;
-- Test count_number_of_workers_in_subtree
select * from count_number_of_workers_in_subtree(1); -- works fine: 1240604
----------------------------------------------------------------------------------------------
-- 7. Проверить граф подчинения на отсутствие аномалий (двойное подчинение,
-- отсутствие руководителя и т.д.).
----------------------------------------------------------------------------------------------
-- Create checking for anomalies in graph function for test data
create or replace function test_check_has_no_anomalies()
returns boolean
language plpgsql as
$func$
declare
entries_count integer; -- total number of entries in the database
root_subtree_size integer; -- number of entries in the subtree of entry with parent_id=1
root_id integer;
root_count integer; -- number of entries with parent_id = -1
begin
-- Calculate the total number of entries
select count(*) into entries_count from people.test;
-- Calculate number of entries with no parent
select count(*) into root_count from people.test where parent_id = -1;
if root_count != 1 then
return false; -- no root or more then one root;
end if;
-- Find id of root of the three (entry with parent_id = -1)
select id into root_id from people.test where parent_id = -1;
-- Calculate the size of the subtree of the root
select * into root_subtree_size from test_count_number_of_workers_in_subtree(1);
-- Check that root's subtree contains all entries
if root_subtree_size != entries_count then
return false;
end if;
-- As the graph is connected and every vertex has only one parent and there is a single root
-- than the graph doesn't have cycles
return true;
end
$func$;
-- Test test_check_anomalies on test data
select * from test_check_has_no_anomalies(); -- works fine: true
-- Change test data that the graph has a cycle 8->5->4->8
update people.test set parent_id = 5 where id = 8;
-- Test
select * from test_check_has_no_anomalies(); -- works fine: false
-- Change test data back
update people.test set parent_id = 7 where id = 8;
-- Change test data that the graph has a cycle through the root 1->7->9->10->1
update people.test set parent_id = 10 where id = 1;
-- Test
select * from test_check_has_no_anomalies(); -- works fine: false
-- Change test data back
update people.test set parent_id = -1 where id = 1;
-- Create checking for anomalies in graph function for initial data
create or replace function check_has_no_anomalies()
returns boolean
language plpgsql as
$func$
declare
entries_count integer; -- total number of entries in the database
root_subtree_size integer; -- number of entries in the subtree of entry with parent_id=1
root_id integer;
root_count integer; -- number of entries with parent_id = -1
begin
-- Calculate the total number of entries
select count(*) into entries_count from people.colleges;
-- Calculate number of entries with no parent
select count(*) into root_count from people.colleges where parent_id = -1;
if root_count != 1 then
return false; -- no root or more then one root;
end if;
-- Find id of root of the three (entry with parent_id = -1)
select id into root_id from people.colleges where parent_id = -1;
-- Calculate the size of the subtree of the root
select * into root_subtree_size from count_number_of_workers_in_subtree(1);
-- Check that root's subtree contains all entries
if root_subtree_size != entries_count then
return false;
end if;
-- As the graph is connected and every vertex has only one parent and there is a single root
-- than the graph doesn't have cycles
return true;
end
$func$;
-- Test check_anomalies on initial data
select * from check_has_no_anomalies(); -- works fine: true
----------------------------------------------------------------------------------------------
-- 8. Вывести "ранг" сотрудника - глубину подчинения
----------------------------------------------------------------------------------------------
-- Create selecting worker's rank function for test data
create or replace function test_select_rank(worker_id integer)
returns integer
language plpgsql as
$func$
declare
rank integer;
begin
select count (*) into rank from test_select_all_bosses(worker_id);
return rank;
end
$func$;
-- Test test_check_anomalies on test data
select * from test_select_rank(1); -- works fine: 1
select * from test_select_rank(7); -- works fine: 2
select * from test_select_rank(6); -- works fine: 5
-- Create selecting worker's rank function for initial data
create or replace function select_rank(worker_id integer)
returns integer
language plpgsql as
$func$
declare
rank integer;
begin
select count (*) into rank from select_all_bosses(worker_id);
return rank;
end
$func$;
-- Test check_anomalies on initial data
select * from select_rank(1); -- works fine: 1
select * from select_rank(2); -- works fine: 2
select * from select_rank(10); -- works fine: 10
select * from select_rank(20); -- works fine: 12
select * from select_rank(1240604); -- works fine: 10
----------------------------------------------------------------------------------------------
-- 9. Вывести иерархию в графическом виде (одно значение - на одной
-- строке, отсортировано в порядке подчинения, количество отступов
-- перед именем сотрудника - степень подчинения в иерархии
----------------------------------------------------------------------------------------------
-- Create printing hierarchy function for test data
create or replace function test_print_hierarchy()
returns table(worker_name text)
language plpgsql as
$func$
declare
root_id integer;
begin
-- Find root's id
select id into root_id from people.test where parent_id = -1;
return query
with recursive recursion as ( -- bfs:
select 0 as rank, id, parent_id, name
from people.test
where id = root_id
union all
select rank + 1 as rank, people.test.id, people.test.parent_id, people.test.name
from people.test
join recursion
on
people.test.parent_id = recursion.id
)
select concat(repeat(' ', rank), name) from recursion;
-- select name from recursion;
end
$func$;
-- Test test_print_hierarchy on test data
select * from test_print_hierarchy(); -- works fine:
/*
1
2
7
3
9
8
10
4
5
6
*/
-- Create printing hierarchy function for initial data
create or replace function print_hierarchy()
returns table(worker_name text)
language plpgsql as
$func$
declare
root_id integer;
begin
-- Find root's id
select id into root_id from people.colleges where parent_id = -1;
return query
with recursive recursion as ( -- bfs:
select 0 as rank, id, parent_id, name
from people.colleges
where id = root_id
union all
select rank + 1 as rank, people.colleges.id, people.colleges.parent_id, people.colleges.name
from people.colleges
join recursion
on
people.colleges.parent_id = recursion.id
)
-- have to trim because some names from dataset are with leading space
select concat(repeat(' ', rank), trim(name)) from recursion;
end
$func$;
-- Test check_anomalies on initial data
select * from print_hierarchy(); -- works fine:
/*
Amanda Allen
Linda Schulz
Tyler Le
Ronald Mckinley
Von Poole
Andrea Weilbacher
Julie Mcduffy
Kelly Wilburn
Oscar Rooney
Denise Jolin
Mary Solis
Carola Helt
Elizabeth Leyva
Margie Miller
Josephine Fair
Jennifer Meyer
Alice Morrison
Shawna Atchison
Allen Bernat
...
*/
----------------------------------------------------------------------------------------------
-- 10. Вывести "путь" между двумя сотрудниками - всех непосредственных и
-- промежуточных руководителей сотрудников.
----------------------------------------------------------------------------------------------
-- Create printing path between two entries from test data
create or replace function test_print_path(first_entry_id integer, second_entry_id integer)
returns table(id integer, name text)
language plpgsql as
$func$
declare
root_id integer;
lca_id integer; -- lca stands for least common ancestor
lca_rank integer;
begin
-- Find root's id.
select people.test.id into root_id from people.test where people.test.parent_id = -1;
-- Find path to root from the first worker and intersect it with the path from
-- the second worker to root.
-- Find maximal rank from the intersection set. This will be the rank of lca.
select max(test_select_rank(worker_id)) into lca_rank from (
select worker_id
from test_select_all_bosses_ids(first_entry_id)
intersect
select worker_id
from test_select_all_bosses_ids(second_entry_id)
) intersection;
-- Find the entry from the intersection set with this rank.
select worker_id into lca_id
from (
select worker_id
from test_select_all_bosses_ids(first_entry_id)
intersect
select worker_id
from test_select_all_bosses_ids(second_entry_id)
) intersection
where test_select_rank(worker_id) = lca_rank;
-- Find name by lca_id
return query
select people.test.id, people.test.name from people.test where people.test.id = lca_id;
end
$func$;
-- Test test_print_path on test data
-- test graph looks like:
/*
1
/ \
2 7
/ / \
3 8 9
/ /
4 10
/ \
5 6
*/
select * from test_print_path(5, 10); -- works fine: 7 7
select * from test_print_path(1, 1); -- works fine: 1 1
select * from test_print_path(3, 7); -- works fine: 1 1
select * from test_print_path(6, 8); -- works fine: 8 8
-- Create printing path between two entries for initial data
create or replace function print_path(first_entry_id integer, second_entry_id integer)
returns table(id integer, name text)
language plpgsql as
$func$
declare
root_id integer;
lca_id integer; -- lca stands for least common ancestor
lca_rank integer;
begin
-- Find root's id.
select people.colleges.id into root_id from people.colleges where people.colleges.parent_id = -1;
-- Find path to root from the first worker and intersect it with the path from
-- the second worker to root.
-- Find maximal rank from the intersection set. This will be the rank of lca.
select max(select_rank(worker_id)) into lca_rank from (
select worker_id
from select_all_bosses_ids(first_entry_id)
intersect
select worker_id
from select_all_bosses_ids(second_entry_id)
) intersection;
-- Find the entry from the intersection set with this rank.
select worker_id into lca_id
from (
select worker_id
from select_all_bosses_ids(first_entry_id)
intersect
select worker_id
from select_all_bosses_ids(second_entry_id)
) intersection
where select_rank(worker_id) = lca_rank;
-- Find name by lca_id
return query
select people.colleges.id, people.colleges.name from people.colleges where people.colleges.id = lca_id;
end
$func$;
-- Test print_path on initial data
select * from test_print_path(1240599, 1); -- works fine: 1
select * from test_print_path(1, 1); -- works fine: 1
select * from test_print_path(3, 7); -- works fine: 1
select * from test_print_path(6, 7); -- works fine: 7
select worker_id from select_all_bosses_ids(1240599)
Editor is loading...