Về họ cực tiểu

Về họ cực tiểu Đóng góp cơ bản nhất của điều khiển học là giải thích được tính mục đích (hành vi hướng đích), một đặc trưng quan trọng của trí não và cuộc sống, dưới dạng điều khiển và thông tin. Những vòng điều khiển phản hồi ngược cố gắng đạt và duy trì những “trạng thái mục đích” được tìm thấy trong khi đó những mô hình cơ bản của các tổ chức tự trị: khi ý định chưa được định hình, hành vi của nó bị ảnh hưởng từ môi trường hoặc những quá trình năng động...
Nội dung trích xuất từ tài liệu:
Về họ cực tiểu TiJ-p chi Tin hqc va fJieu khien Iioc, T. 17, S.3 (2001), 48-52 ON THE MINIMAL FAMILY VU DUC THIAbstract. Equivalent descriptions of family of functional dependencies (FDs) play important role in thedesign and implementation of the relational datamodel. In this paper, we introduce the new concept ofminimal family. We prove that these families are equivalent descriptions of family of FDs.T6111 tl(t. Nhirng str mo ta tuong dircng cda ho cac phu thu9C ham c6 vai tro quan trong trong vi~c thietke va vi~c thu-c hien mo hlnh d ii li~u quan h~. Trong bai nay, chung tai trinh bay khai ni~m moi ve ho ctrctieu. Chung tai chrrng minh di.ng nhimg ho nay Ill, nhirng mo d. tirong dtrong cila ho cac phu thuoc ham. 1. INTRODUCTION It is known [1,4- 8,14,17] that closure operations, meet-semilattices, families of members whichare not intersections of two other members give the equivalent descriptions of FDs, i.e. they andfamily of FDs determine each other uniquely. These equivalent descriptions were successfully appliedto find many desirable properties of functional dependency. Equivalent descriptions of family of FDshave been widely studied in the literature. In this paper, we investigate the minimal family. We showthat it is equivalent description of family of FDs. Let us give some necessary definitions and results that are used in next section. The conceptsgiven in this section can be found in [1,2,4,6,7,8, 17]. Let R = {al, an} be a nonempty finite set of atributes. A functional dependency (FD) is astatement of the form A ----> B, where A, B ~ R. The FD A ----> B holds in a relation r = {hl, ..., hm}over R if V hi, h] E r we have hda) = h](a) for all a E A implies hdb) = h](b) for all b E B. We alsosay that r satisfies the FD A ----> B. Let F; be a family of all FDs that hold in r. Then F = F; satisfies(1) A ----> A E F,(2) (A ----> B E F, B ----> C E F) ~ (A ----> C E F),(3) (A ----> B E F, A ~ C, D ~ B) ~ (C ----> D E F),(4) (A ----> B E F, C ----> D E F) ~ (A U C ----> BuD E F). A family of FDs satisfying (1) - (4) is called an I-family (sometimes it is called the full family)over R. Clearly, F; is an I-family over R. It is known [1] that if F is an arbitrary I-family, then thereis a relation rover R such that F; = F. Given a family F of FDs, there exists a unique minimal I-family F+ that contains F. It can beseen that F+ contains all FDs which can be derived from F by the rules (1) - (4). A relation scheme s is a pair (R, F), where R is a set of attributes, and F is a set of FDs over R.Denote A+ = {a: A ----> {a} E F+}. A+ is called the closure of A over s. It is clear that A ----> B E F+iff B ~ A+. Clearly, if s = (R, F) is a relation scheme, then there is a relation rover R such that F; = F+(see [1]). Such a relation is called an Armstrong relation of s. Let R be a non empty finite set of attributes and P(R) its power set. The mapping H : P(R) ---->P(R) is called a closure operation over R if for all A, BE P(R), the following conditions are satisfied:(1) A ~ H(A),(2) A ~ B implies H(A) < H(B),(3) H(H(A)) = H(A). ON THE MINIMAL FAMILY 49 Let s = (R, F) be a relation scheme. Set H.(A) = {a: A --t {a} E F+}, we can see that H. is aclosure operation over R. Let r be a relation, s = (R, F) be a relation scheme. Then A is a key of r (a key of s) ifA --t R E F; (A --t R E F+). A is a minimal key of r( s) if A is a key of r( s) and any proper subsetof A is not a key of r(s). Denote K r (K.) the set of all minimal keys of r (s). Clearly, Kr, K. are Sperner systems over R, i.e. A, BE K; implies A g; B. Let K be a Sperner system over R. We define the set of antikeys of K, denoted by K-l, asfollows: K-1 = {A c R: (B E K) ==> (B g; A) and (A C C) ==> (:lB E K)(B ~ C)}.It is easy to see that K-1 is also a Sperner system over R. It is known [5] that if K is an arbitrary Sperner system over R, then there is a relation schemes such that K. = K. In this paper we always assume that if a Sperner system plays the role of the set of minimal keys(antikeys), then this Sperner system is not empty (doesnt contain R). We consider the comparisonof two attributes as an elementary step of algorithms. Thus, if we assume that subsets of Rarerepresented as sorted lists of attributes, then a Boolean operation on two subsets of R requires atmost IRI elementary steps. Let L ~ P(R). L is called a meet-irreducible family ...