Cấu trúc cây trong phân tích và thiết kế CSDL

1. GIỚI THIỆU.

Khi bắt tay vào phân tích và thiết kế một Cơ sở dữ liệu, chúng ta thường vạch ra trong đầu mình các kế hoạch thực hiện chung theo một trình tự có tính chất nguyên tắc. Tuy nhiên, song hành với nó, một phần trong suy nghĩ của ta sẽ luôn luôn hiện hữu các yếu tố mang tính chi tiết hơn, như hình ảnh của các bảng sẽ được thiết kế, các trường dữ liệu, cấu trúc dữ liệu nào sẽ được sử dụng, hay những đường ngang dọc của các mối quan hệ ràng buộc,…Tất nhiên, không phải bất cứ chi tiết nhỏ nào cũng để lại trong suy nghĩ của ta những dấu ấn như vậy cả, thực tế là chỉ có những yếu tố mang tính đặc trưng, những yếu tố đã gợi cho ta những hứng thú trong suy nghĩ hay một phát hiện mới tuy rất nhỏ. Tất cả điều đó đã trở nên quen thuộc và ta có thể sử dụng chúng để làm việc một cách dễ dàng, tương tự đối với nhiều đối tượng khác nhau. Mọi sự so sánh đều có sự khập khểnh, tuy nhiên chúng ta có thể ví điều này cũng giống như  khi ta hát lên một bài ca nào đó, điệp khúc, có lẽ là khúc ca mà chúng ta dễ nhớ, dễ thuộc và dễ hát nhất…

Trở lại với vấn đề của chúng ta – Cấu trúc Cây – có lẽ, không phải là một lập trình viên máy tính hay một nhà toán học mới biết đến cấu trúc Cây (Tree structure). Tôi nghĩ, chắc là người nào cũng biết đến nó, vẽ nó ra trên giấy một cách dễ dàng. Ðiều tất yếu là cách nhìn của mỗi người sẽ có những nét khác nhau. Một em bé 6 tuổi hay một chàng sinh viên văn khoa lãng mạn vẽ một -cấu trúc Cây- chúng ta thấy rất tự nhiên, có nghĩa là ngọn ở trên gốc ở dưới, cành lá uốn lượn nhịp nhàng,…Chúng ta thử nhìn lại một lập trình viên khi anh ta vẽ một -cấu trúc Cây-, lạ đấy chứ!, một cây rất đặc biệt, gốc thì ở trên trời còn cành, lá cứ mọc hoài xuống đất,…Nhưng xin đừng cười những chàng trai của chúng ta, họ đang làm một công việc rất lý thú và có ích đấy.

2. CÂY TỔNG QUÁT.

Chúng ta bắt đầu thảo luận về cấu trúc Cây mà chúng ta sẽ dùng những khái niệm này để mô tả cho các ví dụ trong quá trình phân tích và thiết kế.

2.1.  Ðịnh nghĩa Cây.

Một cây là một cấu trúc hữu hạn các nút (node), trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là -quan hệ cha con- (parent-child relationship). Ta có thể định nghĩa Cây một cách đệ qui như sau:

  • Một nút là một cây. Nút đó cũng là gốc của cây ấy
  • Nếu n là một nút và T1, T2, …, Tk là các cây với n1, n2, …, nk lần lượt là các gốc, thì một cây mới T sẽ được tạo lập bằng cách cho nút n trở thành cha của các nút n1, n2, …, nk. Nghĩa là trên cây này n là gốc còn T1, T2, …, Tk là các cành (cây con) (subtrees) của gốc. Khi đó n1, n2, …, nk là các con của nút n.

2.2.  Mô tả Cây.

Tree 1

Theo hình vẽ trên thì:

–          Nút A được gọi là gốc của cây.

–          B, C, D là gốc của các cây con của A.

–          A là cha của B, C, D; B, C, D là con của A

Số các con của một nút được gọi là cấp (degree) của nút đó. Ví dụ: Cấp của A là 3, cấp của H là 2.

Nút có cấp bằng không gọi là nút lá (leaf) hay còn gọi là nút tận cùng (termimal node). Nút không phải là nút lá được gọi là nút nhánh (branch node).

Cấp cao nhất của nút trên cây gọi là cấp của cây đó. Cây được mô tả ở hình trên là cây cấp 3.

Gốc của cây có số mức (level) là một. Nếu nút cha có số mức là l thì nút con có số mức là l+1. Ví dụ A có số mức là 1, B có số mức là 2,…

Chiều cao (height) hay chiều sâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó.

Nếu n1, n2, …, nk là dãy các nút mà ni là cha của ni+1 (1 ( i < k) thì dãy đó là đường đi (path) từ n1 đến nk­. Ðộ dài của đường đi (path length) bằng số nút trên đường đi trừ đi 1.

Nếu thứ tự các cây con được quan tâm thì cây đang xét là cây có thứ tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). Thường thì thứ tự của các cây con của một nút được đặt từ trái sang phải.

3. CẤU TRÚC CÂY TRONG CSDL

Bạn là người luôn quan tâm đến gia đình, đến những người bà con thân thuộc của mình. Nhưng nhiều lúc bạn không thể nhớ hết tất cả những người trong dòng tộc của mình,và có thểõ bạn sẽ bối rối khi so vai vế của mình với những người bà con mà bạn biết rất ít thông tin về họ. Bạn lật cuốn gia phả gia tộc ra, đôi khi bạn mỉm cười một mình –  mình mới 25 tuổi mà lại là ông của một cậu bé trai 5 tuổi,…Vì sao bạn lại có thể biết được điều thú vị này, cũng thật dễ hiểu thôi. Giả sử đây là một đoạn trong gia phả dòng họ của bạn được thể hiện trên một cấu trúc cây, ta tạm gọi là Cây gia phả:

