Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 5: Xử lý câu truy vấn - Nguyễn Trường Sơn

  πL	
  [σC	
  (R	
  ×	
  S)]	
  	
  	
  	
  	
  
41	
  
Áp dụng quy tắc (tt) 
§  10.	
  Qui	
  tắc	
  δ	
  –  δ(R	
  	
  	
  	
  	
  	
  S)	
  	
  =	
  	
  δ(R)	
  	
  	
  	
  	
  	
  δ(S)	
  –  δ(R	
  ×	
  	
  S)	
  	
  =	
  	
  δ(R)	
  	
  ×	
  	
  δ(S)	
  –  δ[σC	
  (R)]	
  	
  =	
  	
  σC	
  [δ(R)]	
  	
  –  δ(R	
  ∩B	
  S)	
  	
  =	
  	
  δ(R)	
  ∩B	
  S	
  =	
  	
  R	
  ∩B	
  δ(S)	
  =	
  	
  δ(R)	
  ∩B	
  δ(S)	
  
42	
  
Áp dụng quy tắc (tt) 
§  11.	
  Qui	
  tắc	
  ℑ	
  	
  – Cho	
  •  X	
  =	
  tập	
  thuộc	
  tính	
  trong	
  R	
  được	
  gom	
  nhóm	
  •  Y	
  =	
  X	
  ∪	
  {một	
  số	
  thuộc	
  tính	
  khác	
  của	
  R}	
  – Ta	
  có	
  •  δ[Xℑ(R)]	
  	
  =	
  	
  Xℑ(R)	
  •  Xℑ(R)	
  	
  =	
  	
  Xℑ	
  [πY	
  (R)]	
  
43	
  
Xét ví dụ 2 
44	
  
πcusNm 
σCustomer.cusID=Account.cusID ∧ balance=100 
Customer Account 
x 
Xét ví dụ 2 
45	
  
πcusNm 
σbalance=100 
Customer Account 
x 
σCustomer.cusID=Account.cusID 
Qui tắc σ 
Xét ví dụ 2 
46	
  
πcusNm 
σbalance=100 
Customer Account 
x 
σCustomer.cusID=Account.cusID 
Qui tắc σ 
Tương đương phép kết 
có điều kiện 
Xét ví dụ 2 (tt) 
47	
  
πcusNm 
σbalance=100 
Customer Account 
Customer.cusID=Account.cusID 
Xét ví dụ 2 (tt) 
48	
  
Qui tắc σ, πcusNm 
σbalance=100 Customer 
Account 
Customer.cusID=Account.cusID 
Xét ví dụ 2 (tt) 
49	
  
πcusNm, cusID πcusID 
πcusNm 
σbalance=100 Customer 
Account 
Customer.cusID=Account.cusID 
Qui tắc π , 
Nội dung chi tiết 
§  Giới	
  thiệu	
  
§  Phân	
  tích	
  cú	
  pháp	
  -­‐	
  ngữ	
  nghĩa	
  
§  Biến	
  đổi	
  sang	
  Đại	
  số	
  Quan	
  hệ	
  
§  Tối	
  ưu	
  hóa	
  cây	
  truy	
  vấn	
  
§  Ước	
  lượng	
  kích	
  thước	
  cây	
  truy	
  vấn	
  
§  Phát	
  sinh	
  và	
  thực	
  thi	
  mã	
  lệnh	
  
50	
  
Ước lượng kích thước cây truy vấn 
§  Trong	
  quá	
  trình	
  tối	
  ưu	
  hóa	
  câu	
  truy	
  vấn,	
  có	
  thể	
  có	
  nhiều	
  giải	
  pháp	
  khác	
  nhau	
  –  Các	
  giải	
  pháp	
  này	
  ngang	
  nhau	
  về	
  mặt	
  chiến	
  thuật	
  tối	
  ưu	
  hóa	
  –  Chỉ	
  được	
  chọn	
  1	
  giải	
  pháp	
  để	
  thực	
  thi	
  –  Việc	
  lựa	
  chọn	
  không	
  được	
  thực	
  hiện	
  theo	
  cảm	
  tính	
  
