Converting a Hash Map to a Table

Several times I have run into a conversion where I have needed to take a table that stores key value pairs into a table that lists all values for a given record.

The table look something like this:

Item_IDFieldValue
3ITEM CLASSIFICATIONHOT DOG
3ITEM DESCRIPTIONA TASTY CHICAGO STYLE DOG
3UNIT OF MEASURELENGTH
3HAS BUNY
4ITEM CLASSIFICATIONCORNDOG
4DIPPING SAUCEMUSTARD
4HAS BUNN
5ITEM CLASSIFICATIONHAMBURGER
5ITEM DESCRIPTIONA HAMBURGER WITH NO CHEESE
5UNIT OF MEASUREPOUND
5HAS BUNY

What I really wanted was something like this:

Item_IDItem ClassificationItem DescriptionUnit Of MeasureHas BunDipping Sauce
3HOT DOGA TASTY CHICAGO STYLE DOGLENGTHY
4CORNDOG NMUSTARD
5HAMBURGERA HAMBURGER WITH NO CHEESEPOUNDY

This is kind of like a PIVOT function, but since there can be a varied number of distinct records in the FIELD column, a pivot won’t always work.

What we can do is create a dynamic sql statement that will scan the distinct FIELD column and create a table for us based on the elements in the column.

DECLARE @selectpiece VARCHAR(1000)
   ,@field VARCHAR(1000)
   ,@columnDef VARCHAR(1000)
   ,@selectquery VARCHAR(MAX)
   ,@insertQuery VARCHAR(MAX)
   ,@createQuery VARCHAR(MAX)
         
SET @createQuery = 'CREATE TABLE dbo.TempElements (ITEM_ID INT'
SET @selectQuery = 'SELECT ITEM_ID'
SET @insertQuery = 'INSERT INTO dbo.TempElements (ITEM_ID'
 
