Arjun Suresh

Cache Misses

January 28, 2019 by Arjun Suresh Leave a Comment

Understanding Cache Types

Three Types of Cache Misses

Compulsory Miss: First access to a memory block will cause a miss (unless mechanism like prefetching is used) and is termed Compulsory miss. Though this is termed compulsory miss this may get reduced by an increase in cache block size (which effectively reduces the number of memory blocks). This is also the misses that will occur even in a infinite size cache.
Capacity Miss: When a cache block is replaced due to lack of space and in future this block is again accessed, the corresponding cache miss is a Capacity miss. i.e., this miss could be avoided with a potentially larger cache. For the purpose of finding if a miss is a capacity miss we will assume the cache as fully-associative one.
Conflict Miss: This miss happens due to conflict and hence absent in a fully associative cache (with LRU replacement policy). When a cache goes from fully-associative to set-associative and then to direct-mapped, conflicts increases and the misses due to them are called conflict misses. To be precise, a conflict miss happens when a cache block is replaced due to a conflict and in future that same block is accessed again causing a cache miss.

Without explaining more lets directly go to some examples:

Consider a physical memory of $1\; MB$ size and a direct mapped cache of $8\; KB$ size with block size $32$ bytes. That is in one go $32$ bytes of data will be taken from/trasferred to main memory to/from cache. This means there are $1\;MB/8\; KB = 128$ blocks in main memory corresponding to a single cache block. Since $128$ memory blocks can map to a single cache entry, this means we need $\log_2 128 = 7$ tag bits.

Tag bits will be chosen from the higher order bits of main memory address so that adjacent main memory blocks won’t map to the same cache entry (useful in case of spatial locality). i.e., if main memory block $x$ gets mapped to a cache entry the next main memory block that maps to the same cache block will be after $X$ bytes where $X$ is the cache size (round robin fashion).
The main address bits get split into $3:$ $\text{tag }: \text{index }: \text{offset}$
For the above configuration we have $20$ bit physical address, $7$ bits of tag, $8$ bits for index ($2^{8} = 256$ entries in cache each of size 32 bytes = 8 KB) and $5$ bits of offset.

Lets see how the cache misses go.

Let there be a sequence of block accesses given by
$$2, 216, 100, 256, 2048, 728, 256, 216$$

Since physical memory is 1 MB we need 20 bits for byte addressing. Out of these 5 bits are taken by a cache block (of size 32 bytes). So, remaining 15 bits are used for block addressing (means the block address can range from 0 – 32767)

If instead of block address, memory addresses were given we have to divide by 32 (or remove the lower 5 bits) to get the block addresses

If values are in decimal consider dividing and if they are in hexa-decimal consider removing the lower bits

No. of blocks in cache $= 8\; KB / 32 B = 256$

Now, to find which cache block a memory block goes, we just have to do $\boxed{\mod 256}$ because the set/index bits of the cache are lower bits and tag bits are upper (as mentioned earlier for utilizing any spatial locality).

Thus $$\begin{array}{c|c} 2& 2\\216 & 216 \\ 100 & 100 \\ 256 & 0 \\2048 & 0 \\ 728 & 216 \\256 & 0 \\ 216 & 216\end{array}.$$

Now, lets classify the misses happened here:

$$\begin{array}{c|c|c} 2& 2 & \text{Compulsory Miss}\\216 & 216& \text{Compulsory Miss} \\ 100 & 100& \text{Compulsory Miss}\\ 256 & 0& \text{Compulsory Miss}\\2048 & 0& \text{Compulsory Miss}\\ 728 & 216& \text{Compulsory Miss}\\256 & 0& \text{Conflict Miss}\\ 216 & 216& \text{Conflict Miss}\end{array}.$$

Now, why are the first $6$ accesses “Compulsory Misses”?

Because they are all FIRST access to a cache block

Why are the last $2$ accesses “Conflict Misses”?

Because these blocks were once in cache and replaced due to a conflict

Why are there no capacity misses?

We have $256$ cache blocks and in the access sequence we accessed only $6$ unique memory blocks. A capacity miss is one which is caused due to shortage in cache size. This is the miss which will happen even if we assume the cache to be fully associative.

