Invariance of Keys with Respect to Operations of Table Algebras
- PDF / 150,974 Bytes
- 9 Pages / 594 x 792 pts Page_size
- 97 Downloads / 235 Views
CYBERNETICS INVARIANCE OF KEYS WITH RESPECT TO OPERATIONS OF TABLE ALGEBRAS V. N. Red’ko,1 D. B. Buy,1† and A. S. Senchenko1‡
UDC 004.655
Abstract. The problem of invariance of keys including simple keys is investigated as applied to operations of table algebras that are modern analogues of classical relational Codd algebras. It is shown that the keys being considered are invariant with respect to the operations of intersection, difference, selection, join, and division, but invariance does not hold for simple keys. The keys including simple keys are shown to be invariant with respect to the renaming operation. Necessary and sufficient conditions under which such keys including simple keys are invariant with respect to the operations of projection and active supplement are established. The results of this work are of theoretical and practical interest and can be used to choose optimal keys in designing relational databases. Keywords: database, table algebra, key. INTRODUCTION At present, information systems are widely used practically in all spheres of activity of man. Databases are kernels of the majority of information systems. Together with a large variety of database types, relational (tabular) databases whose mathematical model was first proposed by E. Codd [1, 2] are most widespread. From the mathematical viewpoint, a relational database is a finite set of finite relations of different arity between predetermined sets of elementary data, i.e., a relational database is a finite model. Table algebras [3] are constructed on the basis of Codd relational algebras and considerably develop them. They form the theoretical foundation of query languages of modern table databases. Elements of the carrier of a table algebra refine relational data structures, and signature operations are constructed from main table manipulations in relational algebras and SQL-like languages. In relational databases, an important role is played by keys of a table, i.e., one or several of its attributes whose values uniquely identify table records. With the help of (primary and external) keys, binary relations of the type “one-to-many” that are destined for supporting the integrity of databases are established. Keys are usually defined so that they are invariant with respect to any changes in database records. This paper considers the question of invariance of keys with respect to signature operations of table algebras. The obtained results are important for the choice of optimal keys in designing databases [4, 5]. BASIC DEFINITIONS Let us fix some nonempty set of attributes A = { A1 ,... , A n }. We call a scheme any finite subset of the set A and note that a scheme can be the empty set. A row s of a scheme R is understood to be a set of pairs s = {( A1¢ , d1 ),... , ( A ¢k , d k )} whose 1
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, †[email protected]; ‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, September–October, 2015, pp. 3–12. Original article submitted February 6, 2015. 1060-0396/
Data Loading...