§  Do	
  đó,	
  cần	
  một	
  cách	
  đánh	
  giá	
  bằng	
  định	
  lượng	
  à 	
  Ước	
  lượng	
  kích	
  thước	
  cây	
  truy	
  vấn	
  –  Cây	
  truy	
  vấn	
  A	
  tốt	
  hơn	
  cây	
  truy	
  vấn	
  B	
  khi	
  kích	
  thước	
  A	
  nhỏ	
  hơn	
  kích	
  thước	
  B	
  –  Cây	
  truy	
  vấn	
  được	
  chọn	
  để	
  thực	
  thi	
  là	
  cây	
  truy	
  vấn	
  có	
  kích	
  thước	
  nhỏ	
  nhất	
  trong	
  các	
  ứng	
  viên	
  
51	
  
Ước lượng kích thước 
§  Thống	
  kê	
  quan	
  hệ	
  R	
  –  T(R):	
  số	
  bộ	
  trong	
  R	
  –  S(R):	
  tổng	
  số	
  byte	
  của	
  1	
  bộ	
  trong	
  R	
  –  B(R):	
  tổng	
  số	
  block	
  chứa	
  tất	
  cả	
  các	
  bộ	
  của	
  R	
  –  V(R,	
  A):	
  số	
  giá	
  trị	
  khác	
  nhau	
  mà	
  thuộc	
  tính	
  A	
  trong	
  R	
  có	
  thể	
  có	
  
52	
  
Ví dụ 
§  Cho	
  quan	
  hệ	
  R	
  như	
  sau	
  –  A:	
  chuỗi	
  20	
  bytes	
  –  B:	
  số	
  nguyên	
  4	
  bytes	
  –  C:	
  ngày	
  8	
  bytes	
  –  D:	
  chuỗi	
  68	
  bytes	
  –  1	
  block	
  =	
  1024	
  bytes	
  	
  
§  Vậy	
  –  T(R)	
  =	
  5	
  –  S(R)	
  =	
  100	
  –  B(R)	
  =	
  1	
  –  V(R,	
  A)	
  =	
  3,	
  V(R,	
  B)	
  =	
  1	
  –  V(R,	
  C)	
  =	
  5,	
  V(R,	
  D)	
  =	
  4	
  
53	
  
A B C R 
x 1 1 
D 
a 
x 1 2 b 
1 
1 
1 
3 
4 
5 
a 
c 
d 
y 
y 
z 
Ước lượng kích thước (tt) 
§  Ước	
  lượng:	
  	
  W	
  =	
  R1	
  ×	
  R2	
  –  S(W)	
  =	
  S(R1)	
  +	
  S(R2)	
  –  T(W)	
  =	
  T(R1)	
  x	
  T(R2)	
  	
  	
  
§  	
  Ước	
  lượng:	
  	
  W	
  =	
  σZ	
  =	
  val	
  (R)	
  –  S(W)	
  =	
  S(R)	
  –  T(W)	
  =	
  T(R)	
  /	
  V(R,	
  Z)	
  	
  
§  	
  Ước	
  lượng:	
  	
  W	
  =	
  σZ	
  <=	
  val	
  (R)	
  –  T(W)	
  =	
  T(R)	
  /	
  2	
  	
  –  Hoặc	
  T(W)	
  =	
  T(R)	
  /	
  3	
  
54	
  
Inequality	
  comparison	
  	
  
Ví dụ 
§  Cho	
  	
  –  R(A,	
  B,	
  C)	
  –  T(R)	
  =	
  10000	
  –  V(R,	
  A)	
  =	
  50	
  
§  Ước	
  lượng	
  kích	
  thước	
  biểu	
  thức	
  S	
  =	
  σA=10	
  ∧	
  B<20	
  (R)	
  –  T(S)	
  =	
  T(R)	
  /	
  [V(R,	
  A)	
  x	
  3]	
  =	
  10000	
  /	
  [50	
  x	
  3]	
  =	
  67	
  
