Earlier tonight I was faced with a corrupted installation of SQL Server. This is perhaps a consequence of my having installed a default instance of SQL Server 2014 after uninstalling an instance of SQL Server 2005. The Engine and SQL Agent would not start. To correct this I had to set the configuration for the engine’s service account to start the engine in SQL Configuration Manager. I then had to add the SQL Agent service account to the login and grant it required permissions.
Kevin was your normal everyday car buyer. He wasn’t an earlier adopter or gadget obsessed. He worked with technology but not in it. As he sat there in the driver’s seat of ALR-300 listening to beep after beep staring at the flashing light, he couldn’t help but wonder if this was some sort of malicious prank. At least he wasn’t late for an important meeting.
He had bought the ALR-300 so he could just sit and ride. Self driving cars were everywhere. There was another one zipping along, not stopped on the shoulder beeping. He wished had signed up for the remote care and technology package so he could ask the car why it was beeping. Staring at the dashboard and the blinking light thinking “if only it would…”, he decided to call for help. After a few minutes of checking his email and posting to Facebook how horrible his day was starting he found a tow truck service and called.
The longest 43 minutes dragged by and at least a dozen ALR-300’s zipped past. How many 400’s and 500’s he’d lost count. He was almost regretting buying a self driving car. At least with a manual he could drive it himself. Ah, but how many hours would he have spent staring at break lights instead of his tablet.
The tow truck drove him and his vehicle to the nearest dealership. He explained the problem to the receptionist. She made a face and walked off to get the service manager. He could see them both talking about him. The service manager looked concerned. He picked up the phone.
After a brief conversation he put the phone down and came out of his office. “Kevin, thank you for coming here today. I had to double check with the manufacturer but I am confident that you can drive home. You see the beeping red light that says drive indicates that you need to drive.”
What if we were to implement an index structure that relied on Cunningham chains for large data sets and contained leaf nodes that were in turn B+ trees?
I want to share with you my Kickstarter. The Crash Surveillance Drone is a UAV deployed from a vehicle by the deployment of an air bag. It can alert the authorities, get real time imagery, and signal other drivers of the accident. From multi-car pileups to people struck exiting their vehicles in an accident, I truly believe that my Kickstarter will lead to many saved lives. Please, share this with everyone you know.
In my last post I discussed the topic of modularity of code in the context of generating prime numbers. In this post I am going to discuss the topic of recursion in SQL server in the context of modular code subsequently in the context of generating prime numbers.
In the prior post we showed how modularizing would allow us more opportunity to improve and correct past work without redoing everything from scratch. We created a function for testing primality called intIsPrime. We call it intIsPrime because if we really want a lot of primes (as many as we can get from SQL Server without inventing a new data type or doing some column and constraint tricks or both) we would need a bigintIsPrime function for all of those primes bigger than the integer data type which ends with the 2,147,483,647 which is prime. 2,147,483,647 is in fact the 3rd double Mersenne prime.
We then went on to query for the primes in the next 100 or so numbers using a technique called a recursive common table expression (CTE). In the spirit of modularity and reaching beyond a mere hundred tests through modular design consider this function:
CREATE FUNCTION dbo.hundredMorePrimeTests(@n int) RETURNS TABLE AS RETURN ( WITH recurseMore AS ( SELECT @n AS p, 1 AS n UNION ALL SELECT p + 1 , n + 1 FROM recurseMore WHERE n < 101 ) SELECT p, n FROM recurseMore WHERE dbo.intIsPrime(p) = 1 )
By putting our recursive CTE into a function. We can pass it the parameter we want to test the next hundred integers for primality. This allows us to call it in a stored procedure that bases the call on the last prime in our prime table. We can also have that stored procedure call its self (another type of recursive technique) which enables us to run the stored procedure once and have it execute 32 times (an error occurs is a stored procedure nests more than 32 levels).
CREATE PROCEDURE thirtyTwoHundredPrimalityTests @c INT = 1 AS BEGIN SET NOCOUNT ON; DECLARE @n INT; SELECT @n = MAX(p) FROM dbo.primes; INSERT INTO dbo.primes SELECT p FROM dbo.hundredMorePrimeTests(@n); SET @n = @c + 1; IF @n < 32 EXEC thirtyTwoHundredPrimalityTests @n ; END
There you have it, modular and recursive. If we wanted to we could call thrityTwoHundredPrimalityTests from another stored procedure that could serve to limit the run based on how long we want to run, or how many integers we want to test. We can pass @c as any integer and the result would be that many 100s of integers tested.
In a previous post I wrote about this new (I think) set of prime numbers and how I generated them with T-SQL. Now, I want to discuss a more philosophical and practical issue. No, I am not going to split hairs about how the prime numbers were there already, like all the integers, and we are just testing them for primality. I also don’t want to discuss why 1 is or is not a prime number (I am not a mathematician). I am actually looking to discuss modularity and code reuse.
Take a look at this function:
DROP FUNCTION intIsPrime; GO CREATE FUNCTION intIsPrime ( @n INT) RETURNS BIT AS BEGIN DECLARE @return BIT; SET @return = 1; IF @n IN (1,2,3) GOTO finished; IF @n % 2 = 0 OR @n % 3 = 0 OR FLOOR(SQRT(@n)) = SQRT(@n) --I can't be the first person to note that an integer squareroot means non-prime. SET @return = 0; GOTO finished; DECLARE @k INT; SET @k = 5; --By starting at five we are starting at 6k-1 WHILE @k <= FLOOR(SQRT(@n)) BEGIN IF @n % @k = 0 OR @n % (@k + 2) = 0 --which makes this 6k+1 SET @return = 0; GOTO finished; SET @k = @k + 6 ; END finished: RETURN @return END
By encapsulating the prime test into a function we separate the operation of testing primality from that of generating integers, as well as from inserting into the table. Why is this advantageous? Consider a scenario where we have a table that we filled with prime numbers using an algorithm that we believed was the most efficient method for testing primality. Later we realized that this super efficient algorithm used by “famous” mathematicians actually only determined that number were likely prime. Uh, oh. Chances are that we were using some sort of special built prime detecting super-computer and didn’t generate nearly enough numbers to have a non-prime that was merely likely. That is still a question of chance rather than certainty.
So now if we were to modify the script from our previous post we would have to get rid of all of numbers and generate new ones. If we had implemented the algorithm for testing primality as above (a better algorithm than before which serves to highlight the advantages of modularity) as a function we can now use the improved algorithm to test those numbers already in the table. We can also use the more efficient approach of selecting the numbers where the prime test fails rather than iterating over all of them. If we wanted to put in new primes we can select from a recursive CTE those integers that pass the primality test rather than incrementing through each number.
WITH recurseMore AS ( SELECT max(p) AS p, 1 AS n FROM primes UNION ALL SELECT p + 1, n + 1 FROM recurseMore WHERE n < 101 ) SELECT p FROM recurseMore WHERE dbo.intIsPrime(p) = 1
Using the recursive CTE (which is more efficient, but that’s a topic for a different post) further serves to highlight the value of modularity. Note that we are restricting the recursive portion of the CTE to n < 101. This is because a CTE can only recurse 100 levels (+1 for the anchor row). This limits us to selecting primes that are within 100 of our max prime. We can work around this by encapsulating the CTE in a stored procedure or table valued function that accepts the max prime as a parameter. Technically it would accept an integer and generate a list of primes less than or equal to that integer + 100. By calling this in a wrapper we can test the return of that function inserting new primes, and increasing the input parameter. If we get no primes for a group of 100 (again I am not a mathematician so don’t make fun if its impossible to go a hundred integers without a prime), we can just pass the next number above it and carry on.
Preview the Crash Safety Drone today.