LR Parsing Part 4: SLR, CLR, LALR and Summary

January 24, 2019 by Arjun Suresh Leave a Comment

In the previous part, we saw

How to make LR(0) items
How to make DFA for recognizing viable prefixes and handles
How to build LR(0) parse table

In LR(0) parsing whenever there is an item $A \to \alpha \bullet$ $(\bullet$ at end and $A$ is not the new Start symbol) action in parsing table for the corresponding state is REDUCE for all terminals. The problem here is that, in this state, we cannot have a SHIFT action for any terminal. i.e., a CFG is LR(0) if

If $A \to \gamma \bullet$ is in a configurating set $(A$ is not the start symbol), no other item $B \to \alpha \bullet x \beta$ is in the set (Otherwise we will get SHIFT-REDUCE conflict as shown above)
If $A \to \alpha \bullet$ is in a configurating set, $B \to \beta \bullet$ should not be there in the same set. Otherwise we will have REDUCE-REDUCE conflist (which production to reduce with?)
The 2 rules above means there can be maximum one complete item in any set

The above restrictions rule most of the CFGs to be not LR(0) and hence LR(0) parsing is less useful. How can we reduce the conflicts here?

Instead of having a REDUCE move for all terminals, we can have it only for FOLLOW(A), where A is the LHS of the production used for reduction. This rule is straightforward as based on the definition of FOLLOW set, only those symbols can any way come after the given non-terminal (in any sentential form). By doing so, we do not add any extra overhead (other than finding the FOLLOW set and use one look-ahead symbol to check if in the FOLLOW set) and we can reduce SHIFT-REDUCE and REDUCE-REDUCE conflicts.
This parser now becomes Simple LR(1) or SLR(1) parser.
The only change in the Parsing Rule as compared to LR(0) parsing is
1. If there is a complete item $A \to \alpha \bullet$ in set $i$, set ACTION[i, a] to REDUCE $A \to \alpha$ for all $a$ in FOLLOW(A) $(A$ is not the start symbol)
SLR(1) parser does allow both SHIFT and REDUCE items to be in same state

Lets now see the condition for a grammar to be SLR(1)

If in a state we have items $A \to \alpha \bullet$ and $A \to \beta \bullet$ $FOLLOW(\alpha)$ and $FOLLOW(\beta)$ must be disjoint
If in a state we have items $A \to \gamma \bullet$ and $A \to \alpha \bullet x \beta$ $(x$ is a terminal), then $FOLLOW(A)$ should not contain $x.$

Problem of SLR(1)

It reduced conflicts by using FOLLOW set for Reduction
But FOLLOW set is not enough
1. FOLLOW set is based on the entire grammar
2. But in any state in the parser, the reduction should be based on only the visited states (entire stack content, not just the stack top)
3. This will make some of the entries in the FOLLOW set invalid for reduction
i.e., if we prune the FOLLOW set we can get less conflicts and a better parser
Canonical LR(1) or CLR(1) or simply LR(1) is such a one

CLR(1)

As detailed in above section, the main difference of CLR(1) as compared to SLR(1) is in having extra information for deciding REDUCE moves as compared to using only the FOLLOW set.

CLR(1) stores extra information in each state
The extra information is the set of valid terminals which can cause a REDUCE move
This set of valid terminals will be a subset of the FOLLOW(A), where $A$ is the LHS of the production used for reduction
Storing extra information can lead to more number of states in CLR(1) as compared to SLR(1)
An LR(1) item is of the form $A \to X_1X_2 \ldots X_i \bullet X_{i+1}\ldots X_j , a/b\dots$
1. This means states corresponding to $X_1 X_2 \ldots X_i$ is on the stack
2. States corresponding to X_{i+1}\ldots X_j$ is expected to be coming to stack
3. After that we REDUCE but only if the lookahead token is one among $a/b/\ldots$ which is the set of valid terminals including $\$$ (subset of FOLLOW(A))

Closure of a state in LR(1) is found by repeating the following until no more production can be added:

