Về các lược đồ cơ sở dữ liệu omega phi chu trình

Về các lược đồ cơ sở dữ liệu omega phi chu trình Điều khiển học thế hệ thứ nhất: Điều khiển học ra đời từ sự bắt đầu quan tâm các điểm giống nhau giữa những hệ tự lập: cơ thể sống và máy móc. Tuy nhiên, đến trước năm 1970, kỹ thuật điều khiển và máy tính chỉ mới tập trung về cách tiếp cận kỹ nghệ là người thiết kế hệ thống xác định hệ thống sẽ làm cái gì. Các hệ thống con người làm ra có tất cả kiến thức theo một cách duy nhất, chính...
Nội dung trích xuất từ tài liệu:
Về các lược đồ cơ sở dữ liệu omega phi chu trình T?-p chi Tin tioc va oo« khi€n tioc, T. 17, S.3 (2001), 53-59 ON THE DESIRABILITY OF {l-ACYCLIC DATABASE SCHEMES NGUYEN VAN DINHAbstract. In this paper we study a subclass of acyclic database schemes, the w- acyclic database schemes andsomeclosely related problems. We first prove that with this class given here, the notion of acyclic hypergraphsused by graph theorists is equivalent to the notion, in the sense relevant to database theories. In the last ofthe paper, new characterizations for the class of the w-acyclic database schemes are also given.T6m tll.t. Trong bai bao nay, chung t6i nghien CUll m9t 16-p con cila cac hroc do CO sO-dir lieu, d6 111, 16-p cachrocdo CSDL w- phi chu irinh, Chung t6i da chtrng minh diroc ding vo i lap nay thl khai niern phi chu trinh.cua cac sieu do thj diroc djnh nghia trong 1:9 th uyet do thi va trong 1:9 th uyet CSDL 111, tucng dirong. Phattrien cac ket qua cda 1:9 thuydt do thj, chung t6i da dua ra nhirng d~c trtrng m&icho 16-p cac hroc do nay. 1. INTRODUCTION Since 1979, Namibar K. K. is the first one, who presented the idea of using hypergraph as atool for the design of relational database schemes [8]. A database scheme is naturally viewed asa hypergraph. If R. is a database scheme over U, then R. may be viewed as a hypergraph (U, R.).That is, the attributes in R. are the nodes in the hypergraph and the relation schemes of R. are thehyperedges. For the first time, since 1981, the notion of acyclic database schemes was appeared in the studyof semijoins and the existence of a full reducer for a system for distributed databases (SDD-1) [10].Then pairwise consistency (PC), total consistency (TC), the connection of fain tree and full reducerof the database schemes were also studied [1], [3] [4]. These studies showed that if a database scheme is cyclic then the management is difficult andthe cost is high. In addition, a cyclic database scheme may has redundancies and lossy [oins, but anacyclic scheme has no above problems. In addition, it appears that queries whose hypergraph areacyclic have a number of optimization algorithms that are simpler and more efficient than those onein the general case. Thus, the acyclicity plays an important role on the database schemes; it is adesirable property of database schemes. There are many equivalent definitions for the notion of acyclic hypergraph, in the sense relevantto database systems. However, none of these definitions is equivalent to the one generally used bygraph theorists. Hence, the direct application of results of graph theory for the database schemes isvery difficult. Some authors presented the new notions of acyclic hypergraphs to study a subclass ofdatabase schemes, such as the l-acyclic database schemes [5]. In this paper, we consider a specialsubclass of database schemes, in which request that the intersection of nondisjoinst pair of relationschemes has only one attribute. We call this class the w-acyclic database schemes. We prove that forthis class the notion of acyclic hypergraphs used by graph theorists is equivalent to the definitions forthis notion, used in the database theories. Up to the present, many characteristics of acyclic database schemes were found and thereexists some algorithms to test cyclicity of the database schemes, such as Graham algorithm, G YOalgorithm ... [7], [9] [12]. In the last section of this paper, basing on the res ults of graph theory, we proved equivalenceof the new characterizations for the w-acyclic database schemes. The new characterizations showedthe relation between the number of attributes and the number of relation schemes on the w-acyclicdatabase schemes.54 NGUYEN VAN DINH 2. HYPERGRAPHS AND DATABASE SCHEMES BACKGROUND Some preliminary concepts about hypergraphs and acyclic database schemes presented in [2], [7], [9],[12] are summarized in this part.2.1. Hypergraphs and cycles. in a hyper graphDefinition 2.1. Let X = {Xl, X2, ... , X,,} be a finite set, and let C = {El E2, ... , Em} be a family ofsubsets of X. The family C is said to be a hypergraph on X if: (1) s. ¥= 0 (i E I = {I, 2, ... , m} ); (2) U e. = X. iEI The pair H = (X, C) is called a hypergraph. The elements Xl, X2, ... ,Xn are called the vertices(or nodes) and the sets El, E2, ... ,Em are called the hyperedges. H is reduced if no edge in C properly contains another edge and every node is in some ed ...