Thuật toán Tree [Archive] - Diễn Đàn Tin Học

hatred

02-07-2005, 10:21

Tớ có một DB với 2 table như sau:

Table: OBJECT, gồm 2 trường ObjectID, Name
Table: HIERARCHY gồm hai trường ParentObjecID, ChildObjectID chứa quan hệ cha con giữa hai Object

Tớ load DB lên memory dựa trên câu lệnh SQL như sau:

SELECT H.ParentObjectID, O.ObjectID, O.Name
FROM Hierarchy H INNER JOIN Object O
ON (H.ChildObjectID = O.ObjectID)

Bi giờ tớ muốn xây dựng một cây object như sau với một node thuộc interface sau:

interface ITreeNode
{
ITreeNode ParentNode { get; set; }
string Name {get; set; }
ArrayList ChildNodes { get; }
}

(Note: ArrayList chủ yếu chứa đối tượng ITreeNode và không hạn chế số lượng node con của nó)

Nếu là root: ParentNode = null;
Nếu là leaf: ChildNodes = null;

Bạn nào có cách giải hay cho bài toán này chỉ tớ với

Thanks.

bienca101

02-07-2005, 13:45

nguoikicuc

04-07-2005, 09:27

Theo mình thì thừa.Chỉ cần 1 table là đủ

Table Node
ID
ParentID

Mối quan hệ kiểu tree là quan hệ 1:N (self-joined), đâu cần 2 tables và inner join cho phí phạm.

Pseudo code để rebuild tree:

//read from database
objects = select * from table Object

//create lookup hash
foreach (object obj in objects)
{
TreeNode node = new TreeNode(obj);
hashtable.add(obj.ID, node);
}

//rebuild tree
foreach (Object obj in Objects)
{
if (obj.ParentID == null) //no parent => add to root
rootNode.ChildNodes.Add( hashtable[obj.ID] )
else
//has parent, add to parent's children nodes
hashtable[obj.ID].ChildNodes.Add( hashtable[obj.ID] );
}

Have fun

1 hay 2 tables thì cũng còn tùy. Có vài vấn đề cần nêu ra ở đây, vì bạn Hatred không đưa ra requirements rõ rang, nên tôi chỉ đóan thôi:

1/ Nếu đây là “toy project”, nghĩa là làm để chơi mà chẳng dùng cho công ty nào cả, thì 1 table đủ rồi.

2/ Nếu đây là 1 project để dùng cho 1 công ty nào đó thật sự, thì 2 tables có nhiều lợi điểm hơn. Sau đây là những lợi điểm của 2 tables:

Lợi điểm 1: Phân chia rõ ràng, 1 table dùng cho data (là “objects” của bạn), table kia chứa relationships của objects trong table kia. Trong tương lai, nếu bạn cần tạo ra 1 lọai relationship khác hẳn với current relationship, mà vẫn muốn giữ current relationship (2 quan hệ song song), thì chỉ cần tạo thêm 1 table thứ 3 để chứa relationship mới mà không cần break hay đổi table thứ 2 (chứa current relationship). Nếu bạn cần tạo ra 1 relationship thứ 3 mà vẫn muốn giữ 2 relationships kia? Tạo ra 1 table thứ 4, thế là xong.

Lợi điểm 2: Bạn không muốn tạo ra quan hệ mới, mà chỉ muốn “refresh” lại hết tất cả những relationship trong database? Chỉ cần “refresh” relationship table mà không cần thay dổi table chứa data (objects)

Lợi điểm 3: Không có gì bảo đảm là trong tương lai object của bạn chỉ có ID và Name, mà sẽ có thêm rất nhiều attributes trong dó. Nếu cả object + object attributes + relationship đều nằm trong 1 table thì sao? Chắc chắn bạn sẽ tốn rất nhiều thời gian để query cho 1 tree.

3/ Nếu giải quyết như bienca, thì tòan database chỉ có 1 tree mà thôi. Trong thực tế hầu như không có trừong hợp như vậy. Trong database của bạn thông thường sẽ có nhiều root nodes, mỗi root node là gốc của 1 tree.

Nếu xếp của bạn buồn buồn bảo rằng requirements đổi, bây giờ không chứa trees mà chứa "forests". 1 forest là 1 set của trees mà có quan hệ dính líu tới nhau, cho nên 1 forests có nhiều root nodes trong dó có liên hệ lẫn nhau.

Thông thường bạn sẽ phải có những queries như sau:

Query 1: tìm 1 tree mà root node có tên là “ROOTA”

Query 2: tìm 1 tree mà root node có tên có chữ “OT” trong đó. Những root node có tên là “ROOTA”, “AOTIM”, “BOT” đều thỏa mãn query này. Dĩ nhiên là bạn có thể đặt thêm điều kiện “bắt đầu bằng” hoặc “kết thúc bằng”

Query 3: tìm 1 tree mà root node có ID = ***

Query 4: tìm root node mà object name = “OBJ01” nằm trong tree của root node đó, dĩ nhiên từ đó bạn có thể tìm duoc tòan bộ tree đó

Có thể có vài queries khác, tùy theo requirements của project, chẳng hạn, so sánh 2 trees theo 1 số điều kiện nào đó, hoặc đếm xem có bao nhiêu trees “ngắn” hơn hay “dài” hơn tree hiện có, vân vân …

Với khối lượng data lớn, để tránh nhiều “round trips” đi lại giữa program của bạn và database server trong khi đi tìm và xây dựng lại 1 tree, bạn nên tạo ra store procedure để làm chuyện này, mọi queries để tạo tree đều run tren server thì không có vấn đề gì về performance (trừ khi bạn viet store procedure quá … tệ)

Chúc may mắn.

bienca101

04-07-2005, 12:50

Ừ, cám ơn nguoikicuc đã giải thích thêm. Bản thân mình chưa đưa "graph" thật bự vào database bao giờ cả.

Về chuyện

3/ Nếu giải quyết như bienca, thì tòan database chỉ có 1 tree mà thôi. Trong thực tế hầu như không có trừong hợp như vậy. Trong database của bạn thông thường sẽ có nhiều root nodes, mỗi root node là gốc của 1 t