For each configuration $[A \to \alpha •B \beta, a]$ in $I,$ for each production $B \to w$ in $G’,$ and for each terminal $b$ in $FIRST(\beta a)$ such that $[B \to •w, b]$ is not in $I$: add $[B –> •w, b]$ to $I.$ $a$ in $(FIRST(\beta a)$ becomes relevant when $\beta$ becomes empty.

To understand how LR(1) parsing works and how the LR(1) items differ from LR(0) items lets take the example from Ullman:

$S’ \to S$
$S \to XX$
$X \to aX$
$X \to b$

The SLR and LR configurating sets are shown below. The number of states in LR increases to $10$ from $7$ in the SLR. This is due to the difference in the lookahead which necessitized creation of new states.

$$\begin{array}{c|c}
\underline{\text{SLR Configurating Sets}} &\underline{\text{LR Configurating Sets}}\\
\boxed{S’\to .S\\S \to .XX\\ X \to .aX \\X \to .b} & \boxed{S’\to .S, \$\\S \to .XX, \$\\ X \to .aX, a/ b \\X \to .b, a/ b} \\
\boxed{S’\to S.} & \boxed{S’\to S., \$}\\
\boxed{S \to X.X\\ X \to .aX \\X \to .b} & \boxed{S \to X.X, \$\\ X \to .aX, \$ \\X \to .b, \$} \\
\boxed{S \to XX.}& \boxed{S \to XX., \$}\\
\boxed{ X \to a.X\\
X \to .aX \\X \to .b} & \boxed{ X \to a.X,\$\\
X \to .aX,\$ \\X \to .b,\$} \boxed{ X \to a.X,a/b\\
X \to .aX,a/b \\X \to .b,a/b}\\
\boxed{X \to aX.} &\boxed{X \to aX., \$} \boxed{X \to aX., a/b}\\
\boxed{X \to b.}& \boxed{X \to b.,\$} \boxed{X \to b.,a/b} \end{array} $$

After the configurating sets are done, working of LR parser follows the approach of SLR or LR(0) one. You can see the systematic approach here.

Now, we can see the formal requirement for a grammar to be LR(1)

A grammar is LR(1) if the following two conditions are satisfied for each configurating set:

If $[A \to \alpha \bullet x \beta, a],$ $x$ a terminal, is in a set, then there should be no item of the form $[B \to \gamma \bullet, x]$ in the same set. (Shift-Reduce conflicts)
$[A \to \alpha \bullet, a]$ and $[B \to \beta \bullet, a].$ must not be in a set. (Lookaheads for all complete items must be disjoint).
(Reduce-Reduce conflicts)

So, we have seen LR(1) parser which reduces conflicts from SLR(1) parsing but at the expense of more number of states. As seen in the example, this increase in states is due to the “lookahead” symbols being part of the configuration item.

What happens if we merge the states having same items but different lookaheads?
1. We get the same number of states as in SLR(1)
2. We still avoid all Shift-Reduce conflicts which are avoided by LR(1)
3. We may have more REduce-Reduce conflicts as compared to LR(1) as we are having imprecise lookaheads
This is exactly what is LALR(1) parser.
You mostly won’t need to know more about it but still if interested can READ THIS

PS: So that completed the parsing notes for GATE 2019. Will be having a small Test on Parsing coming up tomorrow.

923 total views, 6 views today

LR Parsing Part 3: LR(0) items and LR(0) parsing

January 23, 2019 by Arjun Suresh 1 Comment

Just revising on the previous part we have the following relation. Here $Lang$ denote the set of languages defined by the given set of grammars.

$LL(0) \subset LL(1) \subset LL(2) \dots LL(k) \subset LL(k+1)\dots$
$Lang(LL(0)) \subset Lang(LL(1)) \subset Lang(LL(2)) \dots Lang(LL(k)) \subset Lang(LL(k+1))\dots$
$LR(0) \subset LR(1) \subset LR(2) \dots LR(k) \subset LR(k+1)\dots$
$Lang(LR(0)) \subset Lang(LR(1)) = Lang(LR(2)) \dots Lang(LR(k)) = Lang(LR(k+1))\dots$ ($Lang(LR(0)$ is DCFL with prefix property and $Lang(LR(k)); k \geq 1$ is DCFL (with or without prefix property))
$Lang(LR(0)\$) = Lang(LR(1)) = Lang(LR(2)) \dots Lang(LR(k)) = Lang(LR(k+1))\dots$ ($Lang(LR(0)\$$ is DCFL as when we add an end delimiter no string becomes a prefix of another)

Coming to LR parsing we have $3$ main types:

Simple LR or SLR(1) – Can parse a superset of LR(0) grammars but a proper subset of LR(1) grammars
LALR – Can parse a superset of grammars that can be parsed by SLR(1) parsers but a proper subset of LR(1) grammars
LR(1) or Canonical LR(1) – Can parse any LR(1) grammar

Now we will see more about these:

LR(0) Parser

LR(0) parser is quite uncommon because it is quite restrictive (not in terms of the language but interms of the grammars it can parse). By adding an end delimiter we can remove the prefix-free restriction of $LR(0)$ set of languages (when an end delimiter is added, no string becomes a prefix of any other string) but even then it does not allow $\epsilon$ production for a symbol if that symbol is dervining anything else. Still $LR(0)$ parser is the basic LR parser and will help us understand how LR parsers work in general. SLR(1), CLR(1) and LALR(1) are all extensions to $LR(0)$ parser.

Lets consider a grammar

$E’ \to E$
$E \to E + T $
$E \to T $
$T \to (E) $
$T \to id$

Now, when we parse a string say “id + id”, at each step we will either Shift or Reduce. For example:

$id + id$ (Shift “id”)
$\quad => T + id$ Reduce $(T \to id)$
$\quad => E + id$ Reduce $(T \to E)$ Shift “+”
$\quad=> E + T$ Reduce $(T \to id)$
$\quad=> E$ Reduce $(E \to E + T)$
$\quad=> E’$ Reduce $(E’ \to E)$

Now, to get these steps programmatically lets construct a DFA. The states of the DFA are the LR(0) items and they are made from the Grammar productions. The formal procedure is given here but the as you can see below, the construction is pretty intuitive. For the start production add a “$\bullet$” to the leftmost point on RHS. Then, if a non-terminal follows, add its production too to the item. Rest of the procedure can even be inferred from the below diagram.

As you can see in the diagram

the states of the DFA are the LR(0) items
the transitions are for each grammar symbol (both terminals and non-terminals)
If we consider all states as accepting, the DFA above is accepting the set of all viable prefixes
Any item with a $\bullet$ at end of the production is accepting handles.

Now, how we will use this DFA to parse a given string? Say “id+id”. It is not the case that a given string will take the DFA to accepting state – because the given grammar is context-free and not necessarily regular. So, we will need something EXTRA which is a stack. Lets see how this STACK helps.

We always start in the $I_0$ state. Since “id” comes in the input we
- GOTO $I_4$ (see DFA)
- PUSH $I_4.$ (Pushing on Stack which is used later for coming back when we have a REDUCE move)
- SHIFT “id”.
- Stack becomes $I_0 I_4$
In $I_4$ $\bullet$ is at the end of the production and so we
- REDUCE by $T \to id.$
  $\bullet$ is at end of a production in $I_4$. So, in the DFA we go back (going back requires a stack) one step (POP one item from stack which is $I_4$ and we get to $I_0$ (since RHS of production has one symbol we POP only one symbol from stack)
- Since we did a REDUCE, we will move to the state given by $GOTO (I_0, T)$ $(T$ is the LHS of the REDUCE move) which is $I_2$ (the transition on $T$ from $I_0$ is $I_2.$)
- Stack is $I_0 I_2$
Again in $I_2$ we have a $\bullet$ at end of the production and so we reduce by $E \to T$ and go back to $I_0$ and then to $I_1$ as the transition on $E$ from $I_0$ is $I_1.$
- Stack goes to $I_0 I_1$
PS: In $I_1$ $E’$ being the start symbol, $E’ \to E \bullet$ will cause a reduce move only for the end symbol $\$.$ And so there is no Shift-Reduce conflict here.
- Stack is $I_0I_1$ only
Next input symbol is “+” and so we SHIFT “+” and move to $I_5.$
- Stack is $I_0I_1I_5$
Next input symbol is “id” and we go to $I_4$ by shifting “id”.
- Stack is $I_0I_1I_5I_4$
In $I_4$ $\bullet$ is at the end of the production and so we reduce by $T \to id.$
We come back to $I_5$ and on $T$ (the LHS of production used for Reduce) we move to $I_8.$
- Stack is $I_0I_1I_5I_8$
In $I_8$ $\bullet$ is at the end of the production $E \to E + T \bullet$ and so we reduce by $E \to E+ T \bullet $
- Here the RHS of the production HAS 3 symbols and so we need to pop $3$ states from the stack (basically traverse back 3 steps in the DFA along the path we came)
- Stack becomes $I_0$
- Since we reduced by $E \to E + T$ we have to go to $GOTO(I_0, E)$ which is $I_1$
- Stack becomes $I_0I_1$
In $I_1$ “$\$$” comes and we reduce by the Start production $E’ \to E$ and that signals “Accept”.
That’s it.

If this part is thorough, the next $3$ parsers $SLR(1), CLR(1)$ and $LALR(1)$ will be quite straightforward.

685 total views, no views today

LR Parsing Part 2: Language of LL and LR grammars

January 3, 2019 by Arjun Suresh Leave a Comment

In the previous part we talked about viable prefixes and handles. Today we will do a bit of background to ensure your concepts are clear.

When we started LR parsing I assumed that you know LL parsing. LL means scan input from left to right and do a left-most derivation. This is less powerful than LR – why?

Assume for simplicity that we are talking about LL(1) and LR(1) where the ‘1’ refers to the lookahead- that is at anytime we look at the ‘next ONE’ input character to decide the parser action.
In LL(1) we see the first symbol of the input and see the production to apply. So, if there is two productions with the same ‘first’ symbol as in the input parser gets a conflict and fails.
In LR(1) we see the input from left till we get a handle. After this, we see one more lookahead symbol and determine the parser action. i.e., the parser has MORE information to decide its action than in LL(1) and this makes it more powerful than LL(1). More powerful means, any grammar that can be parsed by LL(1) can also be parsed by LR(1)
This holds in general case too – for any $k$, LL(k) set of grammars is a PROPER subset of LR(k) set of grammars

Now, when we say “power of a parser” it is with respect to the GRAMMARS it can parse- not the language where as when we say “power of a grammar” it is with respect to the languages it can generate. So, what will be the language of LL(1) – that is the languages which can be generated by the set of all LL(1) grammars?

Actually the power of LL(k) grammar strictly increases with an increase in ‘k’. i.e., language of LL(k) is a strict subset of the langauge of LL(k+1).

What about LR(k)?

Power of LR(0) grammar is lower than power of LR(1).

Language of LR(0) (set of all LR(0) grammars) is same as DCFL having prefix property or the set of languages accepted by a DPDA with empty stack – this is neither a super set nor a subset of the set of regular languages.

Language of LR(1) (set of all LR(1) grammars) is same as DCFL
i.e., Language of LR(0) $\subset$ Language of LR(1) = Language of LR(2) = Language of LR(k), k > 0.

Since any LL(k) grammar is also an LR(k) grammar, language of any LL(k) grammar is guaranteed to be a DCFL. But since language of LL(k) is a strict subset of the langauge of LL(k+1), for any finite $k$, there exist SOME DCFL which cannot be generated by ANY LL(k) grammar.

For sake of completeness we can see the languages of LL(0) and LL(1).

0 in LL(0) means the parser must be able to determine the production without seeing any lookahead symbol. This basically means there cannot be multiple choices for any non-terminal. But if there are no choices, the grammar can only generate a single string or no string. So, the language of LL(0) is the set of all single string languages and also the empty language.
LL(1) grammars have more power but as we saw earlier it cannot generate all DCFLs. But can it at least generate all regular languages?
- It does. Every regular language has a right liner grammar (also a left linear one) and this is LL(1)

So, now we can come back to LR parsing. I wont be discussing LL or Top down parsing. For that please see here. But we can see the definitions of FIRST and FOLLOW which are useful even for LR parsing.

(Greek letters means a sequence of terminals or non-terminals)

$FIRST(\alpha)$ is the set of terminals that begins strings derivable from $\alpha$ ($\alpha$ itself can be starting with a terminal). (How does it help in parsing?)

$FOLLOW(A)$ (see capital English alphabet A, so a single non-terminal only) is the set of terminals that can appear immediately to the right of $A$ in some sentential form. (So, should $FOLLOW(S)$ have $\$$ – the end marker for string?)

We can now see the condition for a grammar to be LL(1). A grammar $G$ is LL(1) only if

$G$ is unambiguous
$G$ is not left-recursive
If there is a production $A \to \alpha \mid \beta,$ then
1. $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$ Otherwise parser gets confused which production to use
2. If $FIRST(\alpha)$ contains $\epsilon$, $FIRST(\beta)$ should not contain $\epsilon$ (same reason as above)
3. If $FIRST(\alpha)$ contains $\epsilon$, $FIRST(\beta) \cap FOLLOW(\alpha) = \emptyset$ (again same reason as above)

SLR(1), LALR and CLR parsing to be continued in next part…

1,659 total views, 1 views today

Viable Prefixes and Handle in LR Parsing

January 1, 2019 by Arjun Suresh 1 Comment

Well lets start from the basic of Bottom up Parsing

Consider the grammar

$S \to XX$
$X \to aX \mid b$

Now, consider a string in $L(S)$ say aabb. We can parse it as follows by left most derivation – replacing the left most non-terminal in each step, or right most derivation – replacing the rightmost non-terminal in each step.

$S \to XX$
$\quad \to aX X$
$\quad \to aaXX$
$\quad \to aabX$
$\quad \to aabb$

$S \to XX$
$\quad \to Xb$
$\quad \to aXb$
$\quad \to aaXb$
$\quad \to aabb$

Here, the rightmost-derivation is used in bottom-up parsing. We will soon come back to it.

Any string derivable from the start symbol is a sentential form — it becomes a sentence if it contains only terminals

A sentential form that occurs in the leftmost derivation of some sentence is called left-sentential form

A sentential form that occurs in the rightmost derivation of some sentence is called right-sentential form

Consider the string aabb again. We will see a method to parse this:

Scan the input from left to right and see if any substring matches the RHS of any production. If so, replace that substring by the LHS of the production.

So, for “aabb” we do as follows

‘a’ “abb” – No RHS matches ‘a’
‘aa’ “bb” – No RHS matches ‘a’ or ‘aa’
‘aab’ “b” – RHS of $X \to b$ matches ‘b’ (first b from left) and so we write as
aaXb
‘aaX’ “b” – RHS of $X \to aX$ matches “aX” and so we write as
aXb – Again RHS of $X \to aX$ matches “aX” and we get
Xb – RHS of $X \to b$ matches “b” and we get
XX – RHS of $S \to XX$ matches XX and we get
S – the start symbol.

Now what we did here is nothing but a bottom-up parsing. Bottom-up because we started from the string and not from the grammar. Here, we applied a sequence of reductions, which are as follows:

$aabb \to aaXb \to aXb \to Xb \to XX \to S$

If we go up and see the Rightmost derivation of the string “aabb”, what we got is the same but in REVERSE order. i.e., our bottom up parsing is doing reverse of the RIGHTMOST derivation. So, we can call it an $LR$ parser – $L$ for scanning the input from Left side and $R$ for doing a Rightmost derivation.

In our parsing we substituted the RHS of a production at each step. This substituted “substring” is called a HANDLE and are shown in BOLD below.

aabb $\to$ aaXb $\to$ aXb $\to$ Xb $\to$ XX $\to$ S

Formally a handle is defined as (Greek letters used to denote a string of terminals and non-terminals)

A handle of a right sentential form ‘$\gamma$’ $(\gamma = \alpha \delta \beta$) is a production $E \to \delta$ and a position in $\gamma$ where $\delta$ can be found and substituted by $E$ to get the previous step in the right most derivation of $\gamma$ — previous and not “next” because we are doing rightmost derivation in REVERSE. Handle can be given as a production or just the RHS of a production.

The handle is not necessarily starting from the left most position as clear from the above example. There is importance to the input string which occurs to the left of the handle. For example for the handles of “aabb”, we can have the following set of prefixes

aabb	$\{a, aa, aab\}$
aaXb	$\{a, aa, aaX\}$
aXb	$\{a, aX\}$
Xb	$\{X, Xb\}$
XX	$\{X, XX\}$

These set of prefixes are called Viable Prefixes. Formally

Viable prefixes are the prefixes of right sentential forms that do not extend beyond the end of its handle.

i.e., a viable prefix either has no handle or just one possible handle on the extreme RIGHT which can be reduced.

We will see later that viable prefixes can also be defined as the set of prefixes of the right-sentential form that can appear on the stack of a shift-reduce parser. Also, the set of all viable prefixes of a context-free language is a REGULAR LANGUAGE. i.e., viable prefixes can be recognized by using a FINITE AUTOMATA. Using this FINITE AUTOMATA and a stack we get the power of a Push Down Automata and that is how we can parse context-free languages.

In the next part we will see how to construct the above FINITE AUTOMATA and how our stack works for different LR parsers.

Reference: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/100%20Bottom-Up%20Parsing.pdf

2,369 total views, 17 views today

Demystifying Database Normalization

October 20, 2018 by Arjun Suresh Leave a Comment

This will be a short and concise material to understand and check your understanding of Normal forms in databases. I assume you have already read about them from standard text books like Silberschatz or Navathe.

Functional Dependency – We say an attribute set (a single attribute or a group of attributes) $A$ determines an attribute set $B$ if whenever $A$ repeats its value, $B$ also repeats its value. Any unique attribute determines every other attribute.

Super Key – An attribute set which determines every other attributes

Candidate Key – A minimal super key becomes a Candidate key. i.e., if we remove any attribute from a candidate key, it should no longer be a candidate key

Primary Key – Any one candidate key is selected as a Primary key so that the table can have only one primary key but multiple candidate keys may be present (we will see its use in Table indexing)

Prime attribute: An attribute that is part of some candidate key is a prime attribute


Student ID	Name	Phone	Email
CS_001	Ravi	9995677893	email1@abc.com
CS_002	Manya	9992347689	[email protected]
CS_003	Ravi	9456792001	[email protected]

Here, we are having a table which is an instance of the Relation Student (Student ID, Name, Phone, Email) – the same relation can have other table instances too. We can see that Name value is repeating and so cannot be the key. Student ID, Phone and Email are Unique values and all are candidate keys (we can say they are candidate keys for the given table; but to say the same for Student relation we must be sure of all possible instances of it; i.e., there can be another Student table with $2$ students having same Phone number or email. Assuming all instances of Student relation are like the given one we have the following keys:

Candidate Keys: Student ID, Phone, Email
Primary Key: Any one of {Student ID, Phone, Email}
Super Keys: {Student ID}, {Phone}, {Email}, {Student ID, Name}, {Phone, Name}, {Email, Name}, {Student ID, Phone}, {Phone, Email}, {Email, Student ID}, {Student ID, Name, Phone}, {Phone, Name, Email}, {Email, Name, Student ID}, {Email, Phone, Student ID} {Email, Name, Student ID, Phone}

Now, we will see how we can ensure a given relation satisfies certain normal forms. The higher the normal form, better the relation is in terms of redundancies and removal of anomalies. But practically to ensure higher normal forms we need to decompose the relations to smaller ones which can have performance issues. Anyway that is not our concern here and we see how we can decompose the relations to ensure higher normal forms. While we decompose a relation we must ensure

Losslessness – A decomposition of a relation $R$ into $R_1$ and $R_2$ is not lossy if $R_1 \cap R_2$ is a key of either $R_1$ or $R_2.$

It is also ideal to keep dependencies. i.e., while decomposing a relation it is ideal we can ensure the dependencies without a need to JOIN the decomposed relations. But this is not a strict requirement like losslessness.

1NF

1NF does not allow multi-valued attributes. i.e., every attribute in a row must have a single value. (An attribute is free to have multiple components like an Address attribute having House No., Street Name etc.). For example, in the below table “Phone” attribute is violating this.

For the below relation assume that only a single course can start on any day and all enrolments must be on that day. i.e., Enroll Date $\to$ Course ID is a FD as well as Course ID $\to$ enroll Date. The candidate keys for the below relation are {SID, Course ID} and {SID, Enroll Date}

SID	Course ID	Enroll Date	SNAME	Phone	Marks	Grade
100	1	31/7/2018	DONY	7474749892, 9994567321	80	A
100	2	1/8/2018	DONY	7474749892, 9994567321	70	B
101	1	31/7/2018	JOSE	7856400234	85	A
101	2	1/8/2018	JOSE	7856400234	85	A

To make the above table to 1NF, we can do as follows:

SID	Course ID	Enroll Date	SNAME	Phone	Marks	Grade
100	1	31/7/2018	DONY	7474749892	80	A
100	1	31/7/2018	DONY	9994567321	80	A
100	2	1/8/2018	DONY	7474749892	70	B
100	2	1/8/2018	DONY	9994567321	70	B
101	1	31/7/2018	JOSE	7856400234	85	A
101	2	1/8/2018	JOSE	7856400234	85	A

i.e., we duplicated ROWS to remove multi-value for attribute Phone and thus make the relation in 1NF.

2NF

Second Normal Form requires a relation to be in 1NF and for every functional dependency $A \to B,$ we should not have $C \to B$ where $C \subset A$ and $B$ is a non-prime attribute. i.e., there should not be any partial functional dependency ($A\to B$ is a partial FD, if a proper subset of $A$ determines $B$) for any non-prime attribute. Partial functional dependency means an attribute being determined by a proper subset of some candidate key.

A necessary (but not sufficient) condition for a relation to be in 1NF but not in 2NF is that it should have at least one candidate key with multiple attributes

SID	Course ID	Enroll Date	Marks	Grade
100	1	31/7/2018	80	A
100	1	31/7/2018	80	A
100	2	1/8/2018	70	B
100	2	1/8/2018	70	B
101	1	31/7/2018	85	A
101	2	1/8/2018	85	A

SID	SNAME	Phone
100	DONY	7474749892
100	DONY	9994567321
100	DONY	7474749892
100	DONY	9994567321
101	JOSE	7856400234
101	JOSE	9994567321

3NF

A relation is in 3NF if it is in 2NF and no non-prime attribute should be determined by anything but a super key (no transitive dependency) . In the first relation above we have a FD, Marks $\to$ Grade and Grade is a non-key attribute and Marks is not a super key. So, this violates 3NF. To make this relation into 3NF, we can decompose the relation as follows:

SID	Course ID	Enroll Date	Marks
100	1	31/7/2018	80
100	1	31/7/2018	80
100	2	1/8/2018	70
100	2	1/8/2018	70
101	1	31/7/2018	85
101	2	1/8/2018	85

Marks	Grade
80	A
80	A
70	B
70	B
85	A
85	A

A necessary (but not sufficient) condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute or a set containing a non-prime attribute

BCNF

A relation is in BCNF, if for every non-trivial functional dependency $A \to B,$ $A$ is a super key. It basically removes the “non-prime attribute” restriction in the 3NF definition thus ensuring that every attribute must be determined only by a super key. The above relation is not in BCNF because Enroll Date determines Course ID (also vice versa) and Enroll Date is not a super key. In order to make the relation to BCNF, we need to split them as follows:

SID	Course ID	Marks
100	1	80
100	1	80
100	2	70
100	2	70
101	1	85
101	2	85

Course ID	Enroll Date
1	31/7/2018
1	31/7/2018
2	1/8/2018
2	1/8/2018
1	31/7/2018
2	1/8/2018

A necessary (but not sufficient) condition for a relation to be in 3NF but not in BCNF is that it should have overlapping candidate keys – two candidate keys of two or more attributes and at least one common attribute

The proof for the above statement can be given as follows:

If a relation is in 3NF and not in BCNF, then there must be a non-trivial FD $A \to B,$ where $B$ is a prime attribute and $A$ is not a super key (assume $A$ is the minimal attribute set which determines $B$). This means $B$ is not a super key as otherwise $A$ must also be a super key. But since, $A$ is a prime attribute, for some non-empty set of attributes $Y,$ $BY$ is a candidate key. Since $A \to B,$ and $A$ is assumed to be minimal, this means $AY$ is also a candidate key. Thus we got two candidate keys $AY$ and $BY$ and $Y$ is common.

Till 3NF, we can always ensure a lossless and dependency preserving decomposition. But for BCNF, this may not be possible always and so we ensure lossless property at the expense of losing some dependencies.