Truy vấn hướng đối tượng dựa trên đồ thị chữ ký nhị phân

Bài viết xây dựng một mô hình cấu trúc đồ thị để tổ chức lưu trữ chữ ký của các đối tượng trong cơ sở dữ liệu hướng đối tượng, trong đó các đối tượng được mã hóa và xây dựng dưới dạng một đồ thị chữ ký, từ đó xây dựng thuật toán để xử lý truy vấn trên đồ thị chữ ký và đề xuất mô hình ứng dụng.
Nội dung trích xuất từ tài liệu:
Truy vấn hướng đối tượng dựa trên đồ thị chữ ký nhị phânTruy vấn hướng đối tượng . . . TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ NHỊ PHÂN Trương Công Tuấn*, Trần Minh Bảo**TÓM TẮT Bài báo xây dựng một mô hình cấu trúc đồ thị để tổ chức lưu trữ chữ ký của các đối tượngtrong cơ sở dữ liệu hướng đối tượng, trong đó các đối tượng được mã hóa và xây dựng dưới dạngmột đồ thị chữ ký, từ đó xây dựng thuật toán để xử lý truy vấn trên đồ thị chữ ký và đề xuất môhình ứng dụng. Từ khoá: hướng đối tượng cơ sở dữ liệu; cơ cấu chỉ số; chữ ký; tập tin chữ ký; đồ thị chữ ký OBJECT-ORIENTED QUERY PROCESSING BASED BINARY SIGNATURE GRAPHABSTRACT In this paper, we construct a graph structure model to store object signatures in object-oriented databases, in which the objects are hash encoded and presented by a signature graph.Then we built an algorithm to process the query on signature graph and propose an applicationmodel. Keyword: Object-oriented database; index structure; signature; signature ile; signature graph. 1. ĐẶT VẤN ĐỀ tượng trên cây chữ ký SD-Tree [3], truy vấn Truy vấn trực tiếp trên các đối tượng trong đối tượng trong cơ sở dữ liệu hướng đối tượngcơ sở dữ liệu hướng đối tượng rất tốn kém chi dựa trên cấu trúc cây chữ ký đối tượng [2], xâyphí lưu trữ dữ liệu trong quá trình truy vấn dựng cấu trúc tập tin chữ ký và cây chữ ký [8],và tốn nhiều thời gian để thực hiện truy vấn xây dựng cấu trúc đồ thị chữ ký dựa trên tập tintrên hệ thống dữ liệu thực. Bài toán đặt ra là chữ ký để truy vấn trong cơ sở dữ liệu hướngcần mô tả lại hệ thống dữ liệu đơn giản hơn đối tượng [9, 12], xây dựng cấu trúc cây chữ kývà xây dựng cấu trúc dữ liệu tương ứng để có để giảm không gian tìm kiếm dữ liệu [1, 2, 7,thể giảm không gian tìm kiếm trong quá trình 10], truy vấn dữ liệu trên tập tin văn bản bằngthực thi câu truy vấn mà vẫn đảm bảo được tập tin chữ ký tuần tự và tập tin chữ ký phânviệc truy vấn được các đối tượng cần thiết. mảnh [4], tạo chỉ mục truy vấn cho các tập tin Các phương pháp truy vấn dựa trên chữ văn bản [5, 6], tạo cấu trúc cây chữ cân bằngký nhị phân đã công bố như: truy vấn đối và thao tác trên cây chữ ký cân bằng [1, 8],…* PGS.TS. Trường Đại học Khoa học, Đại học Huế. E-Mail: tctuan_it_dept@yahoo.com** ThS. GV. Trường Đại học Công nghiệp Thực phẩm Tp.HCM. E-Mail: tmbaovn@gmail.com 59Tạp chí Kinh tế - Kỹ thuật Bài báo sẽ tiếp cận phương pháp tạo chữ giá trị thuộc tính. Chữ ký của một giá trị thuộcký cho các đối tượng, từ đó xây dựng cấu trúc tính là một chuỗi bít được mã hóa bằng hàmđồ thị để tham chiếu đến cơ sở dữ liệu thực. băm, có độ dài với bít 1 và bít 0. Chữ ký đốiChữ ký nhỏ hơn rất nhiều so với đối tượng tượng được xây dựng bằng phép toán OR bítthực, khoảng từ 10% – 20% so với đối tượng cho tất cả các chữ ký của các giá trị thuộc tính[4, 5, 8]. Chữ ký của các đối tượng sẽ được của đối tượng [1].lưu trữ trong tập tin chữ ký và qua đó thực Các chữ ký đối tượng của một lớp đượchiện phép truy vấn các đối tượng dựa trên tập lưu trữ trong một tập tin, gọi là tập tin chữtin chữ ký này. Ngoài ra, để việc tìm kiếm ký. Tập tin chữ ký tuần tự SSF (Sequentialhiệu quả hơn, cần xây dựng cấu trúc dữ liệu Signature File) gồm các chữ ký đối tượnglưu trữ tập tin chữ ký. Cấu trúc lưu trữ tập được lưu trữ tuần tự [1, 3, 8].tin chữ ký này có thể dưới dạng các tập tin Một câu truy vấn chỉ định các giá trị cầnchữ ký tuần tự, các tập tin chữ ký phân mảnh, tìm kiếm cũng sẽ được mã hóa thành chữ kýcấu trúc cây chữ ký, cấu trúc dạng đồ thị chữ truy vấn giống như cách mã hóa chữ ký cácký,… các cấu trúc lưu trữ tập tin chữ ký sẽ giá trị thuộc tính của đối tượng. Lúc đó chữlàm giảm không gian tìm kiếm và tối ưu quá ký truy vấn được so sánh đối với mọi chữ kýtrình truy vấn dữ liệu. đối tượng trong tập tin chữ ký. Có ba trường Bài báo mô tả lại hệ thống dữ liệu thực hợp có thể xảy ra:trở thành một cấu trúc dữ liệu tham chiếu có 1. Đối tượng phù hợp với câu truy vấn,không gian tìm kiếm nhỏ hơn để từ đó giảm nghĩa là đối với mọi tập bít trong chữ ký truythời gian truy vấn dữ liệu và đồng thời cấu vấn sq, tập bít tương ứng tron ...