Là do mình đoán hatred dùng TreeView trong winform nên mới đưa ra code trên. Theo định nghĩa thì 1 tree bao giờ cũng có 1 root duy nhất, cho dù root đó là implicit hay explicit. Còn graphs thì mới có rẽ nhánh (multiple roots) thôi.

Tiện thể nếu bạn có thể góp ý thêm cho mình cách thiết kế database cho 1 network graph thì tốt biết mấy. Lấy ví dụ là có n thành phố, từ thành phố này có thể đi đến m thành phố nào đó. Đây là dạng toán graph kinh điển (ví dụ: tìm đường đi ngắn nhất trong bản đồ). Mình chỉ muốn hỏi riêng về phần lưu relationships giữa các node như thế nào. Mình muốn ứng dụng cho multi-dimension data array. Tuy có tìm hiểu một số thuật toán nhưng chưa tìm được cái nào ưng ý cả. Hy vọng khi bạn rảnh rỗi có thể chỉ thêm cho mình

nguoikicuc

05-07-2005, 09:16

Là do mình đoán hatred dùng TreeView trong winform nên mới đưa ra code trên. Theo định nghĩa thì 1 tree bao giờ cũng có 1 root duy nhất, cho dù root đó là implicit hay explicit. Còn graphs thì mới có rẽ nhánh (multiple roots) thôi.
Dù là tree nhưng thông thường sẽ có nhiều trees trong database chứ không phải chỉ có 1 tree trong database

Tiện thể nếu bạn có thể góp ý thêm cho mình cách thiết kế database cho 1 network graph thì tốt biết mấy. Lấy ví dụ là có n thành phố, từ thành phố này có thể đi đến m thành phố nào đó. Đây là dạng toán graph kinh điển (ví dụ: tìm đường đi ngắn nhất trong bản đồ). Mình chỉ muốn hỏi riêng về phần lưu relationships giữa các node như thế nào. Mình muốn ứng dụng cho multi-dimension data array. Tuy có tìm hiểu một số thuật toán nhưng chưa tìm được cái nào ưng ý cả. Hy vọng khi bạn rảnh rỗi có thể chỉ thêm cho mình
Graph có 2 dạng, directed graphs & undirected graphs.

