Some Characterizations of Finitely Specifiable Implicational Dependency Families

Document Type



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.


Electrical and Computer Engineering | Engineering


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.