Tree 2

Bạn sẽ khó khăn hơn khi cần giải thích với một người nào đó rằng bạn có một cậu bé 5 tuổi trong gia tộc gọi là ông bằng những câu văn mô tả thứ tự về các mối quan hệ trong dòng họ của bạn. Nhìn lên hình vẽ trên, bạn cảm thấy thế nào? Tôi tin là bạn sẽ cảm thấy thoải mái hơn để có thể diễn đạt một cách dễ dàng những mô tả về gia tộc của bạn.

Bây giờ chúng ta thử xem lướt quá một số đối tượng trong thực tế mà cấu trúc nội tại của nó có dáng dấp của cấu trúc cây mà ta đã mô tả. Cấu trúc của một danh sách vật tư (BOM – Bill of Material) trong các nhà máy, tổ chức nhân sự trong công ty của bạn, tổ chức cấp bậc của các địa phương,…Ta có thể tìm hiểu một ví dụ cụ thể hơn: Một nhà máy chuyên về lắp ráp máy điện toán. Các bộ phận cấu thành một máy điện toán bao gồm: màn hình,  bộ vi xử lý, đĩa cứng, hộp bảo vệ,…một người công nhân làm việc tại công đoạn lắp ráp màn hình của một dây chuyền sản xuất máy điện toán có thể không cần quan tâm đến các bộ phận cấu thành nên một bo mạch chủ (mother board) nhưng nhất thiết anh ta phải biết được chính xác các bộ phận có trong một màn hình. Khi đó, một yêu cầu đặt ra cho các kỹ sư phụ trách thiết kế là phải mô tả thật chính xác, đầy đủ các bộ phận của một máy điện toán, chẳng hạn: màn hình sẽ được lắp ráp từ những linh kiện nào, trong linh kiện này cần bao nhiêu chiếc đinh ốc,… Như vậy, các mối quan hệ phân cấp lúc này đã xuất hiện, nghĩa là chúng ta đã có thể trình bày mối quan hệ giữa các bộ phận mà người kỹ sư kia cần mô tả theo một cấu trúc cây:

Tree 3

Tất nhiên, bước mô tả này chỉ là một phần rất nhỏ trong quá trình mô tả các thành phần dùng để sản xuất một máy điện toán. Còn rất nhiều yêu cầu khác để có thể hoàn thành một bản thiết kế như: cần bao nhiêu cuộn cảm trong một vi mạch, bao nhiêu chiếc đinh ốc để lắp ráp một đĩa cứng, …Một vấn đề mới lúc này đã xuất hiện, đó là việc thiết kế các -Danh sách vật tư” (Bill of Material – BOM), một yêu cầu rất quan trọng trong kế hoạch sản xuất của một nhà máy, tuy nhiên, chúng ta sẽ thảo luận về vấn đề này trong một dịp khác.

Tìm kiếm là một yêu cầu không thể thiếu đối với một Cơ sở dữ liệu, bên cạnh yêu cầu tìm kiếm chính xác, đầy đủ các thông tin thì yếu tố về tốc độ tìm kiếm cũng không kém phần quan trọng. Thêm nữa, yêu cầu tìm kiếm rất đa dạng, để thỏa mãn được điều này thì đòi hỏi những nhà phân tích và thiết kế CSDL phải mô tả đầy đủ các đối tượng thực tế và lưu trữ dữ liệu từ việc phân tích các đối tượng này một cách hợp lý vào CSDL. Ví dụ, công ty của bạn có khoảng 1000 nhân viên: A, B, C, D…, được tổ chức theo hình thức quản lý cấp bậc, nghĩa là, chẳng hạn: nhân viên A dưới quyền quản lý của nhân viên B, nhân viên B lại dưới quyền quản lý của nhân viên C,…Khi đó, một khi người quản lý nhân sự của công ty bạn cần tìm kiếm những nhân viên được quản lý trực tiếp bởi nhân viên A, hay liệt kê tất cả các thuộc cấp của nhân viên B,…bạn sẽ thực sự dễ dàng đáp ứng được yêu cầu này bằng các câu lệnh Select từ CSDL, khi bạn đã có trong tay một cấu trúc Cây trong bảng Nhân viên (employee) được thiết kế trong CSDL. Chúng ta sẽ tìm hiểu kỹ hơn vấn đề này ở những phần sau.

Chúng ta sẽ gặp rất nhiều cấu trúc tương tự như những ví dụ mà ta đã miêu tả: Cấu trúc của một bộ từ điển, cấu trúc bảng Mục lục của một tập sách, cấu trúc của một hệ thống phân công công việc, hệ thống tài khoản kế toán, hệ thống ngân sách trong bản hoạch định tài chính của một công ty, cấu trúc lưu trữ các công văn giấy tờ của phòng hành chính tại một tổ chức – đơn vị nào đó,… Tất cả những cấu trúc này, chúng ta có thể sẽ tìm thấy được rất nhiều điều lý thú khi mô tả chúng theo những hình thái mà chúng ta đã nói từ trước: Cây gia phả, Danh sách vật tư.

4. PHÂN TÍCH CẤU TRÚC CÂY TRONG CSDL

4.1. Phương pháp mô tả truyền thống.

