Luận án Một số phương pháp xử lý truy vấn mới trên cơ sở dữ liệu hướng đối tượng mờ

The modelling and manipulation of complex object and imprecise information

together are emerging as leading problems to the database research [60]. The

involvement of complex object & uncertainty measures in the data or attribute

values make the existing relational data models unanswered. Object oriented data

models are capable enough to handle complex objects but are restricted towards the

representation of imprecise or uncertain data. These problems in the database world

bring the innovative concept of object based fuzzy data model by extending the

object oriented data model and applying fuzzy techniques to it. The fuzzy object

data model is being continuously prototyped with the objective that it evolves into

a powerful knowledge representation methodology with inherent fuzzy reasoning

techniques for problem solving in complex and uncertain environment [44].

Research has started from defining fuzzy attribute, fuzzy object, fuzzy class and is

continuing to define relationship among fuzzy objects, attributes, classes and to

represent fuzziness at various level of class hierarchies [40], [41], [42], [43]

The increasing demand for applications in multimedia systems, hypertext

information systems and many other fields has raised the problem of enhancing the

Object Oriented(OO) data models for imprecise and uncertain data. It is recognized

that the fuzzy theory is suitably applied to human-oriented engineering fields, one

of which is fuzzy information processing, in particular database retrieval. Fuzzy OO

databases have been studied in [22, 23]. They describe fuzzy domains of attribute,

fuzzy reference relations, fuzzy instance of relations, or fuzzy is a relations. The

inheritance partial ordering relation has been already pointed out in [24]. However,

these studies are restricted to only a construction of data models.

Most of the fuzzy relational data models have a fuzzy relational algebra or a

fuzzy relational calculus which are theoretical foundations [25, 26, 27]. Several

query algebra for the OO databases have been developed on the different bases of

data models, such as Excess [28], [29] for Extra, Reloop [30] for O_2 [31], A



algebrar [32] for OSAM*[SY12] and the query algebra for ENCORE [34] which

are the mathematical foundations for their models.

Object oriented databases are considered better than relational databases ,due to

increasing demand of new approaches to deal with complex data, complex

relationship exiting among such data and large data intensive applications. Object

oriented databases are much suitable for modern database applications, like

CAD/CAM (Computer Aided Design/Computer Aided Manufacturing),

CASE(Computer Aided Software Engineering), GIS (Geographical Information

Systems), Spatial Databases, Office Automation; Knowledge based Systems,

Hardware and Software Design, Network Management, Multimedia databases,

VLSI (Very Large Scale Integrated) Design. In these applications, several types of

information inexactness exist. Such incomplete and ill-defined information has

been accepted, represented and manipulated with a certainty measure of acceptance

using fuzzy techniques. So FOOD deal with different fuzzy concepts, like =almost

all, =majority, =approximately, which include uncertainty. Complex object

Structures can be represented well without fragmentation of aggregate data and

complex relationship among attributes. Fuzzy object oriented database shows lack

of formal semantics and algebra for manipulation and representation of knowledge

as well DVWKHLQH[DFWLQIRUPDWLRQGDWDLQIRUPDWLRQ)X]]\UHODWLRQDOGDWDEDVHGRQ¶W

use the concept of reusability, but reusability of classes allows for faster

development and easier maintenance of the database and its application in FOOD.

pdf 147 trang chauphong 16/08/2022 11880
Bạn đang xem 20 trang mẫu của tài liệu "Luận án Một số phương pháp xử lý truy vấn mới trên cơ sở dữ liệu hướng đối tượng mờ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Luận án Một số phương pháp xử lý truy vấn mới trên cơ sở dữ liệu hướng đối tượng mờ

Luận án Một số phương pháp xử lý truy vấn mới trên cơ sở dữ liệu hướng đối tượng mờ
 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC 
