tailieunhanh - Sự liên hệ giữa khái niệm xác định trực tiếp và các FD-đồ thị

Sự liên hệ giữa khái niệm xác định trực tiếp và các FD-đồ thị Cũng vì lý do đó mà Lý thuyết hệ thống tổng quát dù được đưa vào như một tiếp cận mới của các ngành khoa học khác nhưng chưa được hiểu biết, áp dụng sâu sắc, công nhận đúng vai trò cần có, cũng như khả năng thâm nhập giải quyết các vấn đề đặt ra của Thế giới quan và Triết học. | Tạp chí Tin học vầ Điều khiển học T. 18 s. 1 2002 9-14 THE RELATIONSHIP BETWEEN DIRECT DETERMINATION AND FD-GRAPH HO THUAN NGUYEN VAN DINH Abstract. The notion of direct determination was introduced by D. Maier 5 to study the structure of minimum covers. Using direct determination he showed that it is possible to find covers with the smallest number of FDs Functional Dependencies in polynomial time. In 2 G. Ausiello et al. presented an approach which is based on the representation of the set of FDs by FD-graph considered as a special case of the hypergraph formalism introduced in 7 . Such a representation provides a unified framework for the treatment of various properties and for the manipulation of FDs. In this paper we establish the relation between FD-graph and direct determination and prove some well-known and new properties concerning direct determination. Tóm tắt. Khái niệm xác định trực tiếp đã được trình bày bổũ D. Maier 5 để nghiên cú u cấu trúc các phủ cực tiều. Sú dụng khái niệm này ông đã chỉ ra rằng có thể tìm được các phủ vói số phụ thuộc hàm là ít nhất trong thời gian đa thức. Trong 2 G. Ausiello và các tác giả khác đã đu a ra một cách tiếp cận mới trên cơ sà biểu diễn tập các phụ thuộc hàm bằng một FD-đồ thị xem như một trường hợp đặc biệt cúa siêu đồ thị được giới thiệu trong 7 . Cách biểu diễn như vậy cho một khung thống nhất để xứ lý nhiều tính chất khác nhau và thao tác trên các FD. Trong bài báo này chúng tôi xác định mối liên hệ giữa FD-đồ thị và khái niệm xác HỊnh trực tiếp chúng minh một số tính chất quen biết và những tính chất mới liên quan đến khái niệm này. 1. BASIC NOTIONS AND RESULTS In this section we recall some notions and results which will be needed in the sequel. The reader is requứed to know the basic notions of the relational model and functional dependency 8 As usual we will only consider sets of FD in natural reduced form 4 and we assume that all attributes are chosen from some fixed universe Q. That means for any F Xi Yi I