Theory and Practice of Database and Data Analysis (3) – Exhaustive Search by Traversing Table Relationships

Thursday, September 29, 2011

In this post, I will discuss about building a script to find all the relevant data starting from a table name and primary key value. In the previous post, I have discussed how to a list of tables that references a table. From a parent table, we just need to get a list of child tables. We then loop through each child table to select records using the parent primary key value. If the child tables themselves have child tables, we repeat the same approach by recursively getting the grand children.

I often need to remote-desktop into clients system where I only have read privilege; I can neither create stored procedures nor execute them. So I am going to present a script that requires only read privilege.

In transact-SQL (T-SQL) batch, looping through records can be implemented using cursor or temp table. I used the later approach as temp table can grow so that I can also use it for recursion as well.

Recursion is a harder problem here. Recursion can be done in most of programming languages by calling procedures recursively. However, that is not possible here since I am restricted to a batch. In computer science, recursion can be implemented with a loop with a stack. In many programming languages, when a caller calls a callee, the program would save the current local data as well as the returning location of the caller into the stack. The area in the stack used by each call is called a stack frame. Once the callee returns, the program will restore the local data from the stack and resume from the previous location.

In my script, I use temp table #ref_contraints to accomplish both looping and recursion. referential constraints from the top table are added to the table as they are discovered and removed from the table when they are consumed (that is, no longer needed). I used the depth-first traversal in my script. With this structure, I can change to breath-first traversal with minimum efforts.

The #keyvalues temp table contains the primary key values for the table that I have already traversed. I can get the records from the child tables by joining to the key values in this table so that I only need to query each child table once for each foreign key relationship.

In order to make the script simpler, I eliminate the schema and assume all tables are under the schema “dbo”. This works with our database, and works with databases in Microsoft Dynamics CRM 2011.

I have also assumed that all primary keys contain only one integer column. This is true with out database. This is also true with Microsoft Dynamics CRM 2011 except you need to change integer id to guid.

I added comments the script so that one would know where the code would correspond to looping and procedure calling if the code is written in a language like VB.NET or C#. The comments also indicate the insertion points if additional code is needed.

--input values
declare @ptable varchar(256)
declare @pid int
set @ptable = 'Invoices'
set @pid = 55813

--variables
declare @sql varchar(2000)
declare @pcolumn varchar(256) --primary key column of the parent table
declare @ftable varchar(256)  --child table name
declare @fcolumn varchar(256) --column of the child table that link to primary key of the parent table
declare @fpcolumn varchar(256) --primary key column of the child table
declare @frame int
declare @rid int
set @frame = 0

--Temp table used to hold key values in related tables
--drop table #keyvalues
--select * from #keyvalues order by id asc
create table #keyvalues
(
    id int not null identity(1,1),
    tablename varchar(256),
    keyvalue int
)

--Temp table used to hold referential contraints so that we can navigate down
--drop table #ref_contraints
--select * from #ref_contraints order by rid
create table #ref_contraints
(
    rid int not null identity (1,1),
    frame int,
    ptable varchar(256),
    pcolumn varchar(256),
    ftable varchar(256),
    fcolumn varchar(256)
)

--get the primary column name
select @pcolumn = kcu.COLUMN_NAME
from INFORMATION_SCHEMA.TABLE_CONSTRAINTS tc
inner join INFORMATION_SCHEMA.KEY_COLUMN_USAGE kcu on tc.CONSTRAINT_NAME = kcu.CONSTRAINT_NAME
where tc.CONSTRAINT_TYPE = 'PRIMARY KEY' and tc.TABLE_NAME = @ptable

--select the parent record
set @sql = 'select t1.* from ' + @ptable + ' t1 where ' + @pcolumn + '=' + cast(@pid as varchar(10))
--print @sql
exec (@sql)