§  Ước	
  lượng	
  kích	
  thước	
  biểu	
  thức	
  S	
  =	
  σA=10	
  ∨	
  B<20	
  (R)	
  –  Giả	
  sử	
  :	
  •  m1	
  là	
  số	
  bộ	
  thỏa	
  A=10	
  trong	
  R	
  •  m2	
  là	
  số	
  bộ	
  thỏa	
  B<20	
  trong	
  R	
  •  Đặt	
  n	
  =	
  T(R)	
  –  T(S)	
  =	
  n[1	
  -­‐	
  (1	
  -­‐	
  m1/n)(1	
  –	
  m2/n)]	
  
55	
  
Ước lượng kích thước (tt) 
§  Ước	
  lượng:	
  	
  W	
  =	
  R1	
  	
  	
  	
  	
  	
  R2	
  	
  
§  Cho	
  	
  –  X	
  =	
  tập	
  thuộc	
  tính	
  của	
  R1	
  –  Y	
  =	
  tập	
  thuộc	
  tính	
  của	
  R2	
  
§  Xét	
  trường	
  hợp	
  X	
  ∩	
  Y	
  =	
  ∅	
  –  Tương	
  tự	
  W	
  =	
  R1	
  x	
  R2	
  
§  Xét	
  trường	
  hợp	
  X	
  ∩	
  Y	
  =	
  A	
  –  Nếu	
  mọi	
  giá	
  trị	
  của	
  A	
  trong	
  R1	
  đều	
  có	
  trong	
  R2	
  •  T(W)	
  =	
  T(R1)	
  [T(R2)	
  /	
  V(R2,A)]	
  –  Nếu	
  mọi	
  giá	
  trị	
  của	
  A	
  trong	
  R2	
  đều	
  có	
  trong	
  R1	
  •  T(W)	
  =	
  T(R2)	
  [T(R1)	
  /	
  V(R1,A)]	
  –  Tổng	
  quát	
  •  T(W)	
  =	
  T(R1).T(R2)	
  /	
  Max[V(R1,A)	
  ,	
  V(R2,A)]	
   56	
  
Ví dụ 
§  Cho	
  	
  –  R1	
  •  T(R1)	
  =	
  1000	
  •  V(R1,	
  A)	
  =	
  50	
  •  V(R1,	
  B)	
  =	
  100	
  –  R2	
  •  T(R2)	
  =	
  2000	
  •  V(R2,	
  B)	
  =	
  200	
  •  V(R2,	
  C)	
  =	
  300	
  –  R3	
  •  T(R3)	
  =	
  3000	
  •  V(R3,	
  C)	
  =	
  90	
  •  V(R3,	
  D)	
  =	
  500	
  
57	
  
Ví dụ (tt) 
§  Hãy	
  ước	
  lượng	
  U	
  =	
  R1(A,	
  B)	
  	
  	
  	
  	
  R2(B,	
  C)	
  –  T(U)	
  =	
  (1000	
  x	
  2000)/Max(100,200)	
  =	
  10000	
  –  V(U,	
  A)	
  =	
  50	
  –  V(U,	
  B)	
  =	
  100	
  –  V(U,	
  C)	
  =	
  300	
  
§  Hãy	
  ước	
  lượng	
  Z	
  =	
  R1(A,	
  B)	
  	
  	
  	
  	
  R2(B,	
  C)	
  	
  	
  	
  	
  R3(C,	
  D)	
  –  Nhận	
  xét	
  :	
  Z	
  =	
  U(A,B,C)	
  	
  	
  	
  	
  	
  R3(C,	
  D)	
  –  Vậy	
  	
  •  T(Z)	
  =	
  (10000	
  x	
  3000)/Max(300,90)=100000	
  •  V(Z,	
  A)	
  =	
  50	
  •  V(Z,	
  B)	
  =	
  100	
  •  V(Z,	
  C)	
  =	
  90	
  •  V(Z,	
  D)	
  =	
  500	
  
58	
  