Chúng ta bắt đầu từ khái niệm: -quan hệ phân cấp” (hay còn gọi là quan hệ cha con”) trong định nghĩa của cấu trúc Cây. Ở đây, chúng ta sẽ chỉ quan tâm đến -một Cây” trong khi mô tả, có nghĩa là chỉ có một gốc duy nhất (root). Trong trường hợp, giá trị của nút gốc bằng rỗng (null), để đơn giản chúng ta sẽ thừa nhận sự tồn tại của nó, nhưng chúng ta sẽ không xét đến khi phân tích. Theo đó, với mối quan hệ Cha – Con (parent – child) thì một nút Cha có thể không có, chỉ có 1 hoặc có nhiều hơn một nút Con. Ngược lại, một nút Con chỉ có duy nhất một nút Cha của nó.

Có bạn sẽ đặt câu hỏi rằng: cùng một loại đinh ốc (S1) nhưng có thể được sử dụng trong một chi tiết nào đó khi lắp ráp một màn hình (M1), đồng thời cũng có thể dùng để giữ chặt hộp bảo vệ của một đĩa cứng (D1),…Như vậy, S1 sẽ có đồng thời hai Cha: M1 và D1? Ý kiến này rất có lý, nhưng câu trả lời thì không! Trong trường hợp đó, vai trò của M1 và D1 sẽ khác nhau. Vì sao? Bạn đã có bao giờ thấy một người con được sinh bởi 2 người Cha không? Nhưng bạn vẫn nói rằng người đó có 2 người Cha, tôi thì nghĩ rằng, ít nhất một trong hai người đó là Cha nuôi.

Khi sử dụng các hệ quản trị Cơ sở dữ liệu liên quan (RDBMS – Relational Database Management System) để mô tả mối quan hệ Cha – Con, chúng ta thường dùng mối quan hệ phụ thuộc vào chính đối tượng đó (self-join). Ví dụ: bảng dữ liệu nhân viên trong một hệ quản lý nhân sự thường được mô tả:

CREATE TABLE EMPLOYEE (

EMP_NO      CHAR(15) NOT NULL,

EMP_NAME   VARCHAR(63),

EMP_PARENT         CHAR(15));

ALTER TABLE EMPLOYEE ADD CONSTRAINT PK_EMPLOYEE PRIMARY KEY (EMP_NO);

ALTER TABLE EMPLOYEE ADD  CONSTRAINT “Ràng buộc trên EMP_No” FOREIGN KEY (EMP_PARENT) REFERENCES EMPLOYEE (EMP_NO) ON DELETE SET NULL ON UPDATE CASCADE;

Giả sử dữ liệu có trong bảng Employee được thể hiện:

Tree 4

Ở đây chúng ta chỉ mô tả cấu trúc của bảng Employee một cách đơn giản. Trên thực tế còn nhiều thông tin khác cần đưa vào, và cấu trúc các trường sẽ khác di (Ví dụ: trường Emp_Name sẽ được chia nhỏ hơn: First_Name, Middle_Name, Last_Name). Bây giờ, một yêu cầu từ người quản lý nhân sự: Tìm cấp trên của tất cả các nhân viên. Trong trường hợp chỉ cần liệt kê một cấp trên, câu lệnh tìm kiếm thật dễ dàng:

SELECT B1.emp_no, ‘senior’, E1.emp_no

FROM employee B1, employee E1

WHERE B1.emp_No = E1.Emp_Parent;

Trong trường hợp A là cấp trên của B và C lại là cấp trên của A, như vậy lúc này C cũng là cấp trên của B. Với câu lệnh truy vấn trên bạn không thể biết được rằng C là cấp trên của B. Khi đó, câu lệnh truy vấn của chúng ta sẽ là:

SELECT B1.emp_no, ‘senior’, E2.emp_no

FROM employee B1, employee E1, employee E2

WHERE B1.emp_No = E1.Emp_Parent

AND E1.Emp_No = E2.Emp_Parent;

Trong trường hợp có D là cấp trên của C để thỏa mãn yêu cầu đã được đặt ra, chúng ta cần phải thực hiện tiếp câu lệnh truy vấn:

SELECT B1.emp_no, ‘senior’, E3.emp_no

FROM employee B1, employee E1, employee E2, Employee E3

WHERE B1.emp_No = E1.Emp_Parent

AND E1.Emp_No = E2.Emp_Parent

AND E2.emp_No = E3.Emp_Parent;

Thật không may cho chúng ta nếu như dánh sách cấp trên của D lại cứ dài ra, nghĩa là, có E là cấp trên của D, rồi F lại là cấp trên của E,…Rõ ràng bạn sẽ gặp khó khăn hơn khi thực hiện yêu cầu đã được đặt ra. Tất nhiên, có thể có sự giới hạn trong phân cấp quản lý giữa các nhân viên, nhưng bạn hãy thử đặt yêu cầu này trong cấu trúc của một hệ thống gia phả của một dòng họ. Ví dụ, ta chỉ xét giới hạn một gia phả theo các đời:

Kỵ

Cố

Ông

Cha

Tôi

Con

Cháu

Chắt

Khi đó để có được lời giải, bạn phải dùng một câu truy vấn với 7 điều kiện Where, điều này, dĩ nhiên là được, nhưng sẽ ảnh hưởng rất nhiều đến tốc độ xử lý của CSDL cũng như các yêu cầu về tính chặt chẻ, chính xác trong thiết kế CSDL.

Trở lại với bảng dữ liệu Employee của chúng ta, với yêu cầu chỉ xác định một cấp trên của từng nhân viên, ta chỉ cần thực hiện từng câu lệnh truy vấn như trên tương ứng với từng trường hợp: có một cấp trên, có 2 cấp trên, có 3 cấp trên,…. Nhưng khi có yêu cầu: liệt kê tất cả các cấp trên của một nhân viên, thì bạn cần phải kết hợp các câu lệnh truy vấn như đã miêu tả – bạn có cảm thấy dài dòng và khó khăn hơn không?

