Why Snowflake?

Snowflake Schema

Snowflaking is a form of dimensional modeling in which a dimension is normalized by moving attributes with low cardinality (few distinct values) into separate dimension tables that relate to the main dimension table by using foreign keys.

Snowflakingcan be done in case of:

• Sparsely populated attributes, where most dimension member records have a NULL value for the attribute, are moved to a sub-dimension.
• 
  
• Low cardinality attributes that are queried independently.  For example, a product dimension may contain thousands of products, but only a handful of product types.  Moving the product type attribute to its own dimension table can improve performance when the product types are queried independently.
• 
  
• Attributes that are part of a hierarchy and are queried independently.  Examples include the year, quarter, and month attributes of a date hierarchy; and the country and state attributes of a geographic hierarchy.

Number of Centuries

Question: You have 2 tables as follows:

create table table1(player varchar2(10), ground_name varchar2(10), num_centuries number);

create table table2(ground_name varchar2(10), country varchar2(10));

Write a SQL to list the player names who have made centuries in every country

Solution:

select p.player

from

(select count(distinct country) cnt from table2) g,

(select player,count(distinct table2.country) cnt from table1,table2 where num_centuries>0

 and table1.ground_name=table2.ground_name

group by player) p

where g.cnt=p.cnt

Asymptotic analysis of Algorithms

The complexity of an algorithm function is usually described as a function of the number of inputs it receives.

e.g searching(linear search) a particular element in an array of n integers can be described as 

f(n) = 4 + 2n

However, in terms of the performance, we are generally interested in the terms which grow faster as n increases than the terms which grow slower as n increases. So we can drop constant '4' from the above function definition. Also the constant factor '2' can be dropped. Thus the function becomes

f(n) = n

This method of removing all factors and of "keeping the largest growing term" as described above is what we call asymptotic behavior. So the asymptotic behavior of f(n) = 2n + 4 is described by the function f(n) = n. In mathematical terms, it means that we are interested in the limit of function f as n tends to infinity (Mathematically, an aysmptote of a curve is line such that the distance between the curve and the line approaches zero as they tend to infinity. Asymptotic analysis is a method of describing limiting behavior)

So, if a program does not contain any loop can be describes as f(n)=1. This is because the number of instructions are fixed. If a program contains 1 loop (through 1 to n), it will be describes as f(n)=n.

Similarly a program with 2 loops(a loop with in a loop) will be f(n)=n*n

A program with 3 loops(a loop within a loop within a loop) will be f(n) = n*n*n

Big-Oh Notation: Its the notation which expresses the worst case complexity of an algorithm i.e the behaviour of an algorithm will never exceed a certain bound.

In the previous example, the complexity of an algorithm having 2 loops can be written as O(n*n). This means that this program's run time is never worse than n*n. It can be better but can never be worse. This gives a good idea about how fast this program runs.