数据库 课后习题

DB

数据库常用关系代数符号：https://billc.io/2020/04/latex-relational-algebra/

.

第二章

2.14
a. $\Pi_{person\_name}(\sigma_{company\_name="BigBank"}(works))$
b. $\Pi_{person\_name,\ city}(employee\bowtie\sigma_{company\_name="BigBank"}(works))$
c. $\Pi_{person\_name,\ street,\ city}(employee\bowtie\sigma_{company\_name="BigBank"\land salary>10000}(works))$
d. $\Pi_{person\_name}(employee\bowtie works\bowtie company)$

2.15
a. $\Pi_{loan\_number}(\sigma_{amount>10000}(loan))$
b. $\Pi_{ID}(depositor\bowtie\sigma_{balance>6000}(account))$
c. $\Pi_{ID}(depositor\bowtie\sigma_{balance>6000\land branch\_name="Uptown"}(account))$

2.18
a. $\Pi_{ID,\ name}(\sigma_{dept\_name="Physics"}(instructor))$
b. $\Pi_{ID,\ name}(instructor\bowtie\sigma_{building="Watson"}(department))$
c. $\Pi_{ID,\ name}(\sigma_{dept\_name="Comp.\ Sci."}(course)\bowtie takes\bowtie student)$
d. $\Pi_{ID,\ name}(student\bowtie\sigma_{year=2018}(takes))$
e. $\Pi_{ID,\ name}(student)-\Pi_{ID,\ name}(student\bowtie\sigma_{year=2018}(takes))$

第三章

3.11
a.

select distinct ID, name
from student natural join takes natural course
where course.dept_name='Comp. Sci.'

b.

select ID, name
from student
except
select distinct ID, name
from student natural join takes
where year<2017

c.

select dept_name, max(salary)
from instructor
group by dept_name

d.

select min(max_salary)
from (
    select dept_name, max(salary)
    from instructor
    group by dept_name ) as dept_salary(dept, max_salary)

3.12
a.

insert into course
    values('CS-001', 'Weekly Seminar', 'Comp. Sci.', 0)

b.

insert into section(course_id, sec_id, semester, year)
    values('CS-001', 1, 'Autumn', 2017)

c.

insert into takes(ID, course_id, sec_id, semester, year)
    select ID, 'CS-001', 1, 'Autumn', 2017
    from student
    where dept_name='Comp. Sci.'

d.

delete from takes
where ID=12345 and course_id='CS-001'
    and sec_id=1 and semester='Autumn' and year=2017

e.

delete from takes
where course_id='CS-001'
delete from section
where course_id='CS-001'
delete from course
where course_id='CS-001'

因为section有引用course的外键约束，先删除course会导致违反完整性约束，删除失败。

f.

delete from takes
where course_id in
    select course_id
    from course
    where lower(title) like '%advanced%'

3.15
a.

select ID, customer_name
from customer
except
select C.ID, C.customer_name
from customer as C
where not exists(
    select branch_name
    from branch
    where branch_city='Brooklyn'
    except
    select branch_name
    from customer natural join depositor natural join account
    where customer.ID=C.ID )

b.

select sum(amount)
from loan

c.

select branch_name
from branch
where assets > some(
    select assets
    from branch
    where branch_city='Brooklyn' )

3.16
a.

select ID, person_name
from employee natural join works natural join company

b.

select E.ID, E.person_name
from employee natural join manager_id as E, employee as M
where E.manager_id=M.id
    and E.street=M.street and E.city=M.city

c.

select ID, person_name
from employee natural join works as E
where E.salary > (
    select avg(salary)
    from works
    where company_name=E.company_name )

d.

select company_name, sum(salary)
from works
group by company_name
having sum(salary)<= all (
    select sum(salary)
    from works
    group by company_name )

第四章

4.15

select *
from section join classroom using (building, room_number)

4.16

select ID
from student natural left outer join takes
where course_id is null

4.17

select ID
from student left outer join advisor on ID=s_ID
where i_ID is null

第五章

5.12