Ước lượng kích thước (tt) 
§  Ước	
  lượng:	
  	
  W	
  =	
  R1	
  ∪	
  	
  R2	
  	
  –  Nếu	
  R1	
  và	
  R2	
  chấp	
  nhận	
  giá	
  trị	
  lặp	
  •  T(W)	
  =	
  T(R1)	
  +	
  T(R2)	
  –  Nếu	
  R1	
  và	
  R2	
  không	
  chấp	
  nhận	
  giá	
  trị	
  lặp	
  •  TH1:	
  R1∪	
  R2	
  không	
  tạo	
  giá	
  trị	
  lặp	
  T1(W)	
  =T(R1)	
  +	
  T(R2)	
  •  TH2:	
  R1∪	
  R2	
  có	
  tạo	
  giá	
  trị	
  lặp	
  T2(W)	
  <	
  T(R1)	
  +	
  T(R2)	
  •  Tổng	
  quát	
  :	
  T(W)	
  =	
  [T1(W)	
  +	
  T2(W)]/2	
  
§  Ước	
  lượng:	
  	
  W	
  =	
  R1	
  ∩	
  	
  R2	
  –  TH1	
  :	
  	
  (trường	
  hợp	
  nhỏ	
  nhất)	
  R1	
  ∩	
  R2	
  =	
  ∅	
  thì	
  •  T1(W)	
  =	
  0	
  –  TH2	
  :	
  	
  (trường	
  hợp	
  lớn	
  nhất)	
  R1	
  ∩	
  R2	
  =	
  R1	
  hay	
  R2	
  thì	
  •  T2(W)	
  =	
  T(R1)	
  hay	
  T(R2)	
  –  Tổng	
  quát	
  :	
  T(W)	
  =	
  [T1(W)+T2(W)]	
  /	
  2	
   59	
  
Ước lượng kích thước (tt) 
§  Ước	
  lượng:	
  	
  W	
  =	
  R1	
  –	
  	
  R2	
  –  TH1	
  :	
  	
  (trường	
  hợp	
  lớn	
  nhất)	
  R1	
  –	
  R2	
  =	
  R1	
  thì	
  •  T1(W)	
  =	
  T(R1)	
  –  TH2	
  :	
  	
  (trường	
  hợp	
  nhỏ	
  nhất)	
  R1	
  ∩	
  R2	
  =	
  R2	
  thì	
  •  T2(W)	
  =	
  T(R1)	
  –	
  T(R2)	
  –  Tổng	
  quát	
  :	
  T(W)	
  =	
  [T1(W)+T2(W)]	
  /	
  2	
  =	
  T(R1)	
  –	
  T(R2)/2	
  
§  Ước	
  lượng:	
  W	
  =	
  δ(R)	
  	
  –  Giả	
  sử	
  R(a1,a2,a3,,an)	
  –  Vậy	
  số	
  bộ	
  phân	
  biệt	
  tối	
  đa	
  là	
  Πi∈[1,n]V(R,ai)	
  –  Trường	
  hợp	
  nhỏ	
  nhất	
  :	
  R	
  rỗng	
  à 	
  T(W)	
  =	
  0	
  –  T(W)	
  =	
  Min(T(R)/2	
  ,	
  Πi∈[1,n]V(R,ai))	
  
60	
  
Ước lượng kích thước (tt) 
§  Ước	
  lượng:	
  	
  W	
  =	
  ℑ(R)	
  –  TH1	
  :	
  	
  (trường	
  hợp	
  lớn	
  nhất)	
  số	
  bộ	
  phân	
  biệt	
  trong	
  R	
  cũng	
  là	
  số	
  nhóm	
  •  T1(W)	
  =	
  T(δ(R))	
  –  TH2	
  :	
  	
  (trường	
  hợp	
  nhỏ	
  nhất)	
  R	
  rỗng	
  •  T2(W)	
  =	
  0	
  –  TH3	
  :	
  	
  Toàn	
  bộ	
  R	
  tạo	
  1	
  nhóm	
  •  T3(W)	
  =	
  1	
  –  Tổng	
  quát	
  :	
  T(W)	
  =	
  Min(T(R)/2	
  ,	
  Πi∈[1,n]V(R,ai))	
  