Một yêu cầu khác được đặt ra: liệt kê tất cả các nhân viên không là cấp trên của bất cứ một nhân viên nào khác. Câu lệnh truy vấn sẽ là:

SELECT Emp_no, Emp_Name, Emp_Parent

FROM Employee E1

WHERE NOT EXISTS (SELECT *

FROM Employee E2

WHERE E1.emp_No = E2.Emp_Parent);

Trong trường hợp này bạn sẽ dùng 2 câu lệnh truy vấn lồng nhau, bạn sẽ chọn cho mình câu lệnh truy vấn nào, khi có một cấu lệnh truy vấn khác chỉ là một câu Select đơn giản?

4.2. Trái và phải.

Mọi sự vật hiện tượng nào đều có tính hai mặt của nó. Có trời cao thì có đất thấp, có người tốt thì có người xấu, có trước thì có sau,…Tôi có cơ duyên được biết nhiều điều về những câu chuyện như thế này, gần đây, lại được đọc một tài liệu rất hay nói về câu chuyện thiết kế CSDL mà chúng ta đang bàn tới. Tôi thấy lý thú nên tập trung tìm hiểu và ứng dụng vào công việc thiết kế CSDL của mình, kết quả mang lại cũng thật là khả quan.

Bây giờ, chúng ta sẽ quan tâm đến một bảng dữ liệu Nhân viên khác, được thiết kế khác hơn so với bảng dữ liệu mà chúng ta đã bàn luận ở phần -Phương pháp mô tả truyền thống” . Cấu trúc của bảng Employee lúc này sẽ là:

CREATE TABLE EMPLOYEE (

EMP_NO CHAR(15) NOT NULL,

EMP_NAME VARCHAR(63),

EMP_LEFT INTEGER NOT NULL,

EMP_RIGHT INTEGER NOT NULL);

ALTER TABLE EMPLOYEE ADD CONSTRAINT PK_EMPLOYEE PRIMARY KEY (EMP_NO);

Giả sử dữ liệu được mô tả trong bảng Employee như sau:

Tree 5

Trong cấu trúc của bảng Employee vừa được tạo lập, chúng ta thấy xuất hiện 2 trường mới: EMP_LEFT và EMP_RIGHT, đồng thời không có trường EMP_PARENT như trước nữa. Theo cấu trúc mới này, một nhân viên được xem như một nút khi ta thể hiện trên cây, mỗi nút được gắn liền với hai con số, ta tạm gọi là số trái (left_number) và số phải (right_number). Số trái của nút gốc luôn bằng 1 và số phải của nút gốc sẽ bằng (2*n), n là số lượng nút có trên cây. Ðiều này cũng dễ hiểu: bởi vì mỗi lần ta tìm đến một nút nào đó thì phải tìm đến số trái và số phải của nút đó. Nghĩa là, chúng ta sẽ phải thực hiện 2*n lần như vậy khi đi qua hết tất cả các nút của cây. Khi đó, số trái và số phải của một nút sẽ được  đánh dấu như sau:

Số trái  = Số phải kế trước nó + 1;

Số phải = Số trái + k*2 – 1; (k là tổng số nút của cây con có gốc là nút đang xét).

Theo đó chúng ta tạm gọi, cấu trúc mà chúng ta vừa trình bày là: Cấu trúc Left-Right.

Chúng ta dễ dàng nhận thấy sự khác biệt giữa số trái và số phải của nút lá (leaf node) sẽ là: Số trái = Số phải -1.

Bây giờ, bạn có thể liệt kê tất cả các nhân viên không là cấp trên của bất kỳ nhân viên nào khác với họ, bằng câu lệnh truy vấn đơn giản:

Select emp_No, Emp_Name, Emp_Parent

from employee

where Emp_Left = Emp_Right – 1;

Bạn thử so sánh tốc độ xử lý của hai câu truy vấn đã được trình bày qua 2 biểu đồ phân tích ở trên: Hình bên trái mô tả cho câu truy vấn được thực hiện trên cấu trúc Left – Right,  hình bên phải mô tả cho câu truy vấn được thực hiện theo kiểu cấu trúc truyền thống (parent – child).

Tree 6

Bạn cũng có thể liệt kê tất cả các cấp trên của một nhân viên, một cách dễ dàng bằng câu lệnh truy vấn:

For

SELECT P1.Emp_No, P1.Emp_Name, (P1.Emp_Right – P1.Emp_Left)

FROM employee P1, Employee P2

WHERE P2.Emp_no = :Emp_ID

AND P2.Emp_Left BETWEEN P1.Emp_Left AND P1.Emp_Right

into :ID_List, :Name_List, :Emp_Size

do

suspend;

Và cũng có thể tìm được số mức (level) của tất cả các nút có trên cây:

for

Select P2.Emp_No, count(P2.Emp_No) from employee P2, employee P1

WHERE P2.emp_left BETWEEN P1.emp_left AND P1.Emp_right

Group by P2.emp_No

into :EmpNo, :Emplevel

do

for

select Emp_Name from employee

where employee.emp_no =:empNo

into :EmpName

do

suspend;

Bạn có thể tự nghĩ ra cho mình một yêu cầu nào đó, để chọn lọc ra những nhân viên thỏa mãn yêu cầu của bạn. Ví dụ: Tìm tất cả các cấp trên chung cho 2 nhân viên? Hay liệt kê tất cả các cấp dưới của một nhân viên?,…

4.3. Sự kết hợp trong một cấu trúc Cây.

