508 Definitions

These are in no particular order - just as I think of them.

1. Assuming that all queries specify one field, and that p_i is the probability that f_i is the field specified, and that we have 2^B buckets and k fields, the number of bits of the address to assign to each field in order to minimize the average search time is given by b_i = (B - sum over j of lg p_j) / k + lg p_i
   
2. Assuming that queries specify one or more fields, and that p_i is the probability that the value of that field is known, and that we have 2^B buckets and k fields, the number of bits of the address to assign to each field in order to minimize the average search time is given by b_i = (B - sum over j of lg (p_j / (1-p_j)) / k + lg (p_i / (1-p_i) )
   
3. Physical data independence refers to when changes in the physical level organization of a database do not affect the logical level.

4. Logical data independence refers to when modifications to the logical level structure do not affect existing view structures.

5. Given a collection of sets D₁, D₂, ..., D_n (not necessarily distinct), R is a relation on those sets if it is a set of ordered n-tuples <d₁, d₂, ..., d_n> such that d_i is an element of D_i, 1<=i<= n.

6. A record is composed of fields. The manner in which the fields are organized within the record is called the record structure.


7. A file is composed of records. The manner in which the records are organized within the file is called the file structure.
   
   
8. An ISAM file has three parts: the main file, the index file and the overflow file.
   
   
9. An attribute value is atomic if it is non-decomposable.

10. A relation is normalized or in first normal form is every attribute value in each tuple is atomic. A relvar is in first normal form if any reasonable relation created with that relvar would be normalized.

11. A key or candidate key is a non-redundant set of attributes that have unique values in each tuple of the relation. One candidate key is chosen to be the primary key. The other keys are referred to as alternate keys.

12. Integrity refers to the fact that the data is correct. There are many ways to enforce integrity including (but not limited to) entity integrity, functional dependecies, referential integrity and domains.

13. Entity Integrity: no component of a primary key value may be null.

14. Referential Integrity: if an attribute, which is a primary key in one relation, occurs in a second relation, then the values of that attribute in the second relation must occur in the first relation.

15. A given domain may optionally be designated as primary iff there exists some single-attribute primary key defined on that domain.

16. A given attribute is prime if it is part of a key.
    
    
17. If r(A₁...A_n) is a relation and D_i = dom(A_i) 1 <= i <= n, then the active domain of A_i relative to r is the set

18. Let adom(R,r) be the set of all tuples over the attributes of R and their active domains relative to r. The active complement of r is

19. The notation r(R) means that r is a relation with relvar R.
    
    
20. Let r(R) be a relation, A is an element of R, a is an element of dom(A). Then restrict(select) A equal to a on r, written , is defined as

21. Let r(R) be a relation, X is a subset of R. The projection of r onto X, written Π_X(r), is the relation

22. Given r(R) and s(S) are relations and T=R ∪ S, the join of r and s, r><s, is the relation

23. Let q(RS) be a relation, with r= Π_R(q) and s= Π_S(q). Let q'= r>< s. If q=q', then q decomposes losslessly onto R and S.

24. The project-join procedure is idempotent (the result of applying it n times is the same as the result of applying it once.)

25. A constant relation is one where the tuple values are fixed.

26. Let r(R) be a relation, A ∈ R, and B ∉ R-A and dom(A)=dom(B). Let R'=(R-A)B. Then r with A renamed to B, denoted δ_A<-B (r) is the relation

27. Let r(R) and s(S) be relations, with S⊂ R. Let R'=R-S. Then r divided by s, is the relation

28. Let r(R) and s(S) be relations, R ∩ S = ∅, with A_i∈ R, B_i∈S and dom(A_i)=dom(B_i), 1<= i <=m. The A_i's need not be distinct, nor need the B_i's. The equijoin of r and s on A₁...A_m and B₁...B_m written r[A₁=B₁,...,A_m=B_m]s is the relation

29. Let r(R) and s(S) be relations, R∩ S = ∅. Let A∈ R and B∈ S be ρ-comparable for ρ∈ Θ. Then the theta-join of r and s on A and B, written r[AρB]s, is the relation

30. Let r(R) be a relation with X∈ R and Y∈ R. Relation r satisfies the functional dependency X->Y if for every x∈X, has at most one tuple.

31. We have a functional dependency of Y on X if any relation r (which is meaningful) on R will satisfy X->Y.

32. Given a set of functional dependencies F, and X->Y ∈ F⁺, Y is partially dependent upon X under F if X->Y is not left reduced. If X->Y is left reduced, then Y is fully dependent on X.

33. X->Y is left reduced if there does not exist any X'∈ X such that X'->Y.

34. Given a relvar R, A ∈ R, and a set F of functional dependencies over R, A is prime in R with respect to F is A is contained in some key of R. Otherwise A is nonprime in R.

35. A relation scheme R is in second normal form with respect to a set of functional dependencies F if it is in first normal form and every nonprime attribute is fully dependent on every key of R.

36. Given a relation scheme R, X∈R , A∈R , and a set of functional dependencies F, A is transitively dependent on X in R if there is a subset Y of R such that,
       X->Y, Y !-> X, and Y->A under F and A ∉ XY

37. A relation scheme R is in 3NF with respect to a set of functional dependencies F if it is in 1NF and no nonprime attribute in R is transitively dependent upon a key of R.

38. A relation scheme R is in Boyce Codd Normal Form if whenever Y->A holds, A ∉ Y, then Y is or contains a key of R.

39. Let r(R) be a relation, A⊂R , B⊂R, C=R-AB. The multi-valued dependency, A->>B holds iff for every t₁,t₂∈ r, with t₁(A)=t₂(A) then ∃ t₃,t₄∈r such that t₁(A)=t₃(A)= t₄(A) and t₁(B)=t₃(B) and t₂(C)=t₃(C) and t₂(B)=t₄(B) and t₁(C)=t₄(C).

40. X->>Y is trivial if for any R with XY∈ R, any r(R) satisfies X->>Y.

41. A relvar is in 4NF with respect to a given set of functional dependencies and multivalued dependencies iff it is in 3NF and for every MVD X->>Y, either the MVD is trivial or X is or contains a key of R.

42. Let {R₁,R₂,...,R_p} be a set of relvars over U. A relation r(U) satisfies the join dependency, *[R₁,R₂,...,R_p] if r decomposes losslessly onto R₁,R₂,...,R_p.

43. A join dependency is trivial if R=R_i for some 1≤i≤p or if every R_i contains a key of U.

44. Let R be a relvar and let F be a set of fd's and jd's over R. R is in 5NF with respect to F if for every JD implied by F that applies to R, the JD is trivial.

     

    The End - I ain't goin' to do no mor'!