61	
  
Ước lượng kích thước (tt) 
§  Kích	
  thước	
  sau	
  cùng	
  của	
  cây	
  truy	
  vấn	
  	
  –  Là	
  tổng	
  kích	
  thước	
  của	
  phép	
  toán	
  ở	
  tất	
  cả	
  các	
  node,	
  ngoại	
  trừ	
  node	
  lá	
  và	
  node	
  gốc.	
  
62	
  
63	
  
Ví dụ 
§  R(a,	
  b)	
  –  T(R)=5000	
  –  V(R,	
  a)=50	
  –  V(R,	
  b)=100	
  
§  S(b,	
  c)	
  –  T(S)=2000	
  –  V(S,	
  b)=200	
  –  V(S,	
  c)=100	
  
δ 
σa =10 
R S 
δ 
σa =10 
R 
S 
5000 
2000 
100 
1000 
500 
δ δ 
σa =10 
R 
S 
5000 
100 
2000 
1000 50 
250 
1 
2 
Chi phí ở 
nút gốc 
không có ý 
nghĩa 
Chi phí ở 
nút lá 
không có ý 
nghĩa 
1150 
1100 
Nội dung chi tiết 
§  Giới	
  thiệu	
  
§  Phân	
  tích	
  cú	
  pháp	
  -­‐	
  ngữ	
  nghĩa	
  
§  Biến	
  đổi	
  sang	
  Đại	
  số	
  Quan	
  hệ	
  
§  Tối	
  ưu	
  hóa	
  cây	
  truy	
  vấn	
  
§  Ước	
  lượng	
  kích	
  thước	
  cây	
  truy	
  vấn	
  
§  Phát	
  sinh	
  và	
  thực	
  thi	
  mã	
  lệnh	
  
64	
  
Tối ưu hóa cây truy vấn 
65	
  
Phân	
  tích	
  cú	
  pháp	
  
Kiểm	
  tra	
  ngữ	
  nghĩa	
  
Đưa	
  về	
  dạng	
  
Biểu	
  diễn	
  trong	
   Tối	
  ưu	
  hóa	
  
Phát	
  sinh	
  mã	
  
Thực	
  thi	
  mã	
  
Câu truy vấn Kết quả truy vấn 
66	
  
Phát sinh mã (tt) 
§  Từ	
  cây	
  Truy	
  vấn	
  sau	
  bước	
  tối	
  ưu	
  hóa	
  DBMS	
  sẽ	
  	
  –  Phát	
  sinh	
  mã	
  lệnh	
  của	
  ngôn	
  ngữ	
  chủ	
  (ngôn	
  ngữ	
  dùng	
  để	
  viết	
  chính	
  DBMS)	
  để	
  thực	
  thi	
  cây	
  truy	
  vấn	
  ấy	
  –  Các	
  phép	
  toán	
  của	
  Đại	
  số	
  quan	
  hệ	
  •  Được	
  cài	
  đặt	
  trước	
  thành	
  một	
  bộ	
  các	
  hàm	
  (với	
  hệ	
  thống	
  tham	
  số	
  đầy	
  đủ).	
  	
  •  Ví	
  dụ	
  –  Projection	
  (R:	
  Relation,A:	
  Array	
  of	
  Attribute)	
  As	
  Relation	
  –  Selection	
  (R:	
  Relation,C:	
  Array	
  of	
  Condition)	
  As	
  Relation	
  –  	
  –  Việc	
  phát	
  sinh	
  mã	
  lệnh	
  thực	
  chất	
  là	
  việc	
  phát	
  sinh	
  các	
  lời	
  gọi	
  các	
  hàm	
  trên	
  và	
  truyền	
  cho	
  chúng	
  đối	
  số	
  cụ	
  thể	
  
67	
  
