get routes through a sql server fk structure - http://sqlfiddle.com/#!6/4364c/5

diamond FK enforcement.sql


-- idea for making sure that diamond shaped relationships stay within the same parent

/*

-- what the diamond should like like
             ___ middleA-1 ___
           /                   \
parent-1 -                       - chiild-1
           \                   /
             ___ middleB-2 ___

-- a corrupted diamond would look like this, so now child-1 is in two hierarchies:
             ___ middleA-1 ___
           /                   \
parent-1 -                       - chiild-1
                               /
             ___ middleB-2 ___
           /
parent-2 -

*/

use master;
drop database diamond_enforcer;
create database diamond_enforcer;
go
use diamond_enforcer;

create table parent (id int primary key, name nvarchar(50));
create table middleA (id int primary key, name nvarchar(50), parentId int foreign key references parent(id));
create table middleB (id int primary key, name nvarchar(50), parentId int foreign key references parent(id));
create table child (id int primary key, name nvarchar(50), middleAId int foreign key references middleA(id), middleBId int foreign key references middleB(id));

create table foo (id int primary key, name nvarchar(50));
create table barA (id int primary key, name nvarchar(50), fooId int foreign key references foo(id));
create table barB (id int primary key, name nvarchar(50), fooId int foreign key references foo(id));
create table baz (id int primary key, name nvarchar(50), barAId int foreign key references barA(id), barBId int foreign key references barB(id));

-- valid diamond
insert into parent (id, name) values (10, 'parent-1');
insert into middleA (id, name, parentId) values (20, 'middleA-1', 10);
insert into middleB (id, name, parentId) values (30, 'middleB-2', 10);
insert into child (id, name, middleAId, middleBId) values (50, 'child-1', 20, 30);

-- invalid diamond
insert into parent (id, name) values (110, 'parent-1');
insert into parent (id, name) values (111, 'parent-2');
insert into middleA (id, name, parentId) values (120, 'middleA-1', 110);
insert into middleB (id, name, parentId) values (130, 'middleB-2', 111);
insert into child (id, name, middleAId, middleBId) values (150, 'child-1', 120, 130);

select
    *,
    case when parentA.id = parentB.id
        then 'valid'
        else 'parent mismatch'
    end [check]
from child
    inner join middleA on middleA.id = child.middleAId
    inner join parent parentA on parentA.id = middleA.parentId
    inner join middleB on middleB.id = child.middleBId
    inner join parent parentB on parentB.id = middleB.parentId

fk diamond hunting.sql