import java.util.Scanner;
import static java.lang.System.out;
// JDBC
import java.sql.Connection;
import java.sql.Statement;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.DriverManager;
// mysql
import com.mysql.cj.exceptions.MysqlErrorNumbers;
// class
public class Exercise_5_12
{
    static final String JDBC_DRIVER = "com.mysql.cj.jdbc.Driver";
    static final String DB_URL = "jdbc:mysql://localhost:3306/db_exercise?useSSL=false&allowPublicKeyRetrieval=true&serverTimezone=UTC";
    static Connection conn;
    public static void main(String... args)
    {
        // Connect to DB
        // a.
        Scanner scanner = new Scanner(System.in);
        int ret;
        if ((ret=ConnectDB(scanner))!=0)
        {
            while(ret == MysqlErrorNumbers.ER_ACCESS_DENIED_ERROR)
            {
                out.println("Invalid Password. Access denied.");
                ret = ConnectDB(scanner);
            }
            if (ret != 0) {
                Fail();
                return;
            }
        }
        // b.
        if (!TaskB(scanner)) {
            Fail();
            return;
        }
        // c.
        int id = TaskC(scanner);
        if (id == 0) {
            Fail();
            return;
        }
        // d.
        TaskD(id);
        // Finish and close conn and stmt
        CloseConnection(conn);
        out.println("\nfinish!");
    }
    static void Fail()
    {
        out.println("Operation failed. Please check your config.");
    }
    static boolean TaskB(Scanner scanner)
    {
        boolean done = false;
        ResultSet rs = null;
        PreparedStatement pStmt = null;
        out.print("\nB: type the name: ");
        while(true)
        {
            String query = scanner.next();
            try
            {
                pStmt = conn.prepareStatement(
                    "SELECT id, name FROM instructor "+
                    "WHERE lower(name) like ?"
                );
                pStmt.setString(1, "%"+query+"%");
                rs = pStmt.executeQuery();
                while(rs.next())
                {
                    done = true;
                    out.printf("%d %s\n", rs.getInt(1), rs.getString(2));
                }
            } catch (SQLException se) {
                se.printStackTrace();
                return false;
            } catch (Exception e) {
                e.printStackTrace();
                return false;
            }
            // out.println(pStmt.toString());
            if (done) break;
            out.println("No such ID found.");
        }
        CloseResultSet(rs);
        ClosePreparedStatement(pStmt);
        return true;
    }
    static int TaskC(Scanner scanner)
    {
        int ret = 0;
        ResultSet rs = null;
        PreparedStatement pStmt = null;
        out.print("\nC: type the ID: ");
        int query = scanner.nextInt();
        if (query<0 || query>99999)
        {
            out.println("Invalid id.");
            return 0;
        }
        try
        {
            pStmt = conn.prepareStatement(
                "SELECT id, name FROM instructor "+
                "WHERE id=?"
            );
            pStmt.setInt(1, query);
            rs = pStmt.executeQuery();
            if (rs.next())
            {
                ret = rs.getInt(1);
                out.printf("ID Found:\n%d %s\n", rs.getInt(1), rs.getString(2));
            }
            else
                out.println("No such name found. Program exiting.");
        } catch (SQLException se) {
            se.printStackTrace();
        } catch (Exception e) {
            e.printStackTrace();
        }
        CloseResultSet(rs);
        ClosePreparedStatement(pStmt);
        return ret;
    }
    static void TaskD(int id)
    {
        boolean ret = false;
        ResultSet rs = null;
        PreparedStatement pStmt = null;
        out.printf("\nD: checking ID: %d\n", id);
        try
        {
            pStmt = conn.prepareStatement(
                "WITH temp(course_id, sec_id, semester, year, cnt) AS "+
                    "(SELECT course_id, sec_id, semester, year, count(*) "+
                    "FROM teaches inner join takes using(course_id, sec_id, semester, year) "+
                    "WHERE teaches.id=? "+
                    "GROUP BY course_id, sec_id, semester, year) "+
                "SELECT dept_name, course_id, title, sec_id, semester, year, cnt "+
                "FROM course join temp using(course_id) "+
                "ORDER BY dept_name, course_id, year, semester"
            );
            pStmt.setInt(1, id);
            rs = pStmt.executeQuery();
            while (rs.next())
            {
                ret = true;
                out.printf("%s %s %s %d %s %d %d\n", rs.getString(1), rs.getString(2), rs.getString(3), rs.getInt(4), rs.getString(5), rs.getInt(6), rs.getInt(7));
            }
        } catch (SQLException se) {
            se.printStackTrace();
        } catch (Exception e) {
            e.printStackTrace();
        }
        CloseResultSet(rs);
        ClosePreparedStatement(pStmt);
        if (!ret)
            out.println("He/She hasn't taught any course yet.");
    }
    static int ConnectDB(Scanner scanner)
    {
        out.println("Input your username and password:");
        // String username = "root";
        // String password = "GXB";
        String username = scanner.next();
        String password = scanner.next();
        try
        {
            Class.forName(JDBC_DRIVER);
            conn = DriverManager.getConnection(DB_URL, username, password);
        }
        catch(SQLException se)
        {
            if (se.getErrorCode() != MysqlErrorNumbers.ER_ACCESS_DENIED_ERROR)
                se.printStackTrace();
            return se.getErrorCode();
        }
        catch(Exception e)
        {
            e.printStackTrace();
            return -1;
        }
        return 0;
    }
    static void CloseConnection(Connection conn)
    {
        try {
            if(conn!=null) conn.close();
        } catch(SQLException se) {
            se.printStackTrace();
        }
    }
    static void CloseStatement(Statement stmt)
    {
        try {
            if(stmt!=null) stmt.close();
        } catch(SQLException se) {
            se.printStackTrace();
        }
    }
    static void ClosePreparedStatement(PreparedStatement pStmt)
    {
        try {
            if(pStmt!=null) pStmt.close();
        } catch(SQLException se) {
            se.printStackTrace();
        }
    }
    static void CloseResultSet(ResultSet rs)
    {
        try {
            if(rs!=null) rs.close();
        } catch(SQLException se) {
            se.printStackTrace();
        }
    }
}