Bạn đã thấy được một số ưu điểm của cấu trúc Left-Right mà chúng ta đang thảo luận. Tuy nhiên chúng tả hãy thử nhìn lại cấu trúc truyền thống (parent – child) mà chúng ta đã thảo luận ở phần Phương pháp mô tả truyền thống. Giả sử chỉ cần liệt kê tất cả những nhân viên là cấp dưới trực tiếp của một nhân viên. Chúng ta chỉ cần sử dụng một câu lệnh truy vấn đơn giản đối với bảng Employee theo kiểu cấu trúc tự tham chiếu self-join:

SELECT B1.emp_no, ‘senior’, E1.emp_no

FROM employee B1, employee E1

WHERE B1.emp_No = E1.Emp_Parent;

Bạn thử dùng cấu trúc Left-Right để thực hiện yêu cầu trên, có lẽ, câu truy vấn mà bạn sẽ viết ra sẽ không tối ưu hơn so với câu truy vấn mà chúng ta vừa trình bày.

Khi một người tiếp cận với CSDL mà bạn đã thiết kế, họ chẳng cần biết cặn kẽ những ý tưởng của bạn, họ chỉ quan tâm đến những gì mà CSDL của bạn được thể hiện trên màn hình máy tính theo các yêu cầu của họ, từ đó họ có thể thực hiện được chức năng tìm kiếm, lưu trữ dữ liệu. Bạn đã từng quan sát cấu trúc trình bày dạng Cây (TreeView) trên các giao diện được thể hiện trên màn hình máy tính. Ví dụ: trình Explore của Window, hay cửa sổ liệt kê đối tượng của các môi trường phát triển phần mềm Delphi, VB,…Khi đó, bạn có nghĩ rằng: nếu ta thể hiện được những cấu trúc Cây mà ta đã mô tả như: danh sách vật tư, phân cấp nhân viên dưới hình thức trình bày dạng Cây trên giao diện người dùng thì người sử dụng sẽ cảm thấy thoái mái hơn nhiều so với khi họ nhìn vào các ô lưới dày đặc số liệu hay không? Trong trường hợp của tôi, tôi sẽ cảm thấy thoải mái và thích thú hơn nhiều.

Cấu trúc truyền thống của Cây – cấu trúc phân cấp (cấu trúc parent-child), thực sự dễ dàng đáp ứng được  yêu cầu mà chúng ta vừa thảo luận. Tôi đã từng dùng cấu trúc Left-Right để thực hiện điều này nhưng không thể tìm thấy được sự thỏa mãn như khi dùng cấu trúc parent – child. Vì vậy trong các bảng được tôi thiết kế tôi thường kết hợp hai cấu trúc này. Ví dụ bảng Employee của chúng ta, sẽ được tạo lập theo phương pháp kết hợp giữa cấu trúc Cha-Con (parent-child) và cấu trúc Số trái -Số phải (left-right).

5. THIẾT KẾ NHƯ THẾ NÀO.

Trên cơ sở các bước phân tích ở phần trên chúng ta thử cùng bắt tay vào thiết kế.

5.1.    Tạo lập các bảng.

Tạo lập bảng Employee (Nhân viên).

/* Table: EMPLOYEE */

CREATE TABLE EMPLOYEE (

EMP_NO CHAR(15) NOT NULL,

EMP_NAME VARCHAR(63),

EMP_LEFT INTEGER,

EMP_RIGHT INTEGER,

EMP_PARENT CHAR(15));

/* Primary keys definition */

ALTER TABLE EMPLOYEE ADD CONSTRAINT PK_EMPLOYEE PRIMARY KEY (EMP_NO);

/* Foreign keys definition */

ALTER TABLE EMPLOYEE ADD  CONSTRAINT “Ràng buộc trên Emp_No” FOREIGN KEY (EMP_PARENT) REFERENCES EMPLOYEE (EMP_NO) ON DELETE SET NULL ON UPDATE CASCADE;

Bạn sẽ dễ dàng nhìn thấy: trong cấu trúc của bảng Employee có sự kết hợp giữa cấu trúc Cha-Con và cấu trúc Số trái-Số phải.

Tạo lập bảng tạm cho Nhân viên

/* Table: TMP_EMP */

CREATE TABLE TMP_EMP (

TMP_EMP_NO CHAR(15) NOT NULL,

TMP_EMP_NAME VARCHAR(63),

TMP_EMP_LEFT INTEGER,

TMP_EMP_RIGHT INTEGER,

TMP_EMP_PARENT CHAR(15));

/* Primary keys definition */

ALTER TABLE TMP_EMP ADD CONSTRAINT PK_TMP_EMP PRIMARY KEY (TMP_EMP_NO);

Mục đích của việc tạo một bảng TMP_EMP – một bảng có cấu trúc tương tự như bảng Employee- là tạo một vùng đệm tạm thời để lưu trữ một số bản ghi của bảng Employee khi chúng ta thực hiện các bước cập nhật một cây con mà chúng ta sẽ bàn tới sau này.

5.2.    Tạo lập các bảng trình bày (View)

Tạo lập bảng trình bày Nhân viên và cấp trên (Bảng trình bày này sẽ rất có lợi cho những cấu truy vấn về sau).

CREATE VIEW EMP_AND_BOSSES(

EMPNO,

EMPNAME,

BOSSNO,

BOSSNAME)

AS

SELECT P2.emp_no, P2.emp_name, P1.emp_no, P1.Emp_Name

FROM employee P1, employee P2

WHERE P2.emp_left BETWEEN P1.emp_left AND P1.emp_right;

5.3.    Xử lý dữ liệu.

5.3.1  Xử lý dữ liệu theo một nút trên Cây.

  • Xóa một nút.