/*
-- tables to hunt through
select
    tb.name tblname
from sys.tables tb
    inner join sys.schemas sc on sc.schema_id = tb.schema_id
where sc.name = 'dbo'
    and tb.name <> 'foobar'
    and tb.name not like 'something%'
order by tb.name

-- FK list
select
    distinct -- makes no difference if there's two fks between the same tables
    --fk.name,
    parent.name tbl,
    ref.name fkTo
from sys.foreign_keys fk
    inner join sys.objects ref on ref.object_id = fk.referenced_object_id
    inner join sys.objects parent on parent.object_id = fk.parent_object_id
where fk.name <> 'foobar'
    and ref.name <> 'foobar'
    and ref.name not like 'something%'
order by
    parent.name,
    ref.name
;

-- recurse it
-- FK list
with fkCte as
(
    select
        distinct -- makes no difference if there's two fks between the same tables
        --fk.name,
        parent.name tbl,
        ref.name fkTo,
        ref.name hierarchy
    from sys.foreign_keys fk
        inner join sys.objects ref on ref.object_id = fk.referenced_object_id
        inner join sys.objects parent on parent.object_id = fk.parent_object_id
    where fk.name <> 'foobar'
        and ref.name <> 'foobar'
        and ref.name not like 'something%'
    union all
    select
    from fkCte
)
select
    fkCte.*
from fkCte
;


-- first success at recursing the hierarchy into a string
with fkCte
as
(
    select
        cast(ob.name as varchar(1000)) hrch,
        fk.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join sys.objects ob on ob.object_id = fk.parent_object_id
    union all
    select
        cast(fkCte.hrch + ' > ' + ob.name as varchar(1000)) hrch,
        fk.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join fkCte on fkCte.referenced_object_id = fk.parent_object_id
        inner join sys.objects ob on ob.object_id = fk.parent_object_id
    where fk.parent_object_id <> fk.referenced_object_id
        and ob.name <> 'foobar'
)
select distinct
    fkCte.hrch
from fkCte
where fkCte.hrch like '%>%'
order by fkCte.hrch
;

-- find all the parents of every table, and all the paths to get to that parent
-- https://gist.github.com/timabell/4f2c2bd2098424cb2def
with fkCte
as
(
    -- start with all tables that are the parents of FKs
    select
        cast(pa.name + ' > ' + ch.name as varchar(1000)) hrch,
        fk.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join sys.objects pa on pa.object_id = fk.parent_object_id
        inner join sys.objects ch on ch.object_id = fk.referenced_object_id
    where fk.parent_object_id <> fk.referenced_object_id
        and ch.name <> 'foobar'
        and ch.name not like 'something%'
    -- recursively add all the child-tables of those FKs, and find the FKs they are parents of
    union all
    select
        cast(fkCte.hrch + ' > ' + ch.name as varchar(1000)) hrch,
        fkCte.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join sys.objects pa on pa.object_id = fk.parent_object_id
        inner join sys.objects ch on ch.object_id = fk.referenced_object_id
        inner join fkCte on fkCte.referenced_object_id = fk.parent_object_id
    where fk.parent_object_id <> fk.referenced_object_id
        and ch.name <> 'foobar'
        and ch.name not like 'something%'
)
select distinct
    fkCte.parent_object_id,
    pa.name [parent],
    fkCte.referenced_object_id,
    ch.name [child],
    fkCte.hrch
from fkCte
    inner join sys.objects pa on pa.object_id = fkCte.parent_object_id
    inner join sys.objects ch on ch.object_id = fkCte.referenced_object_id
order by fkCte.hrch
;

-- find all the pairs of tables with more than one path between them
-- this is overkill because a path variation may already be covered within that path
with fkCte
as
(
    select
        cast(pa.name + ' > ' + ch.name as varchar(1000)) hrch,
        fk.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join sys.objects pa on pa.object_id = fk.parent_object_id
        inner join sys.objects ch on ch.object_id = fk.referenced_object_id
    where fk.parent_object_id <> fk.referenced_object_id
        and ch.name <> 'foobar'
        and ch.name not like 'something%'
    union all
    select
        cast(fkCte.hrch + ' > ' + ch.name as varchar(1000)) hrch,
        fkCte.parent_object_id,
        fk.referenced_object_id
    from sys.foreign_keys fk
        inner join sys.objects pa on pa.object_id = fk.parent_object_id
        inner join sys.objects ch on ch.object_id = fk.referenced_object_id
        inner join fkCte on fkCte.referenced_object_id = fk.parent_object_id
    where fk.parent_object_id <> fk.referenced_object_id
        and ch.name <> 'foobar'
        and ch.name not like 'something%'
)
-- now with that, find all the duplicate paths
select
    pa.name [parent],
    ch.name [child],
    count(*) qty
from fkCte
    inner join sys.objects pa on pa.object_id = fkCte.parent_object_id
    inner join sys.objects ch on ch.object_id = fkCte.referenced_object_id
group by
    pa.name,
    ch.name
having count(*) > 1
order by
    qty desc,
    pa.name,
    ch.name
;
*/

with tableCte as
(
    select
        tb.object_id tableId,
        tb.name tableName
    from sys.tables tb
        inner join sys.schemas sc on sc.schema_id = tb.schema_id
    where sc.name = 'dbo'
        and tb.name not like 'something%'
        and tb.name <> 'foobar' -- only used for auditing, self-referencing so causes a recursion loop, not required to stick within config boundaries anyway
        and tb.name <> '__MigrationLog' -- ready-roll data
),
fkCte as
(
    select
        parent.tableId parentId,
        parent.tableName parentName,
        fk.object_id fkId,
        fk.name fkName,
        child.tableId childId,
        child.tableName childName
    from tableCte parent
        inner join sys.foreign_keys fk on fk.parent_object_id = parent.tableId
        inner join tableCte child on child.tableId = fk.referenced_object_id
    where fk.parent_object_id <> fk.referenced_object_id -- self referencing tables are ignored to avoid recursion loop
),
recurseCte as
(
    select
        0 level,
        row_number() over(order by fkCte.parentName, fkCte.childName) startNumber,
        *,
        cast(fkCte.parentName + ' > ' + fkCte.childName as nvarchar(1000)) path
    from fkCte
    union all
    select
        recurseCte.level + 1 as level,
        recurseCte.startNumber,
        fkCte.*,
        cast(recurseCte.path + ' > ' + fkCte.childName as nvarchar(1000)) path
    from fkCte
        inner join recurseCte on recurseCte.childId = fkCte.parentId

)
select
    *
from recurseCte
order by recurseCte.path
;

-- abandoned attempt, I don't think CTEs are quite capable of precisely what I'm after

fk path analysis.sql

-- take 2
-- https://gist.github.com/timabell/b192752392d6ffb3e058

-- I'm not using CTEs to do the recursion as sql server doesn't have any nice way of storing a list of ints
-- in a single row (such as an array or list data type), and although I could use strings that's yuck.
-- Without the ability manipulate the segments of the path (hops) there isn't enough info to work on the
-- rest of my problem. (Enforcing consistency in diamond shaped relationships)

set nocount on;

-- can't think of a good name for the schema. tpa is my initials
if object_id('tpa.route') is null
begin
    exec ('create schema tpa');
    create table tpa.route (id int primary key identity(1,1), lastFkId int not null, parentRouteId int, hops int, firstTableId int, lastTableId int, path varchar(1000));
    create table tpa.hop (id int primary key identity(1,1), routeId int not null, fkId int not null);