5.18
修改call处的参数以查看结果。
使用//作为delimiter。

drop procedure if exists find_name;
create procedure find_name(in keyword varchar(64))
    begin
        select id, name
        from instructor
        where lower(name) like concat('%', keyword, '%');
    end
//
call find_name('ri');//
drop procedure if exists print_error;
create procedure print_error(in Message varchar(100))
    begin
        select 'Error', Message;
    end
//
drop procedure if exists query_teacher_by_id;
create procedure query_teacher_by_id(in query int)
    begin
        declare res int;
        if (query<0 or query>99999) then
            call print_error("Invalid ID");
        else
            select id into res
            from instructor
            where id=query;
            if (res is null) then
                call print_error("No such id");
            else
                WITH temp(course_id, sec_id, semester, year, cnt) AS
                    (SELECT course_id, sec_id, semester, year, count(*)
                    FROM teaches inner join takes using(course_id, sec_id, semester, year)
                    WHERE teaches.id=query
                    GROUP BY course_id, sec_id, semester, year)
                SELECT dept_name, course_id, title, sec_id, semester, year, cnt
                FROM course join temp using(course_id)
                ORDER BY dept_name, course_id, year, semester;
            end if;
        end if;
    end
//
call query_teacher_by_id(10001);//

第六章

6.3

每场比赛参加的队员及其得分，用关系play表示。
派生属性：
参加比赛数played_match(): 统计该player_id在play中出现多少次。
比赛总得分total_score()：统计该player_id在play中的得分之和。

6.20 b

6.23

第七章

7.31
$R'=\{(ABCD), (ABEG)\}$
$AB$只能推出$CDE$，不能推出$G$，所以不是超键。
因为$AB\to CD$，R变为$R'=\{(ABCD), (ABEG)\}$。
$ABCD$是BCNF。没有依赖和$ABEG$有关，所以也是BCNF。所以分解完成。
与$DE$有关的依赖都需连接，所以不是保持依赖的。

判断BCNF好像错了，需要用F的闭包而不是F。所以应该用检测算法（检查所有属性子集）。
分解算法好像也不对？

7.32
a. $CD\to A$。
$CD\to AB$，该依赖去掉$C$或$D$都不再成立，去掉$A$则无法推出$A$，去掉$B$依然可以推出$F$，所以可以去掉$B$。

b. $\{(ABC), (ADEG)\}$
$A\to D$不成立，所以$A$不是超键，由$A\to BC$分为$(ABC), (ADEG)$。$ABC$是BCNF。没有一个依赖的两边都属于$ADEG$，所以也是BCNF。

c. 无损。
$A\to ABC$成立，所以无损。

d. 不保持。
后两个依赖在单独模式都不能验证，所以不是保持依赖的。

7.33
a. $AB$。
右侧都没有$AB$，所以$AB$一定包含于候选键。又因为$AB$是候选键，所以只有$AB$一个。

b. $B\to CDG,\ ADE\to G,\ G\to DE$。
1. $F_c=F$，$AB\to CD$的$A$是无关属性，换为$B\to CD$。$ADE\to GDE$换为$ADE\to G$。
2. 合并两个得到$B\to CDG$。

c. $\{AB,\ BCDG,\ ADEG\}$
1. 令$R_1=BCDG,\ R_2=ADEG,\ R_3=DEG$。
2. 添加$R_4=AB$。
3. 删除$R_3$。

d. $\{AB,\ BCDG,\ ADEG\}$

7.34
a. $DEGH,\ ABEGH$。（少了ACEGH）
右侧都没有$EHG$，所以$EHG$一定包含于候选键。
$EHG$再加一个$D$可推出$ABC$，再加一个$AB$可推出$CD$，所以有两个。

b. $AB\to D,\ D\to C,\ DE\to B,\ DEH\to A,\ AC\to D$。
1. $F_c=F$，$AB\to CD$的$C$是无关属性，换为$AB\to D$。同理$AC\to DC$换为$AC\to D$，$DEH\to AB$换为$DEH\to A$。
2. $F_c$不能再更改。

c. $\{ABD,\ BDE,\ ADEH,\ ACD,\ DEGH\}$
1. 令$R_1=ABD,\ R_2=CD,\ R_3=BED,\ R_4=ADEH,\ R_5=ACD$。
2. 添加$R_4=DEGH$。
3. 删除$R_2$。