DECLARE cur CURSOR FAST_FORWARD READ_ONLY
FOR
SELECT DISTINCT
        ',MAX(CASE WHEN [ELEMENT_DESC] = ''' + [ELEMENT_DESC] + '''
            THEN COALESCE([EL].[LIST_DESC],[DETAIL_VALUE])
            ELSE NULL
          END) AS [' + [ELEMENT_DESC] + ']' AS fieldSelect
       ,',[' + [ELEMENT_DESC] + ']' AS ColumnName
       ,',[' + [ELEMENT_DESC] + '] VARCHAR(MAX)' AS ColumnDef
FROM    [dbo].[ATTRIBUTE_ELEMENT] AS AE
WHERE   [ELEMENT_ID] IN (SELECT [ELEMENT_ID]
                         FROM   [ITEM_DETAIL] AS ID)
 
OPEN cur
FETCH NEXT FROM cur INTO @selectpiece, @field, @columnDef
WHILE @@FETCH_STATUS = 0
    BEGIN
     
        SET @createQuery += @columnDef
        SET @insertQuery += @field
        SET @selectQuery += @selectpiece
 
        FETCH NEXT FROM cur INTO @selectpiece, @field, @columnDef
    END
 
CLOSE cur
DEALLOCATE cur
 
SET @createQuery += ')'
 
SET @insertQuery += ')' + @selectquery + '
         FROM   [dbo].[ITEM_DETAIL] AS ID
                LEFT JOIN [dbo].[ELEMENT_LIST] AS EL
                    ON [ID].[ELEMENT_ID] = [EL].[ELEMENT_ID]
                       AND [ID].[LIST_ID] = [EL].[LIST_ID]
                JOIN [dbo].[ATTRIBUTE_ELEMENT] AS AE
                    ON [ID].[ELEMENT_ID] = [AE].[ELEMENT_ID]
            GROUP BY ITEM_ID'
 
EXEC sp_sqlexec @createQuery
EXEC sp_sqlexec @insertQuery

Solving Sudoku in One SQL Query – Part 3 – Solving the Puzzle

Okay, now that we have the general framework we can start writing the pieces that deal with the values that were given to us in the puzzle. The first thing I’m going to do is create a table that contains each possible value for each cell based on the values that are already in the solution.

Possibilities
  AS (
      SELECT    [g].[Row] -- first select just sets the value for the given locations.
               ,[g].[Col]
               ,[locations].[loc]
               ,[g].[Data]
      FROM      @given AS [g]
      JOIN      [locations]
                ON [locations].[col] = [g].[Col]
                   AND [locations].[row] = [g].[Row]
      UNION ALL
      SELECT    [possibility].[row]
               ,[possibility].[col]
               ,[possibility].[loc]
               ,[possibility].[val]
      FROM      (
                 SELECT [locations].*
                       ,[possibleValue].[val]
                 FROM   [locations] -- 
                 LEFT OUTER JOIN @given AS [g] -- I join to the given values to exclude these below
                        ON [g].[Col] = [locations].[col]
                           AND [g].[Row] = [locations].[row]
                 CROSS APPLY (
                              SELECT * FROM [Cnt] -- Join to all values 1-9
                             ) AS [possibleValue]
                 WHERE  [g].[Data] IS NULL --Exclude cells already defined in the given set
                ) AS [possibility]
      WHERE     [possibility].[val] NOT IN -- At this point, every cell not in the given set is
            (
                SELECT  [existingCell].[Data]
                FROM    (
                         SELECT [locations].[loc]
                               ,[g].[Data]
                         FROM   @given AS [g]
                         JOIN   [locations]
                                ON [locations].[row] = [g].[Row]
                                   AND [locations].[col] = [g].[Col]
                        ) AS [existingCell]
                JOIN    [groups] [existingCellGroup]
                        ON [existingCellGroup].[loc] = [existingCell].[loc]
                JOIN    [groups] [possibleValueGroup]
                        ON [existingCellGroup].[grouping] = [possibleValueGroup].[grouping]
                           AND [existingCellGroup].[loc] != [possibleValueGroup].[loc]
                WHERE   [possibleValueGroup].[loc] = [possibility].[loc]
            )
     ),

First we get all the cells that are already given to us. These cells will only have one valid option. Next we need to union those with all the possible values for all the other cells. We could just include all values 1 thru 9 for each of these cells, but we already know that some values will be impossible because they already exist in a group that the cell belongs to. So to reduce our sample space, we do a check to see if the value already exists in any of the cells that are a member of a group that our cell is a member of.

rowStrings
  AS (
      SELECT    CAST([Possibilities].[Data] AS VARCHAR(MAX)) AS string
               ,[Possibilities].[loc]
      FROM      [Possibilities]
      WHERE     [Possibilities].[loc] = 1
      UNION ALL
      SELECT    [rowStrings].[string] + '' + CONVERT(VARCHAR(1), [Possibilities].[Data])
               ,[Possibilities].[loc]
      FROM      (
                 SELECT * FROM [rowStrings] WHERE LEN ([string]) = [loc]
                ) AS [rowStrings]
      JOIN      [Possibilities]
                ON [rowStrings].[loc] + 1 = [Possibilities].[loc]
      WHERE     [Possibilities].[Data] NOT IN 
            (
                SELECT   SUBSTRING([rowStrings].[string], [g1].[loc], 1)
                FROM     [groups] [g1]
                JOIN     [groups] [g2]
                         ON [g2].[grouping] = [g1].[grouping]
                            AND [g2].[loc] = [Possibilities].[loc]
                            AND [g1].[loc] < [Possibilities].[loc]
            )
     ),

 

Solving Sudoku in One SQL Query – Part 2 – Creating the Framework

In this post, I’ll be diving deep into the code that was presented in this post.

Recursive CTEs

My solution utilizes a lot of recursive common table expressions (CTEs). CTEs are a simple way of defining a temporary projection in T-SQL that can be referenced multiple times later on in a query. Their real power, however, lies in their ability to be self-referencing and thus recursive. In a recursive CTE, we define an initial projection and UNION ALL that with a projection that references the table currently being defined.

Since this puzzle is all about digits 1 through 9, I need to make something that will get me those values to work with.

;WITH Cnt AS 
(
   SELECT 1 AS [val]
     UNION ALL
   SELECT [val] + 1
   FROM Cnt -- This is the table I'm creating right now, A SELF-REFERENCING DEFINITION!!!
   WHERE [val] < 9
)
/*
val
1
2
...
8
9
*/

This is an easy way to get the digits we need without having to list them all out. The first statement in the expression gives the basis of the recursion (1), then we UNION ALL to the Cnt table, selecting the value in the table + 1. Initially Cnt has a single record with [val] = 1. Then we union that with a record that is [val] + 1 = 2. This continues until the constraint on the second selection is no longer true. Once [val] = 9, we cannot union it again and we end up with a table of values 1 through 9.

Assigning Each Cell

Next, I want to get a set of all the possible locations in the grid with values ranging from 1 to 81. I could do another CTE like the one I just did, but I already have values 1 to 9, I can utilize my Cnt table to create my location table.

locations
  AS (
	  SELECT    [row].[val] AS [row]
		   ,[col].[val] AS [col]
		   ,(([row].[val] - 1) * 9) + [col].[val] AS [loc]
	  FROM      Cnt AS [row]
	  CROSS APPLY ( val FROM [Cnt] ) AS [col]
	 ),
/* locations table contents
row	col	loc
1	1	1
1	2	2
...
...
9	8	80
9	9	81
*/

Assigning Cells to Groups

In the game of Sudoku, each cell contains a digit that is unique within the row, column, and square that the cell is a member of. In order to facilitate checking that the value is unique, we will create a table that defines all the groups that each cell is a member of. The row and column groups are fairly easy to define, but the nine 3×3 boxes are a bit more difficult. In order to better set these groupings apart, I prefix the row groupings with a 10, the column groupings with a 20 and the box groupings with a 30.

This will allow us to cross-reference any locations to see if a particular value already exists. For instance, if I’m looking at the value in location 19, I’ll need to look at all the locations that are part of the groupings 103, 201, and 301 to see if the value I want to put in that location is already in any of the other locations in those groups.

groups
  AS (
      SELECT   -- Groups of Rows
                FLOOR(([loc] - 1) / 9) + 101 AS [grouping]
               ,[loc]
      FROM      [locations]
      UNION
      SELECT   -- Groups of Columns
                (([loc] - 1) % 9) + 201 AS [grouping]
               ,loc
      FROM      [locations]
      UNION
      SELECT   -- Groups of 3x3 Squares
                FLOOR(([row] - 1) / 3) * 3 + FLOOR(([col] - 1) / 3) + 301 [grouping]
               ,[locations].[loc]
      FROM      locations
     ),

The first two select clauses are retrieving the row and column groupings respectively, then the third grouping is creating groups for the nine 3×3 boxes in the grid. With these available to us, the job of building up a valid solution will be much easier.

/*
grouping  loc
101      1  -- Rows
101      2
...      
101      8
101      9
102      10
..       
102      18
103      19
...      
109      81
201      1  -- Columns
201      10
201      19
201      28
201      37
201      46
201      55
201      64
201      73
202      2
...      
202      74
203      3
...      
209      81
301      1  -- Squares
301      2
301      3
301      10
301      11
301      12
301      19
301      20
301      21
302      4
...      
302      24
303      7
...      
309      81
*/

Now I have all the framework I need to begin solving the sudoku puzzle. I have each of the 9 digits that I need; I have have given each cell in the grid a unique value; and I have made a listing of the groupings of cells that need to contain each of the 9 digits. In the next post I will walk through the code that takes the given values and builds out the correct solution.

Solving Sudoku in One SQL Query – Part 1

I’ve seen a couple examples of using SQL to solve sudoku puzzles, but most of the ones I’ve seen have used loops or cursors to cycle through and create a correct answer. I feel like if you make a solution that’s procedural like that, you might as well have done it in a language that’s designed to be procedural. The real trick is to write a query that really makes use of a relational database’s parallel projection capabilities to solve a sudoku challenge

We’ll start with the fairly simple sudoku puzzle below.

Sudoku

The Solution

For those looking for a tl;dr, here is the complete solution for solving a sudoku puzzle with a single query. The first two query simply define and populate the given values of a puzzle, then the last query evaluates and returns a solved sudoku grid. I’ll be posting a couple more times with in depth looks at various sections of the query.

DECLARE @given AS TABLE (Row INT, Col INT, Data INT);

INSERT  INTO @given
        (Row, Col, Data)
VALUES  (2, 1, 9), (3, 1, 2), (4, 1, 5), (6, 1, 6), (8, 1, 3),
        (9, 1, 8), (5, 2, 1), (6, 2, 3), (8, 2, 2), (4, 3, 2),
        (8, 3, 4), (9, 3, 6), (2, 4, 3), (5, 4, 8), (6, 4, 1),
        (7, 4, 2), (3, 5, 8), (5, 5, 9), (7, 5, 4), (3, 6, 7),
        (4, 6, 4), (5, 6, 5), (8, 6, 6), (1, 7, 3), (2, 7, 5),
        (6, 7, 8), (2, 8, 4), (4, 8, 1), (5, 8, 6), (1, 9, 8),
        (2, 9, 2), (4, 9, 7), (6, 9, 4), (7, 9, 5), (8, 9, 1);

WITH    Cnt
          AS (
              SELECT    1 AS [val]
              UNION ALL
              SELECT    [val] + 1
              FROM      Cnt
              WHERE     [val] < 9
             ),
        locations
          AS (
              SELECT    [row].[val] AS [row]
                       ,[col].[val] AS [col]
                       ,(([row].[val] - 1) * 9) + [col].[val] AS [loc]
              FROM      Cnt AS [row]
              CROSS APPLY (
                           SELECT val FROM [Cnt]
                          ) AS [col]
             ),
        groups
          AS (
              SELECT   -- Groups of Rows
                        FLOOR(([loc] - 1) / 9) + 101 AS [grouping]
                       ,[loc]
              FROM      [locations]
              UNION
              SELECT   -- Groups of Columns
                        (([loc] - 1) % 9) + 201 AS [grouping]
                       ,loc
              FROM      [locations]
              UNION
              SELECT   -- Groups of 3x3 Squares
                        FLOOR(([row] - 1) / 3) * 3 + FLOOR(([col] - 1) / 3) + 301 [grouping]
                       ,[locations].[loc]
              FROM      locations
             ),
        Possibilities
          AS (
              SELECT    [g].[Row]
                       ,[g].[Col]
                       ,[locations].[loc]
                       ,[g].[Data]
              FROM      @given AS [g]
              JOIN      [locations]
                        ON [locations].[col] = [g].[Col]
                           AND [locations].[row] = [g].[Row]
              UNION ALL
              SELECT    [possibility].[row]
                       ,[possibility].[col]
                       ,[possibility].[loc]
                       ,[possibility].[val]
              FROM      (
                         SELECT [locations].*
                               ,[possibleValue].[val]
                         FROM   [locations]
                         LEFT OUTER JOIN @given AS [g]
                                ON [g].[Col] = [locations].[col]
                                   AND [g].[Row] = [locations].[row]
                         CROSS APPLY (
                                      SELECT * FROM [Cnt]
                                     ) AS [possibleValue]
                         WHERE  [g].[Data] IS NULL --Exclude any cells that are already defined in the given set
                        ) AS [possibility]
              WHERE     [possibility].[val] NOT IN 
					(
						SELECT  [existingCell].[Data]
						FROM    (
								 SELECT [locations].[loc]
									   ,[g].[Data]
								 FROM   @given AS [g]
								 JOIN   [locations]
										ON [locations].[row] = [g].[Row]
										   AND [locations].[col] = [g].[Col]
								) AS [existingCell]
						JOIN    [groups] [existingCellGroup]
								ON [existingCellGroup].[loc] = [existingCell].[loc]
						JOIN    [groups] [possibleValueGroup]
								ON [existingCellGroup].[grouping] = [possibleValueGroup].[grouping]
								   AND [existingCellGroup].[loc] != [possibleValueGroup].[loc]
						WHERE   [possibleValueGroup].[loc] = [possibility].[loc]
					)
             ),
        rowStrings
          AS (
              SELECT    CAST([Possibilities].[Data] AS VARCHAR(MAX)) AS string
                       ,[Possibilities].[loc]
              FROM      [Possibilities]
              WHERE     [Possibilities].[loc] = 1
              UNION ALL
              SELECT    [rowStrings].[string] + '' + CONVERT(VARCHAR(1), [Possibilities].[Data])
                       ,[Possibilities].[loc]
              FROM      (
                         SELECT * FROM [rowStrings] WHERE LEN ([string]) = [loc]
                        ) AS [rowStrings]
              JOIN      [Possibilities]
                        ON [rowStrings].[loc] + 1 = [Possibilities].[loc]
              WHERE     [Possibilities].[Data] NOT IN 
					(
						SELECT   SUBSTRING([rowStrings].[string], [g1].[loc], 1)
						FROM     [groups] [g1]
						JOIN     [groups] [g2]
								 ON [g2].[grouping] = [g1].[grouping]
									AND [g2].[loc] = [Possibilities].[loc]
									AND [g1].[loc] < [Possibilities].[loc]
					)
             ),
        correctAnswer
          AS (
              SELECT    [l].[row] AS [Row]
                       ,[l].[col] AS [Col]
                       ,SUBSTRING(string, l.[loc], 1) AS [Val]
              FROM      (
						-- If any of the recursive groups gets to and prints the 81 location, that means 
						-- everything before it is valid
                         SELECT * FROM rowStrings WHERE [rowStrings].[loc] = 81 
                        ) [cte]
              CROSS APPLY (
                           SELECT * FROM [locations]
                          ) [l]
             )
     SELECT [Row],[1],[2],[3],[4],[5],[6],[7],[8],[9]
     FROM   (
             SELECT * FROM correctAnswer
            ) AS SourceTable PIVOT
( MAX([Val]) FOR [Col] IN ([1], [2], [3], [4], [5], [6], [7], [8], [9]) ) AS PivotTable
     ORDER BY [Row];

SQL Cascade Delete without Cascade

One of the things that I’ve commonly run into when I am working on a data conversion is an issue where I want to delete everything from a table, but there are foreign keys pointing to that table, and then there are foreign keys pointing to the tables with the foreign keys, etc. This is a stored procedure I created that will allow you to pass in the qualified name of a table (“[dbo].[MyTable]”) and it will recursively find all tables with foreign keys to it, then delete the data from all those tables in reverse order so that you don’t run into those annoying foreign key references.

IF OBJECT_ID(N'[dbo].[CascadeDelete]') IS NOT NULL 
    DROP PROCEDURE [dbo].[CascadeDelete]
GO

CREATE PROCEDURE [dbo].[CascadeDelete]
    @qualifiedTable VARCHAR(512)
AS 
BEGIN

    IF OBJECT_ID(@qualifiedTable) IS NULL 
        RETURN

    DECLARE @level INT = 1

    CREATE TABLE #keys
        ([Level] INT
        ,[TableName] VARCHAR(512))

    INSERT  INTO [#keys]
            ([Level], [TableName])
            SELECT  @level
                   ,@qualifiedTable

    WHILE @@ROWCOUNT < 0
        AND @level < 100 
        BEGIN

            SET @level += 1

            INSERT  INTO [#keys]
                    SELECT  @Level
                           ,'[' + [S].[name] + '].'
                          + '[' + [T].[name] + ']' AS [TableName]
            FROM    [sys].[tables] AS T
                    JOIN [sys].[schemas] AS S
                        ON [T].[schema_id] = [S].[schema_id]
                    JOIN [sys].[foreign_keys] AS FK
                        ON [T].[object_id] = [FK].[parent_object_id]
                           AND [FK].[referenced_object_id] IN 
                                  (SELECT   OBJECT_ID([TableName])
                                   FROM     [#keys])
                    JOIN [sys].[columns] AS C
                        ON [FK].[key_index_id] = [C].[column_id]
                           AND [C].[object_id] = [FK].[parent_object_id]
                           AND [C].[is_nullable] = 0
            WHERE   [T].[object_id] NOT IN (SELECT  OBJECT_ID([TableName])
                                            FROM    [#keys])
        END

    DECLARE @query VARCHAR(MAX)

    DECLARE cur CURSOR FAST_FORWARD READ_ONLY
    FOR
    SELECT  'DELETE FROM ' + TableName + ';'
    FROM    [#keys] AS K
    ORDER BY [Level] DESC

    OPEN cur
    FETCH NEXT FROM cur INTO @query

    WHILE @@FETCH_STATUS = 0 
        BEGIN
            EXEC sp_sqlexec @query
            FETCH NEXT FROM cur INTO @query
        END

    CLOSE cur
    DEALLOCATE cur
END

Gmail ProTips #2 – Priority Inbox

So my friends asked me to send out some tips for how I set up my email and I got some good feedback from it, so I guess I’ll post this next one on my blog…

I have been using gmail’s new Priority Inbox for some time now and I really like it. Basically, it automatically sorts the emails that are important to me from the ones that are less important. From what I’ve seen, this is mostly determined by who the sender is, and how many recipients there are. IE, a message sent from someone in my contacts to only me is likely more important than one sent by Facebook to a mailing list.

So… to get set up with priority inbox, simply go to your email settings screen

and click on the Priority Inbox view.

 

Select all the options as you see here:

Once this is all set up, you’ll have a link on the top of your left hand menu for Priority Inbox. Clicking on that will take you to a screen similar to this:

As you can see, my emails are now separated into unread messages that Gmail has classified as Important, messages I’ve starred, important messages I’ve already read, and then everything else. Now, Gmail isn’t perfect when it comes to figuring out what’s important to you, but it can actually learn from you as you use the priority settings. If you get a message that should be marked important and isn’t, or one that isn’t important but got labeled as such, you can change it’s importance by selecting it and pressing the little  keys. Gmail will learn to mark these messages correctly over time.

 

This really helps to weed out all the miscellaneous stuff I get from social networks and forums and highlights the important messages I get from actual people! Pretty Cool!

Gmail ProTips #1 – Infinite Email Addresses

I know some of you wanted more deets on filtering spam and such, so here’s my set up that seems to work pretty well.

What you mainly need to know is that you can add a + to the end of your gmail name and add whatever you want and it will all go to your account. So if my email were tanner@gmail.com, I could have people send mail to tanner+skiing@gmail.com or tanner+church@gmail.com or whatever and it will all come to the same inbox, and unless you’re looking for it, you won’t even notice a difference.

So what I do is, any time some service asks for an email and I don’t particularly want any junk from them, I use tanner+spam@gmail.com and then in my gmail I create a filter where I have the word “spam” in the from box and automatically send it to the spam folder. That way I can get the confirmation email out of the spam box when it’s sent to me and ignore anything else from that address.

You could take it a step further by using the name of the service, like, tanner+BestBuy@gmail.com, and then when I start getting spam sent to that address, I know which service sold my email address.

The other thing I was saying is that a lot of websites won’t let you put a + in their email address fields, so for those I use an email address like this:tan.ner@gmail.com

You can add a period anywhere in your name and it will also be sent to you. So I have another filter looking for tan.ner@gmail.com and doing the same thing.

So there’s my Gmail tip of the Day! Tune in next time for Priority Inbox and Keyboard Shortcuts!