Some Characterizations of Finitely Specifiable Implicational Dependency Families

Document Type

Article

Publication Date

10-22-1986

Publication Title

Information Processing Letters

Volume

23

Issue

3

First page number:

153

Last page number:

158

Abstract

Let r be a relation for the relation scheme R(A1,A2,…,An); then we define Dom(r) to be Domr(A1)×Domr(A2)×…×Domr(An), where Domr(Ai) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.

The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r1,r2,…,rm for R such that r ∈ F if and only if no ri is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.

We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.

Keywords

Implicational dependencies; Mathematical logic; Relational model

Disciplines

Electrical and Computer Engineering | Engineering

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS