Finding Islands of Data

"But the universe, as a collection of finite things, presents itself as a kind of island situated in a pure vacuity to which time, regarded as a series of mutually exclusive moments, is nothing and does nothing."

-- Muhammad Iqbal

When I first started using SQL Server 2008 one of the most interesting things I stumbled across was the OVER clause.  At first when I started using I enjoyed that I could use aggregate functions without the need for a GROUP BY clause, in fact I aggregate over different sets of data in the same SELECT statement!

Having grown more use to the idea of thinking in sets, I now see OVER clause and windowing functions in general are very valuable tools in the SQL tool belt.

Using the following:

CREATE TABLE #t1 (
  col1 int NOT NULL
);
GO

INSERT INTO #t1
  VALUES (2),(3),(4),(9),(11),(12),(13),(14),(22),(23),(45),(46);
GO

We create a table with one column and some integer values.

With just this simple data set we can demonstrate how islands of day can be found.  What is an island of data?  An island of data is simply a gap in the data.  Say you get a data feed of security prices, but some of the data is incomplete for some days (maybe a security is thinly traded or maybe whomever you are getting the feed from has some issues).  These gaps in the data form what is called data islands.

Looking at our simple data we can see a few data islands.

col1
2
3
4
9
11
12
13
14
22
23
45
46

The different data islands have been highlighted in different colors.  It would be nice if the data was a way that the different colors had different group identifiers so that we do a GROUP BY (or something similar) on the identifier.  As Polya shows us in How to Solve It, if we can solve an auxiliary problem perhaps we can solve this one.

If we use the ROW_NUMBER window function and ORDER BY the value in col1 we would get the following.

SELECT col1, ROW_NUMBER() OVER(ORDER BY col1) AS rowid
  FROM #t1;
GO

col1 rowid
2 1
3 2
4 3
9 4
11 5
12 6
13 7
14 8
22 9
23 10
45 11
46 12

All we did was simply return the ROW_NUMBER assigning the number based on the values in col1.  Thus 2 is assigned 1 since it is the lowest value, 9 is assigned 4 since there are three values lower than it, 46 is assigned 12 since all eleven other values are lower than it, and so on.  Each ROW_NUMBER is assigned in relation to all the other values it is based on, in this case the number is assigned based on the value in col1.

If we look closer we will find that the difference between the rowid and col1 holds constant for the whole group meaning that we can simple subtract the rowid and col1 to get a value that we can GROUP BY as an identifier.

SELECT col1, col1 - ROW_NUMBER() OVER(ORDER BY col1) AS groupid
  FROM #t1;
GO

col1 groupid
2 1
3 1
4 1
9 5
11 6
12 6
13 6
14 6
22 13
23 13
45 34
46 34

Now we have our identifier to GROUP BY we can do the following to get the range of each island of data.

SELECT DISTINCT
   MIN(col1) OVER(PARTITION BY groupid) AS start_range
  ,MAX(col1) OVER(PARTITION BY groupid) AS end_range
  FROM (
    SELECT 
       col1
      ,col1 - ROW_NUMBER() OVER(ORDER BY col1) AS groupid
      FROM #t1
  ) AS x;
GO

start_range	end_range
2	4
9	9
11	14
22	23
45	46

The PARTITION BY in the OVER clause is very similar to a GROUP BY, the difference being that the PARTITION BY takes the value in the current row and looks at all the related values in the current window, or simply in the case where col1 is equal to 3 the MIN ans MAX are found for all of the col1's with the related groupid of 1, which would be the value 2 ans 4.  Since the OVER clause is looked at for each row of data we need to use a DISTINCT to remove the duplicates.

There you have it, you can find islands of data by using simple windowing functions.

I've placed this code on SQL Fiddle here.

On Immutablity

"And yet in our world everybody thinks of changing humanity, but nobody thinks of changing himself."
Three Methods of Reform by Leo Tolstoy

"When Moses was alive, these pyramids were a thousand years old. Here began the history of architecture. Here people learned to measure time by a calendar, to plot the stars by astronomy and chart the earth by geometry. And here they developed that most awesome of all ideas - the idea of eternity."
Walter Cronkite

In my best Yogi Berra, eternity is a rather long time, even longer than now.  One finds very quickly when learning about functional programming the idea of immutability.  In functional programming one does not find variables in the true since of the word, instead one hears of binding to a value or value functions.  Why is this?  What does this have to do with immutability?

Much like how Immanuel Kant's categorical imperative forbids lying, functional programming forbids mutating values.  This means you cannot say that foo is equal to 5 at one point in time and later on say that now foo is equal to 6.  You have just lied, which one is it, 5 or 6?  Even worst is it now 7?  Immutability solves this be not allowing you to change the value of foo once you say that foo is equal to 5.

One may at this time being saying, "How is immutability useful?  I have been programming for X number of years and that whole time I have been using variables and nothing bad as been happen!"  If we travel back in time a few decades, we can hear a similar argument about GOTO statements.

Why immutability now?  Well, as Uncle Bob points out in his first post about functional programming there is a tide wave coming.  Why?  Hardware designers have chosen to increase the number of processors instead of increasing the speed of a single processor.  What does this mean?  If us programmers want to be able to make use of these ever increasing number of processors, we'll need to be able to make our programs work in multi-core environments!

The easiest way to work in a multi-core environment would be to have functionality that does not have any side effects and thus could be reordered.  Hmmm, how does one do that?  Well if I had data structures that could not be mutated then those untrustworthy functions would not be able to produce side effects.  Hmmm, this sounds like immutability.

So what does immutability look like in F#?


> let foo = 5;;

val foo : int = 5

> foo <- 6="6" font="font">

  foo <- 6="6" font="font">
  ^^^^^^^^

/home/mike/stdin(2,1): error FS0027: This value is not mutable


We cannot even reassign foo to the value of 6!  That my friends is immutability.

Sieve of Eratosthenes in F#

"God may have not play dice with the universe, but something strange is going on with the prime numbers."
Paul Erdős

"Mathematicians  have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate."
Leonhard Euler

Before Caesar, before one anno domini, before the internet, there was the library of Alexander and  Eratosthenes.  Eratosthenes of Cyrene was the third librarian of the library of Alexander.  Among other things, he was the first person to calculate the circumference and tilt of the Earth!

If that was not enough, Eratosthenes summoned a simple prime sieve to find prime numbers.  The Sieve of Eratosthenes works in the following way:

1. list integers from 2 to N
2. initially mark 2 as prime (it is prime)
3. cross off all of the integers which are increments of the marked number apart
4. take the next non-crossed off number and mark it as prime
5. repeat step 3 until all numbers are either crossed off or marked as prime

Visually here is what the sieve looks like:

skip to the end

We mark the prime numbers with green and those that have been crossed off with red.

What would the Sieve of Eratosthenes look like in F#?  Well we would want to have a list created from 2 to N, then a function which would take the head of the list and filter out the numbers from the list that are divisible by the head (I know this is not exactly the same as what is above) and loop back around to the top of the function with the new filtered list.


> let sieve n =
-   let rec aux list =      
-     match list with
-     | [] -> []
-     | hd :: tl -> hd :: aux (list |> List.filter (fun x -> x % hd <> 0) )
-   aux [2 .. n]
- ;;

val sieve : int -> int list

Let's test it (I'll blog about using FsUnit at a latter date, so we'll just use poking around testing for now).


> sieve 3;;
val it : int list = [2; 3]
> sieve 11;;
val it : int list = [2; 3; 5; 7; 11]
> sieve 100;;
val it : int list =
  [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97]

> sieve 2;;  

val it : int list = [2]

> sieve 1;;

val it : int list = []

Looks like it works.

Using SQL Server's sp_MSforeachtable

If you just want the answer, here it is:

use MyDatabase

exec sp_MSforeachtable

  @command1 = N'PRINT ''?''',

  @whereand = N'AND o.name LIKE ''T_TablesWeWant_%'''

Another example (WHICH WILL DROP TABLES!!!!)

use MyDatabase

exec sp_MSforeachtable

  @command1 = N'DROP TABLE ?',

  @whereand = N'AND o.name LIKE ''T_TablesWeWantToDrop_%'''

Actual context

The most well documented undocumented stored procedure in SQL Server would have to be the two foreach stored procedures  sp_MSforeachdb and sp_MSforeachtable.

Being a lazy programmer who is currently working with a vended product that highly leverages SQL Server for it functionality, I did not want to physically go into each table in the tool to add the "hook" columns the tool needs to add to each table that it uses.  Instead I would much rather script out adding in the "hook" columns.  As one would assume the vendor did not have a script for this, much like learning that people in Columbus' time did not believe that the Earth was flat.

Luckily knowing that SQL Server had a few foreach stored procs for just this kind of scripting, Similar to von Bellingshausen, I hit the Google searching high and low.  I came across a very good write up at Database Journal on how sp_MSforeachtable sings.  It even included examples doing things similar to what I was looking to do.

I soon found that sp_MSforeachtable has an argument for commands (@command1) and another for filtering the tables that the commands would run against (@whereand).

I did the following quick test to see if I understood stored proc correctly (with some names changed and details left out):

use MyDatabase

exec sp_MSforeachtable

  @command1 = N'PRINT ''?''',

  @whereand = N'AND name LIKE ''T_TablesWeWant_%'''

This gave the following output:

Msg 209, Level 16, State 1, Line 1

Ambiguous column name 'name'.

