Database(7) -- Design Theory

LeetCode Day 36: P225. Implement Stack using Queues (Easy)

题目：

用queue实现stack。

答案：

class MyStack {

    private Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.add(x);
        for (int i=1; i<queue.size(); i++)
            queue.add(queue.remove());
    }

    public void pop() {
        queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

每次添加元素时，都把这个List循环一圈，把它放到首位。

Database

Functional Dependencies

Functional Dependency(FD): if two tuples of R agree on all of the attributes A1, A2, …, An (i.e., the tuples have the same values in their respective componenets for each of these attributes), then they must also agree on all of another list of attributes B1, B2, …, Bm.

A1A2…An -> B1B2…Bm

Keys of Relations

A set of one or more attributes {A1, A2, …, An} is a key for a relation R if:

1. Those attributes functionally determine all other attributes of the relation. (Unique)
2. No proper subset of {A1, A2, …, An} functionally determines all other attributes of R; i.e., a key must be minimal.

Sometimes a relation has more than one key. It is common to designate one of the keys as the primary key.

Superkeys

Superkey is “superset of a key”. It need not satisfy the second condition: minimality.

Rules About Functional Dependencies

• Two sets of FD’s S and T are equivalent if the set of relation instances satisfying S is exactly the same as the set of relation instances satisfying T. （如果满足两组依赖的关系表完全相同，则这两组依赖是等价的）
• More generally, a set of FD’s S follows from a set of FD’s T if every relation instance that satisfies all the FD’s in T also satisfies all the FD’s in S. (如果满足T中所有依赖的每一个表实例同时满足S中的所有依赖，则T->S)

S and T are equivalent <=> S follows from T, and T follows from S.

The Splitting/Combining Rule

• We can replace an FD A1A2…An -> B1B2…Bn by a set of FD’s A1A2…An ->Bi for i = 1,2,…,m. This transformation we call the splitting rule.
• We can replace a set of FD’s A1A2…An -> Bi for i = 1,2,…,m by the single FD A1A2…An -> B1B2…Bm. We call this transformation the combining rule.

Trivial Functional Dependencies

A constraint of any kind on a relation is said to be trivial if it holds for every instance of the relation, regardless of what other constraints are assumed.

title year -> title

If some of the attributes on the right side are also on the left, it can be simplifed by removing from the right side of an FD those attributes that appear on the left.

If title year -> title length, then title year -> length.

Computing the Closure of Attributes

{A1, A2, …, An}+

Example: AB -> C, BC -> AD, D -> E, CF -> B

The closure of {A,B}, that is {A,B}+, is {A,B,C,D,E}

Transitive Rule

If A->B and B->C, then A->C.