end
go

-- cleanup from previous runs
delete tpa.hop;
delete tpa.route;

-- filtered table list
declare @table table (id int primary key);
insert into @table (id)
select tb.object_id tableId
from sys.tables tb
    inner join sys.schemas sc on sc.schema_id = tb.schema_id
where sc.name = 'dbo'
    and tb.name not like 'something%'
    and tb.name not in (
        'sysdiagrams',
        '__MigrationLog' -- ready-roll data
    )
;

--select st.name from @table tb inner join sys.tables st on st.object_id = tb.id order by st.name;

-- filtered fk list
declare @fk table (id int primary key);
insert into @fk (id)
select fk.object_id
from sys.foreign_keys fk
    inner join @table parent on fk.parent_object_id = parent.id -- filter
    inner join @table child on fk.referenced_object_id = child.id -- filter
where fk.parent_object_id <> fk.referenced_object_id -- self referencing tables are ignored to avoid recursion loop
;

--select sfk.name, parent.name parent, child.name child
--from @fk fk inner join sys.foreign_keys sfk on sfk.object_id = fk.id
--inner join sys.tables parent on parent.object_id = sfk.parent_object_id
--inner join sys.tables child on child.object_id = sfk.referenced_object_id;

declare @hops int = 1;

-- add all fks as routes, ready to recurse their children (single FK is a valid route between two tables)
insert into tpa.route (lastFkId, hops, firstTableId, lastTableId, path)
select fk.id, @hops, sfk.parent_object_id, sfk.referenced_object_id,
    object_name(sfk.parent_object_id) + ' > ' + object_name(sfk.referenced_object_id)
from @fk fk
    inner join sys.foreign_keys sfk on sfk.object_id = fk.id
;

-- add the only hop to those routes
insert into tpa.hop (routeId, fkId)
select rt.id, rt.lastFkId from tpa.route rt
;

-- recurse...
declare @maxRecursion int = 100;
while(@hops < @maxRecursion)
begin
    print 'hops: ' + cast(@hops as varchar);

    -- create another route entry for all longer chains of fks
    insert into tpa.route (lastFkId, parentRouteId, hops, firstTableId, lastTableId, path)
    select childFk.object_id, rt.id, @hops + 1, rt.firstTableId, childFk.referenced_object_id,
        rt.path + ' > ' + object_name(childFk.referenced_object_id)
    from tpa.route rt
        inner join sys.foreign_keys lastFk on lastFk.object_id = rt.lastFkId
        inner join sys.foreign_keys childFk on childFk.parent_object_id = lastFk.referenced_object_id
        inner join @fk childFkFilter on childFkFilter.id = childFk.object_id
    where rt.hops = @hops
    ;
    if @@ROWCOUNT = 0
    begin
        break;
    end

    set @hops = @hops + 1;

    -- copy the existing chain of hops into the new route
    insert into tpa.hop (routeId, fkId)
    select rt.id, hop.fkId
    from tpa.route rt
        inner join tpa.route parentRoute on parentRoute.id = rt.parentRouteId -- the route to get the base hop list from
        inner join tpa.hop hop on hop.routeId = parentRoute.id
    where rt.hops = @hops
    order by hop.id -- make sure path doesn't get re-ordered
    ;

    -- add the new fk as the last hop on these routes
    insert into tpa.hop (routeId, fkId)
    select
        rt.id,
        rt.lastFkId
    from tpa.route rt
    where rt.hops = @hops
    ;

end -- recursion

-- see the result

select * from tpa.route rt order by rt.path;

select
    rt.id routeId,
    rt.hops,
    rt.parentRouteId,
    hop.id hopId,
    concat(child.name, ' > ', parent.name) [child > parent]
from tpa.route rt
    left outer join tpa.hop hop on hop.routeId = rt.id
    left outer join sys.foreign_keys fk on fk.object_id = hop.fkId
    left outer join sys.tables parent on parent.object_id = fk.referenced_object_id
    left outer join sys.tables child on child.object_id = fk.parent_object_id -- confusing but correct
    --left outer join sys.foreign_keys fk on 
order by
    rt.path,
    hop.id;


-- and now for some analysis

-- lets see how many pairs of tables have multiple routes between them that might be susceptible to mismatched parent rows
--select
--    firstTable.name firstTableName,
--    lastTable.name lastTableName,
--    count(*) routeQty
--from tpa.route rt
--    inner join sys.tables firstTable on firstTable.object_id = rt.firstTableId
--    inner join sys.tables lastTable on lastTable.object_id = rt.lastTableId
--group by
--    firstTable.name,
--    lastTable.name
--having count(*) > 1 -- multiple path pairs only, these are the ones that could get corrupted
--order by routeQty desc
--;

-- todo: eliminate uninteresting routes/hops from the data
--  * routes with a point of convergence can be split in half and treated separately
--  * non-divergent appendages to divergent routes
--  * duplicate routes (generated by the above tidying)