Seeing that the write up was from 2004, I assumed that something most likely changed in SQL Server 2012.  One of the difficulties related to using undocumented features, in fact that term is used as an euphemism for software bugs.

I figured I would use the force and read the source (note ... is code I do not think is important for the issue at hand, please who knows I maybe violating some term of contract if I show the whole thing).

exec sp_helptext 'sp_MSforeachtable'

create proc sys.sp_MSforeachtable

   @command1 nvarchar(2000), 

   @replacechar nchar(1) = N'?',

   @command2 nvarchar(2000) = null,

   @command3 nvarchar(2000) = null,

   @whereand nvarchar(2000) = null,

   @precommand nvarchar(2000) = null,

   @postcommand nvarchar(2000) = null

as

         ...

          /* Create the select */

   exec(N'declare hCForEachTable cursor global for select ''['' + REPLACE(schema_name(syso.schema_id), N'']'', N'']]'') + '']'' + ''.'' + ''['' + REPLACE(object_name(o.id), N'']'', N'']]'') + '']'' from dbo.sysobjects o join sys.all_objects syso on o.id = syso.object_id '

         ...

          return @retval

Beholding the FROM clause I knew exactly what I need to do for the @whereand to work.

use MyDatabase

exec sp_MSforeachtable

  @command1 = N'PRINT ''?''',

  @whereand = N'AND o.name LIKE ''T_TablesWeWant_%'''

Giving the output I was looking for (with some names changed and details left out again):

[dbo].[T_TablesWeWant_ACCOUNTING_ACCOUNT]

[dbo].[T_TablesWeWant_ACCOUNTING_TRANSACTION]

[dbo].[T_TablesWeWant_ACCOUNTING_TRANSACTION_TYPE]

...

Yep, using the alias o for the name column is all that I need to do to get sp_MSforeachtable to work in SQL Server 2012.

How to Find Perfect Numbers with F#

"But no perfection is so absolute, That some impurity doth not pollute."
-- The Rape of Lucrece Ver. 124 by William Shakespeare

"It is reasonable to have perfection in our eye ; that we may always advance towards it"
-- Samuel Johnson in letters to The Adventurer

Few things in life can be said to be perfect, but in mathematics there do exist numbers which are said to be perfect.  A perfect number is a number who's sum of its divisors (other than its self) is equal to its self.  

For exemplification, the number 6 is a perfect number.  Why is 6 perfect?

• 6 is divisible by 1
• 6 is divisible by 2
• 6 is divisible by 3

The sum of 1, 2, and 3 is 6 (e.g. 1 + 2 + 3 = 6).  Thus by the definition of a perfect number given above, 6 is a perfect number.  In fact 6 is the first perfect number (1 is never include in the realm of special numbers).

In order to say that a number is perfect we would need to do the following.

1. Find all of the divisors of the given number
2. Sum up the divisors found in step 1
3. Compare the sum found in step 2 to the input

Above is an example of what the flow would look like with the number 6.  We would take the numbers 1 - 5 as a list of possible divisors.  Filter down to 1, 2, and 3.  Sum 1, 2, and 3 giving us 6.  Last comparing the sum we got from the summing step to the input.  Since 6 equals 6, we would return true.

Hmmm, step 1 sounds a lot like a filter and step 2 sounds like folding.  I bet we can write a simple F# function that can find perfect numbers using a filter and a fold (using fsi.exe and Mono).

> let isPerfect x =

-   match x with

-   | x when x <= 1 -> false

-   | _ -> [1 .. x-1] |> List.filter (fun n -> x % n = 0) |> List.sum = x

- ;;

val isPerfect : int -> bool

In the function above we pattern match anything less than and including 1 as false, since by definition those numbers are not perfect numbers (if we wanted we could go up to and including 5 since 6 is the first perfect number).  Succeeding we just need to create a list of numbers up to the number x that we are checking for perfection.  We take this list and filter out the numbers that are not divisors leaving just the divisors.  Then we use the built in folding of summing with the List.sum function.  Finally we compare the sum of the divisors against the input number x.

Now lets test out the function with the perfect numbers 6, 28, and 496.  We'll also test with the less than perfect numbers of 5 and 99.

> isPerfect 6;;

val it : bool = true

> isPerfect 28;;

val it : bool = true

> isPerfect 496;;

val it : bool = true

> isPerfect 5;;  

val it : bool = false

> isPerfect 99;;

val it : bool = false

In fact if we wanted to we could use this function with List.filter against all of the numbers from 1 to 9999!

> [1 .. 9999] |> List.filter isPerfect

- ;;

val it : int list = [6; 28; 496; 8128]

That is in fact the first 4 perfect numbers which were known to the Greeks.

Note, this code is made to be readable not to be fast a few changes should be made to make it fast.