Phát sinh mã (tt) 
§  Sắp	
  xếp	
  ngoài	
  –  Việc	
  sắp	
  xếp	
  là	
  cần	
  thiết	
  cho	
  thực	
  thi	
  truy	
  vấn	
  (Vd	
  :	
  Order	
  by,	
  join,	
  union,	
  distinct)	
  –  Có	
  trường	
  hợp	
  yêu	
  cầu	
  truy	
  vấn	
  liên	
  quan	
  thuộc	
  tính	
  không	
  có	
  chỉ	
  mục	
  trên	
  ấy	
  –  Tập	
  tin	
  CSDL	
  lớn	
  à 	
  không	
  chứa	
  đủ	
  trong	
  bộ	
  nhớ	
  chính	
  để	
  sắp	
  xếp	
  
à 	
  Cấn	
  phải	
  sắp	
  xếp	
  ngoài	
  (dùng	
  °ile	
  tạm	
  trên	
  đĩa)	
  –  Thuật	
  toán	
  :	
  merge	
  short	
  •  Ban	
  đầu	
  sắp	
  xếp	
  trong	
  các	
  run	
  nhỏ	
  của	
  tập	
  tin	
  chính	
  •  Sau	
  đó	
  trộn	
  các	
  run	
  nhỏ	
  và	
  lại	
  sắp	
  xếp	
  để	
  có	
  run	
  lớn	
  hơn	
  •  Lặp	
  lại	
  quá	
  trình	
  đến	
  khi	
  chỉ	
  còn	
  1	
  run	
  
68	
  
Phát sinh mã (tt) 
§  Cài	
  đặt	
  hàm	
  phép	
  chọn	
  1	
  điều	
  kiện	
  –  Tìm	
  tuyến	
  tính	
  :	
  Đọc	
  từng	
  mẫu	
  tin	
  và	
  kiểm	
  tra	
  điều	
  kiện	
  chọn	
  –  Nếu	
  điều	
  kiện	
  chọn	
  là	
  so	
  sánh	
  bằng	
  trên	
  thuộc	
  tính	
  là	
  khóa	
  sắp	
  xếp	
  °ile	
  à 	
  tìm	
  nhị	
  phân	
  –  Nếu	
  điều	
  kiện	
  chọn	
  là	
  so	
  sánh	
  bằng	
  trên	
  thuộc	
  tính	
  là	
  khóa	
  có	
  primary	
  index	
  /	
  hash	
  key	
  à 	
  dùng	
  primary	
  index	
  /	
  hash	
  key	
  –  Nếu	
  điều	
  kiện	
  chọn	
  là	
  so	
  sánh	
  bằng	
  trên	
  thuộc	
  tính	
  không	
  là	
  khóa	
  nhưng	
  có	
  clustering	
  index	
  à 	
  dùng	
  clustering	
  index	
  –  Nếu	
  điều	
  kiện	
  chọn	
  không	
  phải	
  so	
  sánh	
  bằng	
  à 	
  dùng	
  Secondary	
  Index	
  –  Nếu	
  điều	
  kiện	
  là	
  so	
  sánh	
  ≤,	
  ≥	
  thì	
  tìm	
  cho	
  điều	
  kiện	
  =	
  trước	
  
69	
  
Phát sinh mã (tt) 
§  Cài	
  đặt	
  hàm	
  phép	
  chọn	
  nhiều	
  điều	
  kiện	
  (nối	
  bởi	
  AND)	
  –  Chọn	
  1	
  điều	
  kiện	
  để	
  thực	
  hiện	
  như	
  phép	
  chọn	
  đơn.	
  Khi	
  có	
  kết	
  quả,	
  loại	
  dần	
  những	
  bộ	
  không	
  thỏa	
  các	
  điều	
  kiện	
  còn	
  lại	
  –  Thực	
  hiện	
  từng	
  điều	
  kiện	
  như	
  từng	
  phép	
  chọn	
  đơn	
  và	
  giao	
  kết	
  quả	
  với	
  nhau	
  
70	
  