if (@@ROWCOUNT > 0) begin
    --Save the key value of the parent record
    set @sql = 'insert into #keyvalues select ''' + @ptable + ''', t1.' + @pcolumn + 
        ' from ' + @ptable + ' t1 where ' + @pcolumn + '=' + cast(@pid as varchar(10))

exec (@sql)

GOTO GET_CHILDREN_BEGIN --call the get_chilren function
    GET_CHILDREN_RETURN2: --return from the last get_children function
        drop table #keyvalues
        drop table #ref_contraints
        GOTO BATCH_END
end

GET_CHILDREN_BEGIN: --parameters are @ptable and 
    set @frame = @frame + 1

insert into #ref_contraints(frame, ptable, pcolumn, ftable, fcolumn)
    select @frame, kcup.TABLE_NAME, kcup.COLUMN_NAME, kcuf.TABLE_NAME, kcuf.COLUMN_NAME
    from INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS rc 
    inner join INFORMATION_SCHEMA.KEY_COLUMN_USAGE kcup 
        on kcup.CONSTRAINT_SCHEMA = rc.UNIQUE_CONSTRAINT_SCHEMA
        and kcup.CONSTRAINT_NAME = rc.UNIQUE_CONSTRAINT_NAME
    inner join INFORMATION_SCHEMA.KEY_COLUMN_USAGE kcuf
        on kcuf.CONSTRAINT_SCHEMA = rc.CONSTRAINT_SCHEMA
        and kcuf.CONSTRAINT_NAME = rc.CONSTRAINT_NAME
        and kcup.ORDINAL_POSITION = kcuf.ORDINAL_POSITION
    left outer join #ref_contraints trc --Exclude existing records
        on trc.frame = @frame
        and trc.ptable = kcup.TABLE_NAME
        and trc.pcolumn = kcup.COLUMN_NAME
        and trc.ftable =   kcuf.TABLE_NAME
        and trc.fcolumn = kcup.COLUMN_NAME
    where kcup.TABLE_NAME = @ptable
    and not (kcuf.TABLE_NAME = @ptable) --Exclude foreign key relationship within the same table
    and trc.frame is null

FOR_EACH_CHILD_LOOP_BEGIN:    
        select @rid=rid, @ptable = ptable, @pcolumn = pcolumn, @ftable = ftable, @fcolumn = fcolumn
        from #ref_contraints
        where frame = @frame

if (@@ROWCOUNT > 0) begin
            delete #ref_contraints where  rid = @rid    --delete the one that is used
            
            set @sql = 'select ''' + CAST(@frame as varchar(10)) + ''',''' 
                + @ptable + ''', ''' + @ftable + ''', t1.* from ' 
                + @ftable + ' t1 inner join #keyvalues t2 on t1.' +
                @fcolumn + '= t2.keyvalue where t2.tablename=''' + @ptable + ''''
            --print @sql
            exec (@sql)

if (@@ROWCOUNT > 0) begin
                --get the primary column name
                select @fpcolumn = kcu.COLUMN_NAME
                from INFORMATION_SCHEMA.TABLE_CONSTRAINTS tc
                inner join INFORMATION_SCHEMA.KEY_COLUMN_USAGE kcu on tc.CONSTRAINT_NAME = kcu.CONSTRAINT_NAME
                where tc.CONSTRAINT_TYPE = 'PRIMARY KEY' and tc.TABLE_NAME = @ftable
            
                --outer join t3 to avoid duplicated records
                set @sql = 'insert into #keyvalues select distinct ''' + @ftable + ''', t1.' + @fpcolumn + 
                    ' from ' + @ftable + ' t1 inner join #keyvalues t2 on t1.' +
                    @fcolumn + '= t2.keyvalue left outer join #keyvalues t3 on t3.tablename=''' +
                    @ftable + ''' and t3.keyvalue=t1.' + @fpcolumn + 
                    ' where t3.id is null and t2.tablename=''' + @ptable + ''''

exec (@sql)
                
                set @ptable = @ftable --The child table is the new parent table now
                GOTO GET_CHILDREN_BEGIN --Call get_children
                GET_CHILDREN_RETURN1:
            end
        end else begin
            GOTO FOR_EACH_CHILD_LOOP_EXIT
        end
    FOR_EACH_CHILD_LOOP_END:
        --Clean up before returning to the loop
        --On finishing cleaning up, return to the beginning of the loop
        GOTO FOR_EACH_CHILD_LOOP_BEGIN
    FOR_EACH_CHILD_LOOP_EXIT:
    --Execute code after the FOR_EACH_CHILD_LOOP here
    
    --On finishing everything, exit the routine
    GOTO GET_CHILDREN_END
GET_CHILDREN_END:
    --clean up the frame here
    set @frame = @frame - 1
    
    if @frame > 0
        GOTO GET_CHILDREN_RETURN1
    else
        GOTO GET_CHILDREN_RETURN2
        
BATCH_END: --end of the batch

In future posts of this series, I will discuss how to capture human intelligence to make search even more powerful.

No Comments