Sau khi xóa một nút trên Cây, có hai trường hợp sẽ xảy ra: Chỉ xóa nút đã được chọn, các nút thuộc cây có gốc là nút được xóa sẽ được cập nhật lại. Trường hợp thứ hai: xóa luôn cả cây con có nút được xóa là gốc, trường hợp này ta sẽ mô tả trong phần xóa một cây con.

 

Trong trường hợp thứ nhất, khi xóa một nút sẽ xuất hiện hai tình huống nếu chúng ta thực hiện việc cập nhật lại dữ liệu:

– Các nút có nút Cha là nút bị xóa sẽ nhận nút Cha của nút bị xóa làm Cha. Ta co thể miễu ta bằng hình vẽ:

Tree 7

– Các nút có nút Cha bị xóa sẽ nhận một nút đặc biệt trong các nút có số mức bằng nhau làm Cha. Nút đặc biệt này sẽ thay thế vị trí của nút Cha vừa bị xóa trong cấu trú Cây. Chúng ta mô tả quá trình này theo hình vẽ:

Tree 8

Tùy theo mỗi yêu cầu mà chúng ta sẽ lựa chọn cách thực hiện khác nhau. Ở đây tôi trình bày cách xóa một Nút theo các điều kiện của tình huống thứ nhất.

Sau khi xóa một Nút, để đảm bảo được các Số trái và số phải của các Nút còn lại trên Cây chúng ta cần phải thực hiện việc cập nhật một số dữ liệu, sau đây là một thủ tục trình bày cách xóa một nút ra khỏi một Cây:

CREATE PROCEDURE DELETE_NODE (

DEL_EMP_NO CHAR(15))

AS

declare variable right_most_sibling INTEGER;

declare variable Left_most_sibling INTEGER;

declare variable EmpParent char(15);

begin

/* Procedure Text */

SELECT emp_right, Emp_Left, Emp_Parent FROM employee

WHERE employee.emp_no = :Del_Emp_No

into :right_most_sibling, :Left_most_sibling, :EmpParent;

Update employee

Set Emp_Right = Emp_Right – 1,

Emp_Left = Emp_Left – 1

Where (Emp_Left > :Left_most_sibling) and (Emp_Right < :right_most_sibling);

Update employee

Set Emp_Left = emp_left – 2

Where (Emp_Right > :right_most_sibling) and (Emp_Left <> 1) and (emp_left > :right_most_sibling);

Update employee

Set Emp_right = emp_Right – 2

Where (Emp_Right >= :right_most_sibling);

Update employee

Set Emp_Parent = :EmpParent

Where Employee.emp_parent = :Del_Emp_No;

Delete from employee where Emp_No = :Del_Emp_No;

suspend;

end

  • Thêm một nút.

Khi thêm một nút vào Cây, có hai trường hợp xảy ra: thứ nhất nút Cha của nút mới thêm vào là một nút đã tồn tại trên Cây; thứ hai: nút Cha của nút với thêm vào có giá trị rỗng (null). Trong trường hợp thứ 2 chúng ta sẽ có một lúc 2 Cây độc lập với nhau (nút với thêm vào, lúc này, được xem như một Cây độc lập).

CREATE PROCEDURE INSERT_NODE (

NEW_EMP_NO CHAR(15),

YOUR_PARENT CHAR(15),

NEW_EMP_NAME VARCHAR(63))

AS

declare variable right_most_sibling INTEGER;

declare variable Left_most_sibling INTEGER;

begin

/* Procedure Text */

SELECT emp_right, Emp_Left FROM employee

WHERE employee.emp_no = :YOUR_PARENT

into :right_most_sibling, :Left_most_sibling;

Update employee

Set Emp_Left = emp_left + 2

Where (Emp_Right > :right_most_sibling) and (Emp_Left <> 1) and (emp_left > :right_most_sibling);

Update employee

Set Emp_right = emp_Right + 2

Where (Emp_Right >= :right_most_sibling);

INSERT INTO Employee (Emp_No, Emp_Parent, Emp_Name, Emp_left, Emp_right)

VALUES (:New_Emp_No, :Your_Parent, :New_emp_Name, :right_most_sibling, (:right_most_sibling + 1));

suspend;

end

  • Cập nhật một nút.

Ðể cập nhật thông tin mới cho một Nút, chúng ta thực hiện như sau: Lưu trữ những thông tin không bị thay đổi, sau đó thực hiện thủ tục Xóa một Nút và Thêm một nút:

CREATE PROCEDURE UPDATE_NODE (

UPDATE_EMP_NO CHAR(15),

UPDATETOPARENT CHAR(15))

AS

declare variable Emp_Parent_Temp char(15);

declare variable Emp_No_Temp char(15);

declare variable Emp_Name_Temp varchar(63);

begin

/* Cap nhat bang left-right khi thay doi left-right tren bang nhan vien*/

SELECT Emp_No, Emp_Parent, Emp_Name FROM employee

WHERE Emp_no = :Update_Emp_No

into :Emp_No_Temp, :Emp_Parent_Temp, :Emp_Name_Temp;

execute procedure delete_node(:UpDate_Emp_No);

execute procedure insert_node(:Emp_No_Temp, :UpdateToParent, :Emp_Name_Temp);

suspend;

end

5.3.2  Xử lý dữ liệu theo một cây con (Subtrees).

  • Xóa một Cây con (Delete Subtree).

CREATE PROCEDURE DROP_TREE (

DOWNSIZED CHAR(15))

AS

declare variable dropemp CHAR(15);

declare variable droplft INTEGER;

declare variable droprgt INTEGER;

begin

/* Delete a SubTree from the Tree */

/*Now save the dropped subtree data with a single select*/

SELECT emp_no, emp_left, emp_right

FROM employee

WHERE emp_no = :downsized

