Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
24 kB
1
Indexable
Never
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)