VÀ CÔNG NGHỆ VIỆT NAM 
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ 
------------------------------- 
NGUYỄN TẤN THUẬN 
DANH MỤC CÔNG TRÌNH CÔNG BỐ 
LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH 
MỘ SỐ PHƯƠNG PHÁP XỬ LÝ TRUY VẤN MỚI 
TRÊN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ 
Chuyên ngành: Hệ thống thông tin 
Mã số: 9 48 01 04 
Hà Nội, 2021 
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 
STT TÊN BÀI BÁO 
[CT1] 
Nguyễn Tấn Thuận, Đoàn Văn Ban, Trương Ngọc Châu, Trần Thị Thúy 
Trinh (2015), “Phương pháp xử lý truy vấn đa điều kiện trong cơ sở dữ liệu 
hướng đối tượng mờ dựa trên đại số Gia Tử”, Tạp chí Khoa học Đại học Sư 
phạm Hà Nội 1, 7, 2015, 157-168. 
[CT2] 
Nguyễn Tấn Thuận, Trần Thị Thúy Trinh, Đoàn Văn Ban, Trương Ngọc 
Châu, “Analysis of fuzzy query processing and optimization in fuzzy object 
oriented database”, Fair - Hội nghị khoa học Quốc Gia lần thứ IX về nghiên 
cứu cơ bản và ứng dụng CNTT, Trường Đại học Cần Thơ , 2016, pp 24-31. 
[CT3] 
Nguyễn Tấn Thuận, Trần Thị Thúy Trinh, Đoàn Văn Ban, Trương Ngọc 
Châu, “Statistics-theoretical approach for evaluating the similarity of fuzzy 
objects in fuzzyobject-oriented databases”, Hội thảo quốc gia lần thứ XIX: 
Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông – Hà Nội, 
Trường Đại học Sư Phạm Hà Nội 1-2/10/2016, 306-312. 
[CT4] 
Thuan T.Nguyen , Ban D.Van, Chau N.Truong, “Qurey Processing and 
Optimazation in Fuzzy Object Oriented Database”, LAP LAMBERT 
Academic Publishing, ISBN 978-620-2-05295-5, 2017, 52 papers. 
[CT5] 
Nguyen, T. T., Doan, B. V., Truong, C. N.,& Tran, T. T, “A New Approach 
for Query Processing and Optimization Base on the Fuzzy Object Algebra 
and Equivalent Transformation Rules”. Transactions on Machine Learning 
and Artificial Intelligence, 2017, 5(2), 18. (scopus) 
[CT6] 
Nguyen, T. T., Van Doan, B., Truong, C. N., & Tran, T. T. T. “Clustering 
and Query Optimization in Fuzzy Object-Oriented Database”. International 
Journal of Natural Computing Research (IJNCR), 8(1),2019, 1-17. (DBLP) 
JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0063
Educational Sci., 2015, Vol. 60, No. 7A, pp. 157-168
This paper is available online at 
PHƯƠNG PHÁP XỬ LÍ TRUY VẤN ĐA ĐIỀU KIỆN TRONG CƠ SỞ DỮ LIỆU
HƯỚNG ĐỐI TƯỢNG MỜ DỰA TRÊN NGỮ NGHĨA ĐẠI SỐ GIA TỬ
Nguyễn Tấn Thuận1, Đoàn Văn Ban2
Trương Ngọc Châu3, Trần Thị Thúy Trinh1
1Khoa Công nghệ Thông tin, Đại học Duy Tân;
2Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam;
3Khoa Công nghệ Thông tin, Đại học Bách khoa Đà Nẵng
Tóm tắt. Bài báo này đề xuất các phương pháp xử lí truy vấn mờ thông qua hướng tiếp cận
ĐSGT. Bằng các phương pháp xử lí khác nhau như xác định giá trị chân lí, dựa trên cơ sở
đó chúng tôi xây dựng bộ truy vấn mờ cho các trường hợp xử lí đơn điều kiện và đa điều
kiện, kết quả được kiểm chứng thông qua lược đồ cơ sở dữ liệu hướng đối tượng mờ.
Từ khóa: ĐSGT,Giá trị chân lí, Đơn điều kiện, Đa điều kiện, truy vấn mờ
1. Mở đầu
Ngôn ngữ truy vấn trong CSDL mờ được các tác giả quan tâm nghiên cứu và đã có nhiều
kết quả. Truy vấn theo cách tiếp cận lí thuyết tập mờ [3, 8], truy vấn theo cách tiếp cận quan hệ
tương tự [1], truy vấn theo hướng tiếp cận ĐSGT [2]. Hầu hết, các tác giả đều xây dựng ngôn ngữ
truy vấn với mong muốn thao tác mềm dẻo, “chính xác” với dữ liệu mờ bằng cách tập trung xây
dựng các hàm thuộc, từ đó tùy theo ngữ nghĩa của dữ liệu để chọn các ngưỡng phù hợp khi thao
tác dữ liệu.
Tuy nhiên, mỗi ngôn ngữ truy vấn chỉ phù hợp với một mô hình CSDL mờ cụ thể mà không
có ngôn ngữ nào tổng quát cho các mô hình. Chẳng hạn, đối với ngôn ngữ truy vấn trên mô hình
CSDL mờ theo cách tiếp cận tập mờ, việc xác định giá trị chân lí của điều kiện mờ trong truy vấn
thường là khó khăn và kết quả của truy vấn phụ thuộc nhiều vào việc xây dựng các hàm thuộc.
Dựa trên mô hình đã được đề xuất [2] đó, chúng tôi tiếp tục nghiên cứu một số phương pháp
mới xử lí truy vấn hướng đối tượng mờ và xem xét việc đưa điều kiện lọc vào trong câu truy vấn
nhằm làm cho thao tác tìm kiếm dữ liệu trên mô hình này được mềm dẻo và phù hợp với thực tế.
Bài báo gồm 5 phần. Phần 2 giới thiệu mô hình CSDL hướng đối tượng mờ và đại số gia tử,
phần 3 khái quát lớp mờ trong cơ sở dữ liệu HĐT mờ, phần 4 trình bày các phương pháp xử lí truy
vấn trong CSDL hướng đối tượng mờ, phần 5 phương pháp truy vấn dữ liệu mờ và phần 6 đánh
giá hiệu năng.
Ngày nhận bài: 5/7/2015. Ngày nhận đăng: 10/11/2015.
Liên hệ: Nguyễn Tấn Thuận, e-mail: nguyentanthuan2008@yahoo.com.
157
Nguyễn Tấn Thuận, Đoàn Văn Ban, Trương Ngọc Châu, Trần Thị Thúy Trinh
2. Nội dung nghiên cứu
2.1. Mô hình cơ sở dữ liệu hướng đối tượng mờ dựa trên đại số gia tử
Một mô hình dữ liêu hướng đối tượng mờ được định nghĩa như một mở rộng mô hình dữ
liệu hướng đối tượng rõ bằng cách thay thế các đối tượng bởi các đối tượng mờ, các lớp bởi các
lớp đối tượng mờ và các kết hợp bởi các kết hợp mờ trên lược đồ CSDL HĐT.
Một hướng tiếp cận mới để xây dựng mô hình cơ sở dữ liệu hướng đối tượng với thông tin
mờ đó là dựa trên đại số gia tử (ĐSGT), một mô hình toán học về cấu trúc thứ tự ngữ nghĩa của
miền giá trị của biến ngôn ngữ [2, 4].
Xét một lược đồ CSDL hướng đối tượng mờ trên miền vũ trụ U = {CA1, CA2, . . . , Can}.
Mỗi thuộc tính Ai được gắn với một miền trị thuộc tính, kí hiệu là Dom(CAi), trong đó một số
thuộc tính cho phép nhận các giá trị ngôn ngữ trong lưu trữ hay trong các câu truy vấn và được gọi
là thuộc tính mờ. Các thuộc tính còn lại được gọi là thuộc tính kinh điển. Thuộc tính kinh điển Ai
được gắn với một miền giá trị kinh điển, kí hiệu là DAj . Thuộc tính mờ Ai sẽ được gắn một miền
giá trị kinh điển DAj và một miền giá trị ngôn ngữ LDAj hay là tập các phần tử của một ĐSGT.
Xem giá trị ngôn ngữ như là một phần tử của ĐSGT. Để bảo đảm tính nhất quán trong xử lí ngữ
nghĩa dữ liệu trên cơ sở thống nhất kiểu dữ liệu của thuộc tính mờ, mỗi thuộc tính mờ sẽ được gắn
với một ánh xạ định lượng ngữ nghĩa ĐSGT.
Theo cách tiếp cận này giá trị ngôn ngữ là dữ liệu, không phải là nhãn của các tập mờ biểu
diễn ngữ nghĩa của giá trị ngôn ngữ và ưu điểm cơ bản của nó là việc cho phép tìm kiếm, đánh
giá ngữ nghĩa của thông tin không chắc chắn chỉ bằng các thao tác dữ liệu kinh điển thường dùng
và do đó bảo đảm tính thuần nhất của kiểu dữ liệu trong xử lí ngữ nghĩa của chúng. Vì tất cả
các thuộc tính có miền trị chứa giá trị số trong CSDL đều tuyến tính, nên một cách tự nhiên ta
giả thiết ĐSGT được sử dụng là ĐSGT tuyến tính, do đó tập H+ và H− là tập sắp thứ tự tuyến
tính. Như vậy, cho X = (X,G,H,≤) với G = {0, c−,W, c+, 1}, H = H − ∪H+ với giả thiết
H− = {h1, h2, .., hp}, H+ = {h − 1, ..., h − q}, h1 > h2 > ... > hp và h − 1 < ... <
h − q là dãy các gia tử. Cho một ĐSGT tuyến tính đầy đủ AX = (X,G,H,∑,Φ,≤), trong đó
Dom(X) = X là miền các giá trị ngôn ngữ của thuộc tính ngôn ngữ X được sinh từ tập các phần
tử sinh G = {0, c−,W, c+, 1} bằng việc tác động các gia tử trong tậpH,∑ và Φ là hai phép tính
với ngữ nghĩa là cận trên đúng và cận dưới đúng của tậpH(x), tức là
∑
x = supremumH(x) và
Φx = infimumH(x), quan hệ ≤ là quan hệ sắp thứ tự tuyến tính trên X cảm sinh từ ngữ nghĩa
của ngôn ngữ.
2.2. Lớp mờ trong cơ sở dữ liệu hướng đối tượng mờ
Dựa vào các thảo luận trên, chúng ta thấy rằng các lớp trong CSDL hướng đối tượng mờ có
thể mờ. Theo đó, trong CSDL hướng đối tượng mờ, một đối tượng thuộc Z thuộc một lớp tùy theo
mức k và một lớp là lớp con của một lớp khác cũng theo mức k (k+). Trong CSDL hướng đối
tượng, một lớp được định nghĩa bao gồm mối quan hệ kế thừa, thuộc tính và phương thức. Để xác
định một lớp mờ, cần bổ sung một số định nghĩa mới. Khi khai báo mối quan hệ kế thừa cần chỉ ra
mức mà lớp này là lớp con của lớp cha, trong định nghĩa của một lớp mờ, các thuộc tính mờ có thể
được chỉ ra một cách rõ ràng. Về mặt hình thức, định nghĩa của một lớp mờ được thể hiện như sau:
158
Phương pháp xử lí truy vấn đa điều kiện trong cơ sở dữ liệu hướng đối tượng mờ dựa trên ngữ nghĩa...
CLASS tên lớp
INHERITES
tên lớp cha thứ 1 WITH LEVEL OF mức_1
. . .
tên lớp cha thứ n WITH LEVEL OF mức_n
ATTRIBUTES
tên thuộc tính thứ 1: [FUZZY] DOMAIN dom_1: TYPE OF kiểu_1
. . .
tên thuộc tính thứ m: [FUZZY] DOMAIN dom_m: TYPE OF kiểu_m
METHODS . . .
END
Đối với các thuộc tính không phải là thuộc tính mờ, các kiểu dữ liệu bao gồm các loại đơn
giản như số nguyên, thực, logic, chuỗi, và các loại phức tạp như kiểu tập hợp và kiểu đối tượng.
Đối với thuộc tính mờ, các kiểu dữ liệu là kiểu mờ dựa trên các kiểu dữ liệu đơn giản hoặc phức
tạp, cho phép biểu diễn thông tin không chính xác [10].
2.3. Ngôn ngữ truy vấn trong cơ sở dữ liệu hướng đối tượng mờ
2.3.1. Truy vấn dữ liệu mờ
Việc xác định giá trị chân lí của điều kiện mờ trong truy vấn thường là khó khăn và kết quả
của truy vấn phụ thuộc nhiều vào việc xây dựng các hàm thuộc. Nếu chúng ta xem miền trị của
thuộc tính mờ là một ĐSGT thì việc xây dựng ngôn ngữ truy vấn trên mô hình CSDL HĐT mờ để
phù hợp với ngữ nghĩa mới là cần thiết cho việc thao tác và tìm kiếm dữ liệu, giá trị chân lí của
điều kiện mờ trong câu truy vấn được xác định đơn giản và hiệu quả. Vấn đề quan tâm ở đây là
một ngôn ngữ được đề xuất dùng để truy vấn dữ liệu trong mô hình CSDL HĐT mờ đã được xây
dựng trong phần 4.1. Do đó, trước tiên phải đi xây dựng các thuật toán xác định giá trị chân lí của
điều kiện mờ để làm cơ sở khi truy vấn dữ liệu, tiếp đến áp dụng các thuật toán vừa xây dựng để
thực hiện truy vấn.
2.3.2. Câu lệnh Select
SELECT 
FROM 
WHERE 
Trong đó, là một điều kiện mờ hoặc liên kết các điều kiện mờ có sử
dụng các phép toán tuyển và hội, k là số nguyên dương.
2.3.3. Thuật toán xác định giá trị chân lí của điều kiện mờ
Thuật toán 1. Xác định giá trị chân lí của đơn điều kiện mờ với phép toán θ
Vào: Lớp C cùng với các thuộc tính {A1, A2, . . . , An}, tập các đối tượng thuộc lớp C:
{Oi, i = 1, . . . ,m}
Điều kiện Ai θ fvalue, với fvalue là giá trị mờ và Ai là thuộc tính mờ C tính đơn điệu,
159
Nguyễn Tấn Thuận, Đoàn Văn Ban, Trương Ngọc Châu, Trần Thị Thúy Trinh
θ ∈ {= k, 6= k, k}.
Ra: Với mọi t ∈ O thoả mãn điều kiện t[Ai]θ fvalue
Phương pháp
Begin
for each t ∈ O do
if t[Ai] ∈ DAi then t[Ai] = Φk(f(t[Ai])) // Xây dựng các P k dựa vào độ dài các từ.
k = 1
while k ≤ p do
begin
P k = Φ
for each t ∈ O do
if |t[Ai]| = k then P k = P k ∪ {I(t[Ai])}
k = k + 1
end
if θ là phép toán = k then
begin
k = p
while k > 0 do
begin
for each ∆k ∈ P k do
begin
if (I(t[Ai]) ⊆ ∆k and I(fvalue) ⊆ ∆k) then
(t[Ai] = k fvalue) = 1
exit
end
k = k − 1
end
end
else
begin
k = 1
while k ≤ p do
begin
for each ∆k ∈ P k do
begin
Case θ of
6=k: if I(t[Ai]) 6⊂ ∆k or I(fvalue) 6⊂ ∆k then (t[Ai]θ fvalue) = 1
160
Phương pháp xử lí truy vấn đa điều kiện trong cơ sở dữ liệu hướng đối tượng mờ dựa trên ngữ nghĩa...
< k: if (t[Ai] 6= k fvalue) and v(t[Ai]) < v (fvalue) then (t[Ai]θ fvalue) = 1
> k: if (t[Ai] 6= k  ... R4. Permutation selection and projection:
rks:e P a1;...; anð Þ l eFC oð Þ
  
¼ P a1;...; anð Þ rks:e l eFC oð Þ
  
R5. Permutation and a projection over union, on a set/multiset:
P a1;...;anð Þ l eFC1 oð Þop l eFC2 oð Þ
 
¼ P a1;...;anð Þl eFC1 oð Þ opP a1;...;anð Þl eFC2 oð Þ
56 T. T. Nguyen et al.
R6. The selection operation distributes over the union, and difference, on a set/multiset
rksf l eFC1 oð Þop l eFC2 oð Þ
 
¼ rksf l eFC1 oð Þ
 
op l eFC2 oð Þ; if f is related to l eFC1 oð Þ
Generality:
rks f^g^hð l eFC1 oð Þop l eFC2 oð Þ
 
¼ rkuh rksf l eFC1 oð Þ
 
op rktg l eFC2 oð Þ
  
; if f is related to l eFC1 oð Þ;
g is related to l eFC2 oð Þ and h related to both l eFC1 oð Þ and l eFC2 oð Þ
R7. Permutation between selection operation and apply operation: if conditions only
contain attributes selected by the operation returns apply:
applyklse rktf l eFC oð Þ
  
¼ rktf applyklse l eFC oð Þ
  
R8. Permutation between flat and apply on set and multiset: suppose that l eFC oð Þ is an
instance of a class and x is a complex set of attributes of the class:
flat apply
ks applykte P Xð Þ PV leFC oð Þ
     l eFC oð Þ
 0@
1
A
¼ applykte flat applyksP Xð Þ PV l eFC oð Þ
  
l eFC oð Þ
   
R9. Set union is associative:
l eFC1 oð Þ union l eFC2 oð Þ
 
unionl eFC3 oð Þl eFC1 oð Þ union l eFC2 oð Þ unionl eFC3 oð Þ
 
R10. The inheritance laws to allow the selection and apply: if fFC2 is a subclass offFC1, instance of l eFC2 oð Þ is a subset of instance of l eFC1 oð Þ.
rksf l eFC1 oð Þ
 
unionrksf l eFC1 oð Þ
 
¼ rksf l eFC1 oð Þ
 
applykse l eFC1 oð Þ
 
union applykse l eFC2 oð Þ
 
¼ applykse l eFC1 oð Þ
 
A New Approach for Query Processing 57
3.2 FOQL to Fuzzy Object Algebra Translation
The transformation equivalence between FOQL queries and fuzzy object algebra.
Definition. If E is a fuzzy object algebraic expression and Q fuzzy query object is
FOQL together define sets of fuzzy object, we say Q represent E and the opposite; we
call E equivalent to Q. Symbol E 
 Q.
Equal representation between the query language and algebra FOQL fuzzy object is
expressed through two theorems 1 and 2 as follows:
Theorems 1. Every algebraic expression is fuzzy object represented by the object
query in FOQL.
Theorems 2. Every fuzzy object in FOQL queries are represented by algebraic
expressions fuzzy object
Thus, rewrite a given query into algebraic expressions with algebraic set objects are
equivalent. The algebraic expressions can be estimated with different abatement costs.
So theoretically, we wanted to find an algebraic expression equivalent to a query so that
it can achieve a plan for more effective enforcement. However, in the solution installed,
because the number of queries equivalent too large, we only need a subset of this query.
Therefore, in order to find other similar queries, we will need a set of rules to transform
the equivalent algebraic expressions. So, we wanted to prove that the transformation
preserved on a basis equivalent algebraic fuzzy objects that may be acceptable. Some
transformation rules is presented [4].
3.3 Heuristic Optimization Based on Algebraic Equivalences
1. Search space and transformation rules.
The most important advantage of processing and optimizing fuzzy algebra is that
through the algebraic expression of the object, we can use algebraic properties such as
transformation, distribution. Therefore, each fuzzy query has the number of different
equivalent expressions that depend on the input of the query from the user’s request.
These expressions are corresponding to the results they created, but different from their
costs. However, fuzzy query optimizers modify fuzzy query expressions by using
algebraic transformation rules to achieve the same results at the possible lowest cost.
The transformation rules depend a lot on specific objects, as they are determined
properly for each object algebra and their combinations.
2. Search algorithm
Heuristic
1. The parser of a high-level fuzzy query creates an initial internal representation;
2. Apply heuristics rules to optimize the internal representation.
58 T. T. Nguyen et al.
3. A fuzzy query execution plan is generated to execute groups of operations based on
the access paths available on the files involved in the fuzzy query.
The main heuristic is to apply first the operations that reduce the size of intermediate
results.
For example, apply fuzzy SELECT and fuzzy PROJECT operations before
applying the fuzzy JOIN, or other binary operations.
Outline of a heuristic fuzzy object algebraic optimization algorithm:
1. Using rule R2, break up any select operations with conjunctive conditions into a
cascade of select operations.
2. Using inheritance laws for projection (R3), the selection and allows apply (R10)
combination of projection, select a projection and a selection.
3. For each selection, use the law (R4, R6, R7, R10) “pushed” to allow the selection
components to classes or “through” connection nodes and allows creation group.
4. For each projection (objects, sets, sets), use legislation (R3, R4, R5) to projection
move down as far as possible. If the projected attributes include all the attributes of
the expression, we remove that projection.
5. Using the law (R8, R9, R10) on the object class, to remove duplicate elements in
the object class; move allows flattened (flat), lets remove duplicates in multiple files
(bagtoset) ahead of the group or connection operations.
6. Creating a sequence of steps for estimating change in an order every star team for
no group is evaluated; its subgroups.
3.4 Fuzzy Query Execution Plans
After translating the fuzzy query into a fuzzy algebra expression, the query processor
passes the expression to the query optimizer, generates different execution plans, or a
combination of operators.
There are some of algebraic transformations that are performed in the query opti-
mizer to create equivalent (rational) query plans. By removing eð Þ and Push erð Þ.
1. Execution plan
The query processor converts the query to an equivalent fuzzy algebra expression for
the input query and forward it to the query optimizer. The first fuzzy algebraic object
created by the query processor involves in the fuzzy Cartesian product called execution
plan execution.
Example 1: returns the list of names of old salespersons whose Age are ‘very old.’
In FOQL, it can be represented as:
SELECT Name FROM OldSalesPerson as O, SalesPersons as S WITH 0.6
WHERE O.foid = S.foid AND O. Age = ‘very old’ WITH 0.7.
A New Approach for Query Processing 59
In Fuzzy object Algebra above FOQL statement is represented as:
epName erOldSalesPersons:foid¼salesPersons:foid^OldSalesPersons:Age¼0 very old0SalesPersons e OldSalesPersonsð Þ
 
The above expression is represented by the algebraic tree as Fig. 2:
2. Elimination of eð Þ
The eð Þ operations can be combined with erð Þ operations (and sometimes, with fuzzy
projection operations) which use data from both relations to form joins. After replacingeð Þ with efflð Þ; fuzzy object algebra for the query given in example 1 can be presented
as:
epName erOldSalesPersons:Age¼0very old0SalesPersons effl OldSalesPersons:foid¼SalesPersons:foid
OldSalesPersonsð Þ
 0@
1
A
Figure 3 shows gives the operator tree of the above algebraic expression:
Fig. 2. Implementation plan concern in eð Þ
Fig. 3. Implementation plan using efflð Þ
60 T. T. Nguyen et al.
3. Push erð Þ
By pushing erð Þ operation down the expression tree, we actually reduce the size of
relations we need to do before. The fuzzy object algebra for the fuzzy query written in
example under push fuzzy selection strategy can be presented as:
epName SalesPersons efflOldSalesPersons:foid¼SalesPersons:foiderOldSalesPersons:Age¼0very old0
OldSalesPersonsð Þ
 0@
1
A
Figure 4 is a description of their above fuzzy object algebra expression:
4 Performance Evaluation
To provide preliminary performance evaluation on implementation of query, pro-
cessing has been proposed based on fuzzy object algebra [4]. We defined the three
queries processed condition extract filter data for two cases of single conditions, most
conditions and implement them on the same dataset.
The fuzzy query processor first extract filter data for single condition processing
cases. Request query processing engine returns all employees age is very old. Such
queries are written as follows:
SELECT * FROM OldSalesPersons, SalesPersons WITH 0.6
WHERE AND OldSalesPersons.Age = ‘very old’ WITH 0.7.
The second query processing extracts filter data for single-case conditions and
enables a natural join. Request query processing engine return all employees age is
very old. Such queries are written as follows.
SELECT Name FROM OldSalesPerson as O, SalesPersons as S WITH 0.6
WHERE O.FIOD = S.FOID AND O.Age = ‘very old’ WITH 0.7.
Fig. 4. Pushing erð Þ down the tree
A New Approach for Query Processing 61
The third query processing the extract filter data for single-case conditions and
enable a natural join. After performing the optimization algebra objects. Request query
processing engine return all employees age is very old. Such queries are written as
follows.
SELECT Name FROM SalesPersons as S inner join OldSalesPersons as O on O.
FIOD = S.FOID WITH 0.6 WHERE O.Age = ‘very old’ WITH 0.7.
From the above experiments, results achieved confirm that the performance of this
method is effective. As an example, we evaluate the query according to this approach
from the chart the way the query results shown in Fig. 5.
5 Conclusion
This paper presents a new model for optimizing the efficiency of query processing by
semantic analyzing and FO algebra transforming. Specifically, we develop a heuristic
fuzzy object algebraic optimization algorithm relied on equivalent transformation rules
and fuzzy object algebra transformation. Analysis on several experiments using the
proposed algorithm shows better performance of query processing, which proves the
efficiency enhancement of our method.
References
1. Selee Na.: A Process of Fuzzy Query on New Fuzzy Object Oriented Data Model, In IEEE
Tranon Knowledge and Data Engineering. 1(2010), 500–509.
2. Stefano Ceri, Georg Gottlob.: Translating SQL Into Relational Algebra: Optimization,
Semantics, and Equivalence of SQL Queries, Software Engineering, IEEE Transactions, vol.
SE-11, issue 4, 4(1985). 324–345.
Fig. 5. Query performance
62 T. T. Nguyen et al.
3. XU Silao, HONG Mei.: Translating SQL Into Relational Algebra Tree-Using
Object-Oriented Thinking to Obtain Expression Of Relational Algebra, IJEM, vol.2, no.3,
(2012). 53–62.
4. Truong Ngoc Chau, Nguyen Tan Thuan.: A Approach New In The Algebra Fuzzy Object,
Proceedings of the @ Conference, Viet Nam. 11(2013), 204–209.
A New Approach for Query Processing 63

File đính kèm:

  • pdfluan_an_mot_so_phuong_phap_xu_ly_truy_van_moi_tren_co_so_du.pdf
  • pdfDongGopMoi_TiengAnh.pdf
  • pdfDongGopMoi_TiengViet.pdf
  • pdfTOANVANLUANAN_NGUYENTANTHUAN.pdf
  • pdfTomTatLuanAn_ENGLISH_NGUYENTANTHUAN.pdf
  • pdfTomTatLuanAn_TiengViet_NGUYENTANTHUAN.pdf
  • pdfTrichYeu_LATS.pdf