INTO :dropemp, :droplft, :droprgt;

/*The deletion*/

DELETE FROM Employee

WHERE emp_left BETWEEN :droplft and :droprgt;

/* Now close up the gap*/

UPDATE Employee

Set Emp_Left = emp_left – (:droprgt – :droplft + 1)

Where Emp_Left > :Droplft;

UPDATE Employee

Set Emp_right = emp_right – (:droprgt – :droplft + 1)

Where Emp_right > :Droplft;

suspend;

end

Cập nhật một Cây con (Update Subtree).

CREATE PROCEDURE UPDATE_TREE (

UPDATE_EMP_NO CHAR(15),

UPDATETOPARENT CHAR(15))

AS

declare variable EmpNo char(15);

declare variable EmpName varchar(63);

declare variable EmpParent char(15);

declare variable EmpLeft Integer;

declare variable Empright Integer;

declare variable right_most_sibling INTEGER;

declare variable Left_most_sibling INTEGER;

declare variable right_most_sibling_Update INTEGER;

declare variable Left_most_sibling_Update INTEGER;

declare variable Number_Node Integer;

declare variable Temp integer;

begin

/* Cap nhat Toan bo Left_Right tren mot SubTree*/

SELECT emp_right, Emp_Left FROM employee

WHERE employee.emp_no = :Update_Emp_No

into :right_most_sibling, :Left_most_sibling;

Select Count(emp_No) from Employee

where emp_left < :right_most_sibling and emp_left >= :Left_most_sibling

INTO :Number_Node;

for

Select Emp_No, Emp_Name, Emp_Parent, Emp_Left, Emp_Right from employee

where emp_left between :left_most_sibling and :right_most_sibling

into :EmpNo, :EmpName, :EmpParent, :empLeft, :EmpRight

do

Begin

Insert into TMP_EMP (TMP_EMP_NO, TMP_EMP_NAME, TMP_EMP_PARENT, TMP_EMP_LEFT, TMP_EMP_RIGHT)

VALUES (:EmpNo, :EmpName, :EmpParent, :empLeft, :EmpRight);

end

execute procedure drop_tree(:Update_Emp_No);

SELECT emp_right, Emp_Left FROM employee

WHERE employee.emp_no = :UPDATETOPARENT

into :right_most_sibling_Update, :Left_most_sibling_Update;

Update employee

Set Emp_Left = emp_left + :Number_Node * 2

Where (Emp_Right > :right_most_sibling_Update) and (Emp_Left <> 1) and (emp_left > :right_most_sibling_Update);

Update employee

Set Emp_right = emp_Right + :Number_Node * 2

Where (Emp_Right >= :right_most_sibling_Update);

Temp = :right_most_sibling_Update – :Left_most_sibling;

for

Select TMP_EMP_NO, TMP_EMP_NAME, TMP_EMP_PARENT, TMP_EMP_LEFT, TMP_EMP_RIGHT

from TMP_EMP

Order by TMP_EMP_LEFT

Into :EmpNo, :EmpName, :EmpParent, :empLeft, :EmpRight

do

Begin

Insert into EMPLOYEE (EMP_NO, EMP_NAME, EMP_PARENT, EMP_LEFT, EMP_RIGHT)

VALUES (:EmpNo, :EmpName, :EmpParent, :EmpLeft + :Temp, :EmpRight + :Temp);

end

Delete from TMP_EMP;

suspend;

end

5.3.3  Cập nhật Số trái-Số phải dựa vào cấu trúc Parent-Child

Thủ tục này minh họa phương pháp cập nhật lại toàn bộ Số trái – Số phải của một Cây dựa trên cấu trúc phân cấp (Cha-Con) của Cây đó.

  • Cập nhật Số trái – Số phải

CREATE PROCEDURE SEEK_LEFTRIGHT (

IND INTEGER,

PNODE CHAR(15))

RETURNS (

ENDIND INTEGER)

AS

declare variable Node char(15);

declare variable Tmp_Node char(15);

declare variable Tmp_Ind integer;

begin

for select emp_no from employee where emp_parent=:PNode

into :Node

do

begin

/*Danh dau Left*/

update employee set emp_left=:ind where emp_No=:Node;

Ind=:Ind+1;/* Tang len 1*/

/* Gan qua bien tmp de goi ham de qui */

tmp_Ind=:Ind;

tmp_Node=:Node;

/*Danh dau nhung thang con cua Node do*/

select EndInd from seek_leftright(:tmp_Ind, :tmp_Node) into :Ind;

/*Danh dau Right*/

update employee set emp_right =:Ind where emp_No=:Node;

Ind=:Ind+1;/* Tang len 1*/

end

EndInd=:Ind;

suspend;

end

  • Thủ tục xử lý dữ liệu cập nhật

CREATE PROCEDURE UPDATE_LEFTRIGHT

AS

declare variable Count_Rec integer;

declare variable Root Char(15);

begin

Select count(Emp_No) from employee into :Count_Rec;

Update employee

Set Employee.emp_left = 1,

Employee.emp_right = :Count_Rec*2

where Employee.emp_parent is null;

Select Emp_No from employee where Employee.emp_parent is null

into :Root;

execute procedure seek_leftright(2,:Root) returning_values :Count_Rec;

suspend;

end

5.4.    Một số câu lệnh truy vấn.

  • Liệt kê tất cả các nhân viên không có nhân viên dưới quyền (các nút lá của Cây).

CREATE PROCEDURE GET_ALL_LEAFCHILD

RETURNS (

EMPNO CHAR(15),

EMPNAME VARCHAR(63))

AS

begin

/* Liet ke tat ca cac Node la (cac Node khong co Child Node*/

for