d. $\{ABD,\ BDE,\ ADEH,\ ACD,\ DEGH\}$

第十四章 索引

叶节点之间都有连接，但叶子太多改起来很麻烦就不加了

1.
(1, 2, 5, 6, 8, 10, 18, 27, 32, 39, 41, 45, 52, 58, 73, 80, 91, 99)

delete 8.

delete 10.

insert 46.

delete 52

delete 32.

delete 39.

delete 41.

delete 45.

2.
(apple, pear, apricot, peach, grape, banana, pineapple, plum, watermelon, orange, lemon, mango, strawberry, medlar, mulberry, nectarine, cherry, pomegranate)

第十五章 查询处理

15.17
a.
$b_r=40G/4K=10^{7}$块。
$M=40M/4K=10^{4}$块。
第一阶段需$2b_r$次块传输，初始归并段数量$N=\lceil b_r/M\rceil=10^3$个。
归并次数为$cnt=\lceil \log_{\lfloor M/b_b\rfloor-1}N\rceil$。
块传输数$n_t=b_r(2cnt+1)$，寻道次数$n_s=2N+\lceil b_r/b_b\rceil(2cnt-1)$。
块传输时间$t_t=4K/40M=1*10^{-4}s$，寻道时间$t_s=5*10^{-3}s$。
代价$T=t_t*n_t+t_s*n_s$。

$b_b=1$时：
$cnt=\lceil \log_{M-1}N\rceil=1$
$T=10^{3}*(2+1)+5*10^{-3}*(2*10^3+10^7*(2-1))=53010s$。

$b_b=100$时：
$cnt=\lceil \log_{\lfloor M/100\rfloor-1}N\rceil=2$
$T=10^{3}*(4+1)+5*10^{-3}*(2*10^3+10^5*(4-1))=6510s$。

b.
$b_b=1$时：
$cnt=\lceil \log_{M-1}N\rceil=1$遍
$b_b=100$时：
$cnt=\lceil \log_{\lfloor M/100\rfloor-1}N\rceil=2$遍

c.
块传输时间$t_t=4K/400M=1*10^{-5}s$，延迟时间$t_s=2*10^{-5}s$。

$b_b=1$时：
$cnt=\lceil \log_{M-1}N\rceil=1$
$T=10^{2}*(2+1)+2*10^{-5}*(2*10^3+10^7*(2-1))=500.04s$。

$b_b=100$时：
$cnt=\lceil \log_{\lfloor M/100\rfloor-1}N\rceil=2$
$T=10^{2}*(4+1)+2*10^{-5}*(2*10^3+10^5*(4-1))=506.04s$。

15.19
1. 将两棵B+树的叶子节点进行归并，结果文件包含两个关系的元组地址，其中值相同的元组地址会放在一起，在排序时会被一起移动。
2. 将结果文件按一个关系的元组地址进行排序（移动时一起移动值相同的另一个关系的元组地址），然后按顺序读取、将这些元组地址替换为实际的元组。此时结果文件包含已排序的元组和未排序的元组地址。
3. 然后同原算法，对另一个关系的元组地址再进行排序、按序读取。

15.20
设：$n_1=20000$，$n_2=45000$。
包含的块数分别为：$b_1=800$，$b_2=1500$。

1. 设B+树每个叶节点最多包含索引 $k$ 个。
总传输块数：$n_{t1}=\lceil n_1/k\rceil+\lceil n_2/k\rceil+\lceil (n_1+n_2)/25\rceil$
总寻道次数：$n_{s1}=n_{t1}$
结果文件包含的块数$b_r=(n_1+n_2)/25=2300$。

2.
设$M$为缓冲区最大用于排序的块数。
初始归并段数量$N=\lceil b_r/M\rceil$个。
归并次数$cnt=\lceil \log_{\lfloor M/b_b\rfloor-1}N\rceil$。
按序读取、替换元组需要：按序读取原关系的元组、按序读取并写回每个排好序的块。因为交替取这两个块，所以每块都要寻道？
总传输块数：$n_{t2}=2b_r(cnt+1)+b_1+2b_2$
总寻道次数：$n_{s2}=2N+\lceil b_r/b_b\rceil*2cnt+b_1+2b_2$

3.
用到的和第二步的元组数量相同，所以排序代价相同。只不过最后替换时不用写回。
总传输块数：$n_{t3}=2b_r(cnt+1)+b_1+b_2$
总寻道次数：$n_{s3}=2N+\lceil b_r/b_b\rceil*2cnt+b_1+b_2$

第十七章

17.15
$$

17.20
$$

第十八章

18.12
$$

18.25
$$

18.27
$$

第十九章

19.21
$$

19.23
$$

19.25
$$