Trong trường hợp directed graph, ít nhất bạn cần có 2 tables, 1 chứa data, 1 chứa relationships, không thể nhập chung được vì đây là n-n relationship. Table chứa relationship có thể nói không phải ở dạng parent-child nữa, mà là dạng from-to (thật ra cũng gần giống như vậy, nhưng nếu gọi là parent-child relationship thì sẽ có lúc bạn có 1 node là parent của 1 child node, child node là parent của another child node, mà in turn child node thư" 2 này lại là parent của cái node đầu tiên; hoặc là tệ hại hơn, parent có 1 child mà child đó lại là parent của node ... parent, umm... hình như có hơi ... loạn luân :)) Giữa 2 nodes A và B, nếu ta có 1 relationship from A to B, và 1 relationship khác from B to A, trong table chứa relationship bạn phải có 2 entries khác nhau để chứa 2 relationship này giữa A và B.

Trường hợp undirected graphs cũng gần giống như directed graphs, nhưng khi nói A có liên hệ tới B thì cũng tương đương với nói B có liên hệ tới A, có nghĩa là không phải "from-to" relationship nữa, mà là "has relationship with", trong ví dụ A & B thì là "A has relationship with B" mà cũng là "B has relationship with A", 2 câu này tương đương nhau. Với sự liên hệ như vậy, để chứa relationship giữa A và B trong table relationship, bạn có thể làm 2 cách khác nhau:

Cách thứ 1: cho mỗi 1 relationship (chẳng hạn relationship giữa A và B), bạn có 2 entries, 1 từ A - B, 2 từ B - A, tức là giống như trong trường hợp của directed graph, nhưng tự động tạo 2 entries cho mỗi 1 relationship. Cách này bạn phải bảo đảm được là cho mỗi 1 relationship phải có 2 entries trong table, còn không nếu chỉ có 1 (A-B hay B-A only) thì là error. Cũng vậy, khi bạn delete 1 relationship giữa A và B, bạn phải bảo đảm được 1 điều là cả 2 entries thể hiện relationship đó phải bị deleted. Nhưng ngược lại khi chứa relationship kiểu này, queries của bạn sẽ đơn giản hơn

Cách thư" 2: cho mỗi 1 relationship, bạn chỉ có 1 entry trong table relationship. Trong ví dụ A và B, nếu bạn dang work trên object A, muốn thể hiện sự liên hệ giữa A và B, bạn insert into table relationship mối quan hệ A-B. Còn nếu như bạn đang work on object B và muốn tồn trữ sự liên hệ giữa B và A thì insert mối quan hệ B-A. Chú ý rằng 2 trường hợp trên tương đương nhau, và cùng nói lên 1 điều là A có liên hệ tới B, hay là B có liên hệ tới A, như nhau cả. Làm như cách này thì bạn không cần phải bảo đảm 1 relationship có 2 entries giống như cách 1 và không sợ bị thiếu sót, nhưng ngược lại khi queries sẽ phải vất vả hơn. Nói ví dụ, bạn đang có object B, bạn muốn biết những relationships của B trong database, mà table chứa relationship lại chỉ chứa A-B (không phải B-A), bạn phải query cho cả 2 columns của table này xem có entry nào = B hay không, chứ query 1st column không thì không đủ.

Điều này đưa ra câu hỏi là, chọn cách nào? Thời buổi bây giờ thì storage của database không còn là vấn đề nữa, nên disk space không còn ảnh hưởng tới sự lựa chọn 1 entry hay 2 entries cho mỗi relationship nữa. Vậy chỉ còn chọn lư.a dựa vào sự sử dụng của system thôi.

Nếu trong system này, relationship thay dổi liên tục với frequency cao, mà không có statistic report nhiều trên sự liên hệ giữa những object với nhau, thì cách thứ 2 có lẽ dễ dàng hơn. Relationship thay đổi nhiều thì sẽ có nhiều insertions & deletions, dĩ nhiên khi tạo hay xóa 1 entry cho mỗi relationship sẽ dễ dàng hơn là tạo hay xóa 2 entries cho mỗi relationship. Mà system lại không cần statistic reports nhiều thì không cần query nhiêu.

Nếu ngược lại relationships giữa object không thay đổi nhiều sau khi đã được tạo nên, mà lại có nhiều nhu cầu tạo report (statistic chẳng hạn), bạn có thể giữ 2 entries cho mỗi relationship thì querying sẽ dễ dàng hơn nhiều.

bienca101

05-07-2005, 13:42

Về chuyện tree thì mình có 3 lý do để bảo vệ cách của mình:
- Vẫn cho phép multiple tree: đơn giản là root node không cần phải là null mà sẽ có 1 ID riêng, có bao nhiêu tree thì sẽ có bấy nhiêu rootnode, thế thôi. Như vậy thuật toán trên của mình vẫn hợp lệ, chỉ cần thay đổi dòng if (parent = null) thành if (parent = root) (nếu không cứ giữ nguyên thế, multiple tree chẳng qua chỉ là multiple-branch thôi)

- Đành ràng database engine mạnh, nhưng multiple tree mà lưu vô chỉ 2 tables là không nên. Mỗi một tree nên tách riêng ra. Ví dụ: Customer, Employee, Vendors đều là tree được, đều có attributes na ná nhau nhưng vẫn nên tách riêng chứ không nên gộp chung thành 1 (hoặc 2 tables như cách của bạn) duy nhất. Lý do: scalability. Coding thì nên gộp chung, nhưng database thì không.

- Database chỉ nên để dành riêng cho việc persistent. Việc xử lý relationship và rebuild tree nên dành riêng cho phần client code. Do đó, khi design daatabase cần phải quan tâm ngay cả đến chuyện hạn chế dùng joins.

Tuy nhiên, mình hoàn toàn đồng ý với bạn về việc khi có nhiều kiểu relationship thì nên để relationship trong table riêng, còn attributes trong table riêng. Điều này rất chính xác.

Túm lại, về chuyện tree thì mình không cãi nữa. Chuyện 1 hay 2 table đều có cái hay trong tùy trường hợp.

Về chuyện graph, theo mình hiểu thì giải pháp của bạn chính là edge detection. Đại khái là nodes nằm trong 1 table, còn relationship sẽ nằm trong 1 table khác:

table Edge (relationship)
ID NodeA
ID NodeB
other attributes

Phương pháp này áp dụng cho bài toán tìm đường đi thì được, nhưng áp dụng cho multi-dimension data array thì rất phiền bởi 2 vấn đề sau:
- nhiều dữ liệu để save quá. Nội 1 relationship đã cần đến ít nhất: 2 IDs [+ attributes].
- query chậm chạm, thậm chí có khi chưa biết query kiểu nào.

Vấn đề multi-dimension data array mình đưa ra là 1 dạng bài toán network graph nhưng phức tạp hơn tìm đường đi. Lấy ví dụ như thay vì lưu customer, order, product dưới dạng tables trong relational database, mình sẽ lưu hết dưới dạng objects. Thế thì làm sao để query trở ra 1 object thỏa điều kiện A, B, C nào đó? Trong báo cáo quản trị người ta có khái niệm Pivot Table, cho phép slice-n-dice data. Đây là chức năng rất hay. Nhưng Pivot Table chỉ là 1 trường hợp rất đặc biệt của multi-dimension data (pivot table chỉ cho phép 3 dimension, còn relational table chỉ cho phép 2 dimension).

Bài toán multi-dimension data thú vị lắm, không chỉ cho báo cáo tài chính mà còn nhiều ứng dụng khác. Ví dụ như bộ não con người ấy, mỗi một neuron đều là 1 node trong hàng tỉ tỉ node. Khi cần lưu cái gì thì các node sẽ tự tạo link nối kết nhau lại. Đơn giản chỉ có thế. Ấy thế mà khi muốn query 1 object nào cũng được. Thậm chí khi không có đủ dữ liệu thì có thể tự gầy dựng lại dữ liệu (ví dụ: nhớ tên 1 người bạn cũ qua gương mặt).

Mình đi kiếm thuật toán cho cái này cũng 1 năm rưỡi hơn mà vẫn còn đau đầu đây. Thấy bạn trả lời rắn rỏi về tree nên mừng quá, "vồ" ngay lấy để hỏi thêm về multi-dimension data ấy mà :D

hatred

05-07-2005, 17:29

Hi anh Hai và nguoikicuc!

Các bài viết của anh đúng là kha có ích, em cũng chưa liên tưởng đến việc lưu một graph xuống DB như thế nào?

Thật ra bài toán của em nhỏ, không có gì to tát lắm, DB em nghĩ là phù hợp với bài toán của em, vì mình thao tác trên Tree rất nhiều (Tree ở đây trên WEB chứ không phải trên WIN), và lưu History của nó:

Ví dụ việc move một thằng child từ một Parent đến một Parent khác, mình phải lưu được data: a` trong thời điểm này mày là con của ai ==> không thể dùng một bảng như anh Hải được.

(Không Delete Data mình chỉ dùng một trường Deleted trong Table để check xem một Object đã bị Delete hay chưa?)

Còn việc nó có một root hay nhiều root em nghĩ không quan trọng vì mình có thể tạo một root ảo cho tất cả các root nếu trong trường hợp nhiều root.

Có thể có nhiều cách lưu một Tree trong memory, cách mà em hay làm nhất là là dùng một Collection gọi là ObjectCollection chẳng hạn (ArrayList hay Hashtable cũng được miễn là tiện) và một TreeNode phải lưu các ChildId và ParentId của nó.

Nhưng bài toán em muốn ở đây là xây dựng một cây Object thật sự (dùng Pointer để link các node lại với nhau.)

Thanks anh đã trả lời.

nguoikicuc

07-07-2005, 02:09

Tôi thấy có nhiều điều không được rõ ràng cho lắm:

Về chuyện tree thì mình có 3 lý do để bảo vệ cách của mình:
- Vẫn cho phép multiple tree: đơn giản là root node không cần phải là null mà sẽ có 1 ID riêng, có bao nhiêu tree thì sẽ có bấy nhiêu rootnode, thế thôi. Như vậy thuật toán trên của mình vẫn hợp lệ, chỉ cần thay đổi dòng if (parent = null) thành if (parent = root) (nếu không cứ giữ nguyên thế, multiple tree chẳng qua chỉ là multiple-branch thôi)

- Đành ràng database engine mạnh, nhưng multiple tree mà lưu vô chỉ 2 tables là không nên. Mỗi một tree nên tách riêng ra. Ví dụ: Customer, Employee, Vendors đều là tree được, đều có attributes na ná nhau nhưng vẫn nên tách riêng chứ không nên gộp chung thành 1 (hoặc 2 tables như cách của bạn) duy nhất. Lý do: scalability. Coding thì nên gộp chung, nhưng database thì không.

- Database chỉ nên để dành riêng cho việc persistent. Việc xử lý relationship và rebuild tree nên dành riêng cho phần client code. Do đó, khi design daatabase cần phải quan tâm ngay cả đến chuyện hạn chế dùng joins.

Tuy nhiên, mình hoàn toàn đồng ý với bạn về việc khi có nhiều kiểu relationship thì nên để relationship trong table riêng, còn attributes trong table riêng. Điều này rất chính xác.

Túm lại, về chuyện tree thì mình không cãi nữa. Chuyện 1 hay 2 table đều có cái hay trong tùy trường hợp.
Nếu coi mỗI tree là 1 table như bienca nói, vậy cách đọc “select * from table ___” và cách kiểm tra “if (parent = null)” đổI thành “if (parent = root)” (must be “==” here) chẳng ăn nhập gì tới nhau cả.

“nhưng multiple tree mà lưu vô chỉ 2 tables”: ít nhất 2 tables trở lên, không có nhất định là phảI 2 tables

“Customer, Employee, Vendors đều là tree được”: Employees data còn có thể nói là “1 tree”, nếu application chỉ cho 1 company mà không phảI là nhiều companies. Nhưng Customers & Vendors thì không biết “tree” thế nào?

“Database chỉ nên để dành riêng cho việc persistent. Việc xử lý relationship và rebuild tree nên dành riêng cho phần client code. Do đó, khi design daatabase cần phải quan tâm ngay cả đến chuyện hạn chế dùng joins.”: cái ý tưởng này cần phảI coi lạI, nếu design relational database mà sợ joins thì tòan bộ database chỉ tóm gọn lạI trong 2-3 tables sao? Bienca có design large database với large volumn of data bao giò chưa?

Để tôi đưa ra 2 ví dụ nhé. Ví dụ 1: 1 application quản lý tòan bộ dân số trong quận 5 tpHCM. Cho là có khỏang 500 ngàn người trong quận 5 đi, vậy có khỏang 100 ngàn hộ nhân khẩu trong quận này (mỗI hộ trung bình 5 người). Trong application ta có thể coi 1 hộ nhân khẩu là 1 tree, mà chủ hộ là root node, mỗi 1 ngườI trong hộ là 1 child node. Vậy trong database có khỏang 100 ngàn trees. Nếu đọc data từ database theo kiểu “select * from table ___” thì chẳng lẽ đọc hết 100 ngàn trees và 500 ngàn records vào trong memory sao? Đó là mới có 1 quận, bây giò nếu là application để quản lý tòan bộ dân số của thanh phố thì sao?

Ví dụ 2: bienca biet human genes chứ hả. Human body có khỏang trên 30-40 ngàn known genes, chưa kể những genes mà ta không biết. Thậm chí có lab còn nói là human body có trên 100 ngàn genes, nhưng thôi, nói 30-40 trở lên là đủ rồI. Một gene có nhiều transcripts (mRNA) và có nhiều proteins. Database của 1 công ty thử nghiệm về genes sẽ phảI chứa được số lượng data này. MỗI 1 gene được coi là 1 data tree mà gene là root node, transcripts và proteins là chid nodes, dĩ nhiên mỗI lọai genes, transcripts & proteins nên nằm trong 1 table riêng rẽ (đây là truong hợp mà tree tạo ra từ nhiều tables khác nhau). Vậy nộI trong 1 table chứa gene thôi là đã có 30-40 ngàn trees trở lên rồi. Nếu đọc 1 lượt hết bao nhiêu đó vô trong memory (“select * from table ___”) thì sao? Đó là chưa kể những cong ty nghiên cứu về genes không phảI chỉ có nghiên cứu đơn thuần về human genes, mà còn genes của rat, mouse, fish, cat, dog, vân vân. Tổng số lượng genes sẽ lên đến hàng trăm ngàn.

Ở đây tôi hòan toàn không có ý công kích hay đã phá ai cả, tôi chỉ muốn cho những ngườI đọc đừng có suy nghĩ quá đơn giản về vấn đề này.

Về chuyện graph, theo mình hiểu thì giải pháp của bạn chính là edge detection. Đại khái là nodes nằm trong 1 table, còn relationship sẽ nằm trong 1 table khác:
Code:

table Edge (relationship)
ID NodeA
ID NodeB
other attributes

Phương pháp này áp dụng cho bài toán tìm đường đi thì được, nhưng áp dụng cho multi-dimension data array thì rất phiền bởi 2 vấn đề sau:
- nhiều dữ liệu để save quá. Nội 1 relationship đã cần đến ít nhất: 2 IDs [+ attributes].
- query chậm chạm, thậm chí có khi chưa biết query kiểu nào.

Vấn đề multi-dimension data array mình đưa ra là 1 dạng bài toán network graph nhưng phức tạp hơn tìm đường đi. Lấy ví dụ như thay vì lưu customer, order, product dưới dạng tables trong relational database, mình sẽ lưu hết dưới dạng objects. Thế thì làm sao để query trở ra 1 object thỏa điều kiện A, B, C nào đó? Trong báo cáo quản trị người ta có khái niệm Pivot Table, cho phép slice-n-dice data. Đây là chức năng rất hay. Nhưng Pivot Table chỉ là 1 trường hợp rất đặc biệt của multi-dimension data (pivot table chỉ cho phép 3 dimension, còn relational table chỉ cho phép 2 dimension).

Bài toán multi-dimension data thú vị lắm, không chỉ cho báo cáo tài chính mà còn nhiều ứng dụng khác. Ví dụ như bộ não con người ấy, mỗi một neuron đều là 1 node trong hàng tỉ tỉ node. Khi cần lưu cái gì thì các node sẽ tự tạo link nối kết nhau lại. Đơn giản chỉ có thế. Ấy thế mà khi muốn query 1 object nào cũng được. Thậm chí khi không có đủ dữ liệu thì có thể tự gầy dựng lại dữ liệu (ví dụ: nhớ tên 1 người bạn cũ qua gương mặt).

”multi-dimension data array”: multi dimension database hay multi dimension data hay multi dimension array? MỗI thứ đều có ý nghĩa khác nhau đó. Theo tôi đóan thì bienca muốn nói về multi dimensional database, thế thì mình nói về vấn đề này nhé.

“Lấy ví dụ như thay vì lưu customer, order, product dưới dạng tables trong relational database, mình sẽ lưu hết dưới dạng objects”: Khoan đã. Bienca hiểu gì về relational database vs. multi dimensional dabase và hiểu sao về cách multi dimensional database chứa data? Thêm nữa, multi dimensional database ai nói phải là object oriented database??? Dân software có 1 bệnh cần phảI tránh là khi mình thích technology nào rồi thì nhìn cái gì cũng thành ra cái đó, cái gì cũng phảI làm theo cái đó. Làm như vậy thì hại nhiều hơn lợi. Object oriented databse có lợi điểm của nó, nhưng cũng có nhược điểm và chính nhược điểm của nó làm cho nó không được thông dụng bằng relational database. Nhưng thôi, muốn nói về relational vs. object oriented dabase thì nên nói ở 1 thread khác, out of scope here.

1 graph đơn thuần nếu chỉ có đỉnh và cạnh (relationship) thì chỉ cần relational model là đủ rồi. Còn nếu muốn nói tới dùng multi dimensional database để chứa data, thì data phảI có nhiều dimensions mà mình muốn nghiên cứu, chẳng hạn như customer, order & product mà bc có nói ở trên. Xin phân biệt rõ ràng 1 chút, graph chưa chắc là multi dimensional data, và để dùng multi dimensional database, data không nhất thiết phảI trong dạng “graph”. Điều thứ 2 xin nói rõ 1 chút, cho dù là data là multi dimensional data đi nữa cũng chưa chắc nên dùng multi dimensional database, nếu như độ desity của data quá thưa thớt mà làm như vậy thì chỉ tốn chỗ mà lại không hiệu quả.

Để nói thêm về multi dimensional database. Thông thường khi noi về multi dimensional database, ngườI ta noi về OLAP model, nghĩa là On-Line Analytical Processing. Đa số những database hiên giờ là dạng OLTP (Online Transactional Processing), dùng relational model để chứa dữ liệu và transactions.

OLAP/multi dimension database được dùng để build những datawarehouse, dùng để nghiên cứu sâu về statistic, trends, predictions dựa trên data được collect qua nhiều năm nhiều tháng. Nói ví dụ, analysts nghiên cứu trên datawarehouse của 1 công ty buôn bán hàng lớn, có nhiều tiệm nằm ở nhiều thành phố khác nhau (hàng trăm tiệm). Dựa vào data đã được collect qua nhiều năm trong nhiều tiệm, họ có thể đóan được là khách hàng ở vùng nào thích mặt hàng nào, vào mùa đông thì hàng nào bán chạy, về mùa hè thì hàng nào được chuộng, hàng nào đem về lợi nhuận cao, hàng nào ế dài dài, vân vân. Dựa vào kết quả này, cong ty đó có thể thay đổI mặt hàng tùy theo mùa (seasons), tùy theo vùng (geographical area) để nâng mức lợI nhuận lên đến độ tốI đa mà tránh được hàng bị ốI đọng trong tiệm. Vì data của OLAP model là historical data, data không thay đổi nhiều (static).

Còn dạng OLTP, data thay đổI liên tục, cũng lấy ví dụ về công ty buôn bán hàng nói trên, database để collect data cho từng tiệm chính là dạng OLTP. Mỗi ngày mỗi giờ đều có người tới mua hàng, khi có ngườI mua hàng và trả tiền thì có 1 transaction entered into database (1 order). Order này gồm có dữ liệu về khách hàng (customer), về những món hàng mà ngườI khách này mua (products), tổng số tiền người này trả (sale), và dĩ nhiên mỗI món hàng có attributes riêng của nó. Khi có người tới trả hàng vì hàng hư chẳng hạn, sẽ có 1 transaction để return products entered into database.

Đối với cái datawarehouse của công ty mà nói, thì OLTP database của từng tiệm là “external databases”. MỗI tuần hay mỗI tháng, data từ từng tiệm sẽ được đưa về tổng công ty, lọc lại cho “cleaned” và select chiếu theo mục tiêu nghiên cứu của ngườI dùng warehouse, những “cleaned & filtered” data này được đưa vào những databases gọi là datamart.

Data từ những datamarts được “built” lại rồI bỏ vô trong datawarehouse, mà datawarehouse chính là OLAP database model (multi dimensional database). Mỗi một datamart có thể chứa data cho 1 dimension của data trong datawarehouse. RồI từ data trong datawarehouse, sẽ có những interface applications cho ngườI nghiên cứu chọn lựa và nhìn vào data dưới 1 góc cạnh nào đó mà họ muốn, để nghiên cứu và chuẩn đóan.

Trước khi data đi tới được datawarehouse thì phảI qua nhiều bước, và đa số đều được lưu trữ trong traditional databases (từ OLTP databases đến datamarts). Khi đến được datawarehouse thì data không còn đơn thuần là data lúc đầu nữa. Nói ví dụ, trong datawarehouse của công ty bán hàng nói trên không còn chứa từng order (1 lần mua hàng) của khách hàng, cũng không còn chứa tên khách hàng hay chứa từng món sản phẩm mà 1 khách hàng mua nữa. Data mà datawarehouse đó chứa sẽ đại khái là trong từng tháng, ở địa phương đó bán được X số lượng sản phẩm A, Y số lượng sản phẩm B, đọng lại trong kho Z số lượng sản phẩm C, tổng số bán của tiệm M, tổng số lời của tiệm N, vân vân. Đây gọi là “aggregate data”, không còn là individual data nữa.

Đào sâu hơn tí nữa, OLAP dược thực hiện physically bằng nhiều cách khác nhau, MOLAP, ROLAP và HOLAP.

MOLAP model là truly multidimensional database, cái này còn tùy theo cách implement của từng vendor, chẳng ai giống ai cả. Lợi điểm của MOLAP là nhanh, truly multi dimensional model. Khuyết điểm là dễ dẫn đến tình trạng lack of density, nghĩa là trong data cub có nhiều chỗ trống (empty value ở most of the cells), vậy thì phí phạm mà không hiệu quả.

ROLAP là dạng dùng relational database để model multi dimensional database. Lợi điểm của model này là dễ implement, nhược điểm là chậm, không phảI truly multi dimension

HOLAP là dạng hybrid, có nghĩa là tổng hợp của 2 dạng trên. Core data (data chính) sẽ được chứa trong dạng multi dimensional, nhưng details data (data dùng để “grill down”) thì chứa dướI dạng relational. Dùng dạng HOLAP này thì giảm bớt cost của implementation, lạI đáp ứng được tốc độ nhanh của đa số queries. Nhưng khi “grill down” xuống detail data thì sẽ bị chậm lạI vì đụng vào relational model.

Xin nhắc lại rằng, nếu bạn dùng OLAP của 2 vendors khác nhau thì thông thường cách dùng sẽ khác nhau, chẳng ai giống ai.
Hy vọng nói như vậy giảI thích được rõ ràng multi dimensional database model và mục đích của nó.

Mình đi kiếm thuật toán cho cái này cũng 1 năm rưỡi hơn mà vẫn còn đau đầu đây. Không biet bienca tìm “thuật tóan” là thuật tóan thế nào??? Thuật tóan để làm gì ??? Nếu muốn dùng 1 multi dimensional database của 1 vendor nào đó, thì đọc hướng dẫn của vendor đó mà dùng, data bỏ vô datawarehouse dâu phảI là nguyên dạng nữa đâu? Và tại sao phảI tốn 1 năm rưỡI???

Thấy bạn trả lời rắn rỏi về tree nên mừng quá, "vồ" ngay lấy để hỏi thêm về multi-dimension data ấy mà

bienca101

07-07-2005, 05:07

Ui nguoikycuc ui, mình với nguoikycuc coi bộ chưa ngã ngũ về chuyện này mất rồi :)

1/ Tree:
Vâng, mình vẫn biết, vẫn dùng, vẫn thiết kế tree theo kiểu 2 table như thường. Mình chỉ đưa ra 1 cách lưu tree xuống relational database sử dụng 1 table. Cách dùng 1 table có ưu điểm thế này: đơn giản, gọn nhẹ, object-oriented, và không phải lo lắng về chuyện manage relationship.
Khi có dữ liệu nhiều thì dù cách của bạn hay cách của mình đều không nên đọc hết dữ liệu. Đời thuở nhà ai lại đọc hết 500 ngàn tuple cùng một lúc bao giờ? Với khả năng của bạn, bạn thừa biết rằng 2 ví dụ của bạn đưa ra nghe thì to tát nhưng phương pháp của mình vẫn sử dụng được tốt.
Bạn đi sâu nhiều quá vào tiểu tiết bạn ạ. Mình chỉ viết pseudo-code cho một thread < 100 từ, có phải viết research paper đâu? Toàn là mình chịu "đỡ đạn", chưa hề "phản pháo" tí nào cả.
Nếu bạn chưa ưng bụng thì cứ viết 1 cái project be bé của bạn, còn mình sẽ viết theo của mình, sau đó cả hai sẽ benchmark xem cái nào nhanh và hiệu quả hơn.

Mà bạn cũng đừng hỏi mãi mình đã design những project nào bự hay chưa nữa nhé. Mình đến với programming bởi vì đây chính là một môn nghiên cứu khoa học rất hay. Mình đến với diễn đàn này bởi vì có nhiều người giỏi. Mình đến đây không phải để khoe kiến thức hay đẳng cấp gì cả. Hơn nữa, theo mình biết thì Bill Gates viết DOS khi "vắt mũi chưa sạch", mới tò te tí te học chưa xong đại học. Kể về database bự thì Google do 2 sinh viên viết. Kể về thành công thì Bank of America do một anh công chức quèn sáng lập. Mình còn xa lắm những bậc kỳ tài ấy, nhưng mình sẵn lòng học hỏi kinh nghiệm của những người giỏi. :)

2/ Multi-dimension:
Vâng, cám ơn bạn đã chỉ bảo mình thêm. Nhưng mà... mình cũng may mắn đã có học qua các khái niệm OLTP, OLAP, DataWarehouse, DataMart.

Về chuyện bạn đề nghị dùng công cụ có sẵn thì mình muốn thưa với bạn rằng làm thế thì còn gì là nghiên cứu, học hỏi nữa? Thế nếu không có 100.000 đô để mua thì developers phải chấp nhận viết VB6 với Access mãi à? Vâng, họ có thể có những công cụ hay vào lúc này, nhưng mình chưa thấy có công cụ hay technology nào giải quyết được vấn đề multi-dimension data array cả. (vâng, đã biết multi-dimension data, đã biết multi-dimension array, mình vẫn dùng đúng cụm từ này bởi vì từng phrase riêng rẽ mô tả một khái niệm riêng, chưa đủ để diễn đạt)

Mình hỏi bạn nhé, thế hiện tại có database technology nào cho phép hoạt động theo kiểu hệ thần kinh con người nào? Không, mình chả nói gì đến neuron network-based algorithms (ví dụ như nhận dạng khuôn mặt, nhận dạng stock patterns) cả. Ý của mình là cơ chế persist và query dữ liệu của con người rất hiệu quả, rất đặc biệt. Nếu so sánh với OLTP database thì có vẻ chậm hơn, nhưng nếu so sánh với tất cả các OLAP technology hiện có thì máy tính còn thua xa lắc bạn ạ. Nhìn vào một báo cáo tài chính, con người có thể phân tích thông tin ngay trong tích tắc, tính toán thì lâu nhưng phân tích lại nhanh. Lấy ví dụ khác, khi nhìn vào 1 khuôn mặt, ta có thể lục ra mọi thông tin mà ta nhớ về người này rất nhanh, thậm chí có thể tự tiên đoán từ hình ảnh lưu trữ hai chục năm về trước, khi người đối diện còn trẻ, so sánh với người mình đang nhìn hai chục năm sau, đã già. Con người có khả năng làm thế rất hiệu quả, còn OLAP chắc phải đợi vài chục năm mới xử lý nổi vì số lượng dữ liệu quá lớn. (mỗi ngày một người nhận nhiều thông tin đến nỗi bất kỳ datawarehouse hiện có nào cũng phải bó tay x 20 năm)

Đấy chính là thứ mình đang đi tìm. Mình hypothesize đây là dạng toán network graph bởi vì tổ chức của neuron rất giống một network, đơn giản là vậy.

bete

07-07-2005, 09:06

tui xin ké 1 chút: hổng rõ ”multi-dimension data array” theo ý bienca là gì. Và cũng hổng rành về OLAP,.....

Nhưng tui thấy có 1 số cấu trúc dữ liệu như KDB tree, R tree, R* tree, R+ tree, ... dùng cho 2 loại: điểm (không có kích thước) trong không gian N chiều; và vật (có kích thước) trong không gian N chiều

Nhưng có lẽ không thể mượn Oracle để làm mấy cái cây này thì phải (vì Oracle xài B+ tree) còn mấy cái cây này thì lại khác (INSERT/DELETE/SEARCH) chút xíu :(

-thân

nguoikicuc

07-07-2005, 10:14

À, hân hạnh được làm quen với 1 Bill Gates tương lai :) Giỡn thôi. Tôi thì rất hoan nghênh những bạn trẻ tìm tòi học hỏi và khám phá những điều mà người ta chưa bao giờ nghĩ ra, khoa học có tiến bộ hay không là nhờ những tay đi đầu này.

Trong quá trình làm việc, tôi đã gặp qua đủ mọi lọai người. Những tay “geek” thứ thiệt tối ngày chỉ biết chúi mũi vô nghiên cứu. Dạng người này rất chịu khó học hỏi, chia xẻ kiến thức, không bao giờ tỏ vẻ ta đây biết những điều mà họ chẳng có tí tẹo kiến thức nào. Nếu họ không biết điều gì, họ sẽ sẵn sang nói “tôi không rõ” và lắng nghe học hỏi. 1 dạng khác là những tay xu thời, nói giỏi. Những tay này biết lợi dụng thời điểm thuận lợi để đẩy mình lên, biết nói chuyện để mờ măt’ thiên hạ, biết nói lòng vòng để khỏa lấp khuyết điểm của mình. Dạng người này khó chấp nhận là “tôi không biết rõ” 1 vấn đề gì, cho dù không biết rõ cũng có cách nói để thiên hạ nghĩ mình siêu việt như thường. Thật là xấu số cho những ai phải làm việc dưới quyền những người trong dạng này … thôi không dám tả:D

Nói lòng vòng cho vui vậy thôi. Chẳng dám ám chỉ ai :) Bây giờ được biết bienca có bỏ công sức ra cả năm rưỡi trời nghiên cứu về “multi dimension data array” database có khả năng họat động như não người, mặc dù biết là bước khởi đầu, vậy bienca có vui lòng chia sẽ quá trình nghiên cứu của mình như thế nào với các bạn trong diễn đàn không? Dĩ nhiên không dám đòi hỏi details vì biết đâu lại phạm vào secret của … quá trình nghiên cứu, nhưng ít nhất cũng có thể nói đại cương đã tìm được gì, work thế nào, cấu trúc ra sao, cho dù là chưa work, cho mọi người cùng mở mắt.

Nãy giờ đi trên trời, bây giò quay lại trái đất. bienca càng nói tôi càng thấy ý tưởng của you càng không được rõ ràng, có khi còn chõi nhau.

Không cần phải đi sâu, nhưng cái pseudo code của bienca không thực tế. Ngay cả làm cho project trong trường cái pseudo code đó cũng không tốt, đừng nói áp dụng ra ngòai. Đưa cái đó ra cho những người còn đang tạp tễnh ghế nhà trường lấy đó mà noi theo thì … xin lỗi.

Ở trên, bienca nói “Cách dùng 1 table có ưu điểm thế này: đơn giản, gọn nhẹ, object-oriented, và không phải lo lắng về chuyện manage relationship”, hmmm…, làm kiểu gì thì làm, relationship vẫn phải manage, cho dù là database chỉ có 10 nodes trong đó.

Điều nữa, bienca học qua multi dimensional database, OLAP, datawarehouse & datamart rồi thì mừng cho you. Bienca cứ nói dùng multidimensional database để chứa network graph data, chứa dữ liệu để có thể nhận dạng khuôn mặt. Umm, xin lỗi, multi dimensional database mục đích dùng để chứa aggregate data, mục tiêu cuối cùng là cho statistic research. Còn để real time processing, đó không phải là thứ để xài. Thứ để xài cho real time processing phải hoặc là relational database, network database hay object oriented database. Now, bienca có thể nói rằng mình phát minh ra 1 lọai “multi dimensional data array” database mới vượt trội hơn cả những thứ mà hiện giờ hàng ngàn tay tiến sĩ và khoa học gia đang nghiên cứu và come up with, vậy thì xin chúc mừng. Nhưng những operations mà bienca đề ra, pivoting, slice-n-dice, những cái này không phải là operations của những OLAP “tầm thường” đó sao? And, những operations này dùng cho nghiên cứu data “chết” (static data), là những data collected qua hàng năm hàng tháng và được gạn lọc, filtered lại, là aggregate data. Những operations đó không phải là thứ operations cho ‘real time’ data, hay nói cách khác, là raw data.

Phương pháp này áp dụng cho bài toán tìm đường đi thì được, nhưng áp dụng cho multi-dimension data array thì rất phiền bởi 2 vấn đề sau:
- nhiều dữ liệu để save quá. Nội 1 relationship đã cần đến ít nhất: 2 IDs [+ attributes].
- query chậm chạm, thậm chí có khi chưa biết query kiểu nào.1 lần nữa, multi dimensional database không phải đẻ ra là vì giải quyết chuyện “nhiều dữ liệu để save quá” hay “query nhanh”. Bản thân multi dimensional database là kết quả gạn lọc và computed từ raw data trong những relational databases “tầm thường” mà ra. Nó không có đứng riêng rẽ 1 mình :)

À, không phải là neuron network model, nhưng lại rất giống tổ chức của neuron network :D

bienca101

07-07-2005, 12:39

nguoikicuc

08-07-2005, 09:44

Thua.

Mình chấp nhận là người thua cuộc trong cuộc tranh luận này. Mình rút lui không tranh luận nữa. Chấm hết. Nếu nguoikycuc thích thì hãy nhờ anh whiterose ra đề bài cho tree, bạn và mình sẽ viết code để tranh tài. Nếu chỉ tranh luận cò cưa kiểu này thì mình rút lui trước. Chả được cái gì, chỉ được cái tiếng xấu.

Còn về multi-dimension thì mình cũng thua luôn không tranh luận. Mình rút lui là vì "ông nói gà bà nói vịt". Ý tưởng của mình và ý tưởng của nguoikycuc không cộng hưởng nên chỉ thêm rối rắm. Một bên muốn tìm kiếm cái gì đó hay hơn những ý tưởng hiện tại, một bên cứ khăng khăng technology hiện tại đã quá ưu việt, ai dám chê thì hoặc là "bác học", hoặc là thằng ngu nổ quá lời. (Xin lỗi, mình to tiếng quá, thôi, chấm hết không tranh luận nữa).

Đây đâu có phải là sòng bài, hay là đấu trường đâu mà có chuyện thua hay thă'ng :) Ở đây chỉ có bàn luận về technical issues đê? trao đổi kiến thức và giúp đỡ lẫn nhau. Nếu xem mỗi cuộc bàn luận là thua hay thắng, thì còn gì là tình thần học hỏi và cầu tiến nữa :)

Đã nói là technical discussion, thì phải đâu ra đó rõ ràng, đen ra đen trắng ra trắng, logic phải đâu ra đó. Cho dù là nói về fuzzy logic đi nữa thì logic vẫn phải chính xác. Tôi chỉ lý luận dựa vào logic của bienca, và dựa vào những diều bienca đưa ra chứ tôi có đặt chuyện gì đâu :)

Còn về multi dimensional database ấy à, chính là bienca nói không rành rồi hỏi tôi, xong sau khi tôi bỏ công sức ra giải thích, you lại nói you biết rồi. Vậy nghĩa là gì? Có phải đó là tìm hiểu học hỏi không hay chỉ là tìm cách thách đố để khoe tài? Tiếc quá, bà con trong ddth này không được có dịp học hỏi quá trình nghiên cứu về "multi dimension data array" database trong vòng năm rưỡi qua của bienca, chac là vì tính chất "secret" :(

Peace :)

bienca101

08-07-2005, 12:44

<thở dài>

Nếu bạn có hứng thú. Mình muốn mời bạn một bữa uống trà cùng mình. Như vậy mình sẽ có dịp giải thích cho bạn hiểu ý mình đúng hơn, mà mình cũng có dịp học hỏi thêm từ bạn. Mình hoàn toàn open-minded, không nề hà gì đâu. Nhưng tranh luận theo xu hướng này thì misunderstanding và misperception nhiều quá.

Mình còn rất trẻ. Còn bạn chắc đã đứng tuổi và nhiều kinh nghiệm hơn mình. Tuy vậy, nếu bạn không chê thì mình xin mời bạn đi uống trà với mình một bữa. Đi nhậu thì mình xin kiếu, uống trà hay uống nước nhè nhẹ rồi nói chuyện cho vui thì mình rất sẵn lòng.

nguoikicuc

11-07-2005, 11:04

Cảm ơn về chuyện mời uống trà, tôi không có ở VN.

bienca101

11-07-2005, 12:23

Nguoikicuc ơi, thế bạn có ở Maryland, Washington D.C hay gần gần đâu đó không? Nếu có thì cho mình xin nick đi, bữa nào có dịp mình sẽ ghé thăm nguoikicuc.

Diễn đàn này hay ghê. Mình làm quen được với một số bạn mới. Nguoikicuc là người thứ nhì ở nước ngoài đã chỉ bảo thêm cho mình đấy. Vui thật, có diễn đàn và internet thấy mọi người xích lại gần nhau hơn.

NDThuan

11-07-2005, 12:50

Mình cũng có thử nghiên cứu vấn đề này, các bạn hãy xem http://www.vndesire.com/matxichBB/default2.asp và cho ý kiến. Có ai có gì muốn hỏi về cái tôi làm thử ko? :)
Rất vui đc trao đổi :)

bienca101

11-07-2005, 18:50

Có, tui nè. Cho tui biết điểm hay của sản phẩm của bạn đi.

NDThuan

12-07-2005, 08:41

Có, tui nè. Cho tui biết điểm hay của sản phẩm của bạn đi.
:D hì.
Bạn này đang mỉa mai tui roài, nó chẳng có cái gì hay hết :). Tôi đang nghiên cứu về việc thiết kế db và code để có thể tạo ra các ứng dụng phân cấp không giới hạn, thấy mấy bạn đang nói về thuật toán tree nên góp thử ý kiến vậy thôi. Tôi ko có ý tranh tài với mấy bạn đâu, tôi biết mình ko đủ sức :)

bienca101

12-07-2005, 17:53

Ui, không phải thế. Ý của mình là mình đã đến cái link của bạn. Mò mẫm một hồi rồi... chả hiểu gì :)

Bạn giới thiệu thêm một tí đi.

nguoikicuc

16-07-2005, 03:00

Nguoikicuc ơi, thế bạn có ở Maryland, Washington D.C hay gần gần đâu đó không? Nếu có thì cho mình xin nick đi, bữa nào có dịp mình sẽ ghé thăm nguoikicuc.
À không, tôi không có ở gần vùng này.