Phát sinh mã (tt) 
§  Cài	
  đặt	
  hàm	
  phép	
  kết	
  R	
  	
  	
  	
  	
  	
  R.A=S.B	
  S	
  –  Dùng	
  2	
  vòng	
  lặp	
  lồng	
  nhau	
  :	
  Duyệt	
  mỗi	
  bộ	
  r	
  trong	
  R,	
  duyệt	
  mỗi	
  bộ	
  s	
  trong	
  S	
  và	
  kiểm	
  tra	
  điều	
  kiện	
  r.A=s.B	
  –  Nếu	
  có	
  chỉ	
  mục	
  trên	
  B	
  à 	
  dùng	
  1	
  vòng	
  lặp	
  :	
  Với	
  mỗi	
  bộ	
  r	
  trong	
  R,	
  truy	
  cập	
  trực	
  tiếp	
  (bằng	
  chỉ	
  mục)	
  các	
  bộ	
  s	
  trong	
  S	
  thỏa	
  s.B	
  =	
  r.A	
  –  Nếu	
  R	
  và	
  S	
  đều	
  được	
  sắp	
  xếp	
  vật	
  lý	
  theo	
  A	
  và	
  B	
  thì	
  duyệt	
  trên	
  °ile	
  tương	
  ứng	
  và	
  so	
  khớp	
  các	
  giá	
  trị	
  A	
  và	
  B	
  –  Dùng	
  hàm	
  băm	
  •  Băm	
  trên	
  khóa	
  A	
  à 	
  phân	
  các	
  dòng	
  r	
  trong	
  R	
  vào	
  các	
  lô	
  Ri	
  •  Băm	
  trên	
  khóa	
  B	
  à 	
  phân	
  các	
  dòng	
  s	
  trong	
  S	
  vào	
  các	
  lô	
  Si	
  •  Quét	
  qua	
  Ri	
  và	
  Si	
  và	
  tìm	
  các	
  lô	
  mà	
  Ri.A	
  =	
  Si.B	
  
71	
  
Thực thi mã lệnh (tt) 
§  Hiệu	
  quả	
  của	
  việc	
  thực	
  thi	
  mã	
  lệnh	
  đã	
  phát	
  sinh	
  ở	
  bước	
  trước	
  phụ	
  thuộc	
  vào	
  2	
  yếu	
  tố	
  –  Mức	
  độ	
  tối	
  ưu	
  của	
  cây	
  truy	
  vấn	
  –  Mức	
  độ	
  tối	
  ưu	
  của	
  các	
  hàm	
  cài	
  đặt	
  các	
  phép	
  toán	
  đại	
  số	
  quan	
  hệ	
  
§  Tối	
  ưu	
  hóa	
  cây	
  truy	
  vấn	
  	
  –  Áp	
  dụng	
  các	
  quy	
  tắc	
  (đã	
  học	
  trong	
  chương	
  này)	
  
§  Mức	
  độ	
  tối	
  ưu	
  của	
  các	
  hàm	
  –  Vận	
  dụng	
  các	
  cấu	
  trúc	
  lưu	
  trữ	
  Dữ	
  liệu	
  (chương	
  5)	
  và	
  các	
  thuật	
  toán	
  truy	
  xuất,	
  tìm	
  kiếm	
  trên	
  các	
  cấu	
  trúc	
  Dữ	
  liệu	
  (môn	
  Cấu	
  trúc	
  Dữ	
  liệu	
  1	
  &	
  2)	
  –  Đặc	
  biệt	
  quan	
  tâm	
  cài	
  đặt	
  cho	
  phép	
  chọn	
  và	
  phép	
  kết	
  
Tài liệu tham khảo 
§  [5]	
  Database	
  systems:	
  the	
  complete	
  book,	
  Hector	
  Garcia-­‐Molina,	
  Jeffrey	
  D.	
  Ullman,	
  Jennifer	
  Widom,	
  Pearson	
  Prentice	
  Hall,	
  2009	
  –  Chapter	
  16.	
  Query	
  Optimizer	
  	
  	
  
72