select emp_no, emp_Name from employee

where employee.emp_left = employee.emp_right – 1

into :empNo, :EmpName

do

suspend;

end

  • Liệt kê tất cả cấp trên chung của hai nhân viên

CREATE PROCEDURE GET_COMMON_BOSS (

FIRST_EMP CHAR(15),

SECOND_EMP CHAR(15))

RETURNS (

FIRSTGUY CHAR(15),

SECONDGUY CHAR(15),

BOSSES CHAR(15))

AS

begin

/* Liet ke cac cap tren chung cua hai nhan vien*/

for

SELECT :first_Emp, :second_emp, bossNo

FROM Emp_And_Bosses

WHERE empno = :first_emp

AND bossno IN (SELECT bossNo

FROM Emp_And_Bosses

WHERE empno = :second_emp)

into :firstguy, :secondGuy, :bosses

do

suspend;

end

  • Liệt kê tất cả các nhân viên cấp dưới của một nhân viên

CREATE PROCEDURE GET_INFERIOR (

EMP_ID CHAR(15))

RETURNS (

ID_LIST CHAR(15),

NAME_LIST VARCHAR(63))

AS

declare variable GetRight integer;

declare variable GetLeft integer;

begin

/* Liet ke tat ca cap duoi cua mot nhan vien*/

Select Emp_Left, Emp_Right From employee

where Employee.emp_no = :emp_ID

into :GetLeft, :GetRight;

for

select Emp_No, Emp_Name from Employee

where (Employee.emp_right < :Getright)

and (employee.emp_left > :GetLeft)

into :ID_List, :Name_List

do

suspend;

end

  • Lấy số mức của các các nhân viên (Số mức của các nút).

CREATE PROCEDURE GET_LEVELONTREE

RETURNS (

EMPNO CHAR(15),

EMPNAME VARCHAR(63),

EMPLEVEL INTEGER)

AS

begin

/* Lay cap cua cac node tren mot cay */

for

Select P2.Emp_No, count(P2.Emp_No) from employee P2, employee P1

WHERE P2.emp_left BETWEEN P1.emp_left AND P1.Emp_right

Group by P2.emp_No

into :EmpNo, :Emplevel

do

for

select Emp_Name from employee

where employee.emp_no =:empNo

into :EmpName

do

suspend;

end

  • Liệt kê các nhân viên là cấp dưới trực tiếp của một nhân viên

CREATE PROCEDURE GET_PRIME_INFERIOR (

EMP_ID CHAR(15))

RETURNS (

ID_LIST CHAR(15),

NAME_LIST VARCHAR(63))

AS

begin

/* Liet ke tat ca cap duoi TRUC TIEP cua mot nhan vien

dung de loc khi so luong nhan vien duoi quyen qua lon

*/

for

Select Emp_No, Emp_Name From employee

where employee.emp_parent = :emp_ID

into :ID_List, :Name_List

do

suspend;

end

  • Liệt kê tất cả các cấp trên của một nhân viên

CREATE PROCEDURE GET_SENIOR (

EMP_ID CHAR(15))

RETURNS (

ID_LIST CHAR(15),

NAME_LIST VARCHAR(63),

EMP_SIZE INTEGER)

AS

begin

/* Liet ke tat ca cap tren cua mot nhan vien*/

For

SELECT P1.Emp_No, P1.Emp_Name, (P1.Emp_Right – P1.Emp_Left)

FROM employee P1, Employee P2

WHERE P2.Emp_no = :Emp_ID

AND P2.Emp_Left BETWEEN P1.Emp_Left AND P1.Emp_Right

into :ID_List, :Name_List, :Emp_Size

do

suspend;

end

Tôi không trình bày cách thức Thêm một Cây con vào một Cây đã tồn tại, bởi vì điều đó là không cần thiết, tất nhiên là vẫn thực hiện được điều này (là tập hợp của việc thêm nhiều nút vào một Cây), tôi nghĩ bạn có thể làm được một cách dễ dàng theo nhưng phương pháp xử lý mà chúng ta vừa thảo luận.

6. KẾT LUẬN.

Tôi đã dùng thử cấu trúc Cây kết hợp như chúng ta đã thảo luận ở trên, đồng thời cũng thực hiện một yêu cầu mà chúng ta đã từng nói đến là đem đến sự thoải mái cho người dùng khi họ làm việc với rất nhiều thông tin có trong một CSDL. Tôi đã trình bày dữ liệu theo phương pháp trình bày dạng Cây (TreeView) trong một số ví dụ mô tả, tôi có cảm giác là giao diện đẹp hơn và thấy thú vị hơn khi sử dụng.

Bạn có thể áp dụng thử vào những ví dụ của bạn. Có thể bạn sẽ thú vị hoặc không? Nhưng tôi tin, bạn sẽ có thêm một điều gì đó, vào một buổi tối đẹp trời, sẽ thì thầm với suy nghĩ của bạn, tuy rằng tiếng thì thầm rất khẽ.

7. TÀI LIỆU THAM KHẢO.

  • http://www.dbmsmag.com
  • http://searchdatabase.techtarget.com
  • Cấu trúc dữ liệu và giải thuật (Giáo sư Nguyễn Xuân Lôi – NXB Khoa học-Kỹ thuật).
  • Tìm về bản sắc Văn hóa Việt Nam (GS-TSKH Trần Ngọc Thêm – NXB TP.HCM).
  • Designing Relational Database System (Rebecca Riordan).
  • InterBase 6.0 Documentation (Borland press).
  • Database Systems handbook (Paul J.Fortier).

Sài Gòn 12/2001

Mai Thế Hùng

Cảm tác  – Phong Kiều Dạ Bạc

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s