Topological sort of SQL Server objects

Dependencies Object List.sql

--use master;
--go

--drop database if exists UnravelDependencies;
--go

--create database UnravelDependencies;
--go
use UnravelDependencies;
--go

--create schema s;
--go


--
-- Test cases
--
-- The notation A <- B means B references A so A must exist before B can be created.
--


/*
Test: simple case, single stand-alone table.
Result: single table output.

create table s.stand_alone(c int primary key);
*/


/*
Test: a chain of tables with foreign key relationships.
Result: highest table in level 0, middle in level 1, lowest in level 2.

create table s.highest(c int primary key);
create table s.middle(c int primary key, d int not null foreign key references s.highest(c));
create table s.lowest(c int primary key, e int not null foreign key references s.middle(c));

*/


/*
Test: two tables reference a common parent with foreign key relationships.
Result: parent table in level 0, children in level 1 sorted by name.

create table s.parent(c int primary key);
create table s.child1(c int primary key, d int not null foreign key references s.parent(c));
create table s.child2(c int primary key, d int not null foreign key references s.parent(c));

*/


/*
Test: a table references two parents.
Result: parent tables in level 0, child in level 1.

create table s.Mother(m int primary key);
create table s.Father(f int primary key);
create table s.Offspring
(
	m int not null foreign key references s.Mother(m),
	f int not null foreign key references s.Father(f)
);

*/


/*
Test: self-referencing table.
Result: the table is in level 0; self-reference is ignored.

create table s.Employee
(
	EmployeeId	int		primary key,
	ManagerId	int		NULL
		foreign key references s.Employee(EmployeeId)
);
*/


/*
Test: multiple references between two tables.
Result: Address in Level 0, PurchaseOrder in Level 1; each is output once only.

create table s.Address(AddressId int primary key);
create table s.PurchaseOrder
(
	DeliveryAddressId int not NULL
		foreign key references s.Address(AddressId),
	BillingAddressId int not NULL
		foreign key references s.Address(AddressId)
);
*/

/*
Test: multiple pathways of different depth between two tables.
      A <- B <- C
	  ^         |
	  +---------+
Result: the lowest object is output only when all paths have been resolved.
    L0:A; L1:B; L2:C.

create table s.A(a int primary key);
create table s.B
(
	b int primary key,
	a int not NULL
		foreign key references s.A(a)
);
create table s.C
(
	a int not NULL
		foreign key references s.A(a),
	b int not NULL
		foreign key references s.B(b),
);
*/

/*
Test: SP references a table that exists.
Result: Table returned at level 0, SP at level 1.

create table s.T1(c int);
go
create or alter procedure s.P1
as
begin
	select * from s.T1;
end
go
*/

/*
Test: SP references a table that does NOT exist.
Result: Error message, batch halts.

create or alter procedure s.P_Ghost
as
begin
	select * from s.Ghost;
end
go
drop procedure if exists s.P_Ghost;
go
*/


/*
Test: Table depends on a module e.g. calculated column using a function.
Result: function returned at Level 0, table at level 1.

create function s.Uno()
returns int
as
begin
    declare @Response int;
    set @Response = 1;
    return(@Response);
end
go

create table s.Calculated(c int, u as s.uno());
go
*/


/*
Test: circular references
		e.g. stored procedures A execs B, B execs A.
		Can circular FKs be defined?
Result: dumped at the end for manual reconciliation.


-- Circular procedures

create or alter procedure s.P_X
as
begin
	exec s.P_Y;
end
go

create or alter procedure s.P_Y
as
begin
	exec s.P_X;
end
go


-- Circular tables
create table s.Circle1
(
	c1 int primary key,
	c2 int null
);
go

create table s.Circle2
(
	c2 int primary key,
	c1 int null foreign key references s.Circle1(c1)
);
go

alter table s.Circle1
add constraint FK_C1_C2 foreign key (c2)
references s.Circle2(c2);
go
*/


/*
Test: views are processed
Result: the tables are at level 0, the view at level 1.

create table s.TV(a int);
go

create or alter view s.V
as
	select a.* from s.TV as a, s.TV as b;
go
*/


/*
Test: ensure user defined types are processed.
Result; type is level 0 and SP at level 1.

create type s.Type1 as table (c int);
go

create or alter procedure s.P_TYPE
	@Data s.Type1 READONLY
as
	select * from @Data;
go
*/






set nocount on;

declare @Level	int = 0;		-- counts the iterations
declare @r		int = 0;


-- Have to separate objects from links else the last object in a chain is
-- deleted when the last link is deleted and that object is never returned.
declare @Object table
(
	SchemaName	sysname			not NULL,
	ObjectName	sysname			not NULL,
	TypeDesc	nvarchar(60)	not NULL,

	primary key clustered
	(
		SchemaName	ASC,
		ObjectName		ASC
	)
);


declare @Link table		-- objects whos dependency has not yet been determined.
(
	ReferencingSchema	sysname		not NULL,
	ReferencingName		sysname		not NULL,
	ReferencedSchema	sysname		not NULL,
	ReferencedName		sysname		not NULL,

	primary key clustered
	(
		ReferencingSchema	ASC,
		ReferencingName		ASC,
		ReferencedSchema	ASC,
		ReferencedName		ASC
	)
);


declare @Result table			-- objects in their proper dependency order.
(
	Level		int				not NULL,
	SchemaName	sysname			not NULL,
	ObjectName	sysname			not NULL,
	TypeDesc	nvarchar(60)	not NULL,

	primary key clustered
	(
		SchemaName	ASC,
		ObjectName	ASC
	)
);



--
-- Populate Data
--


-- Find all objects that are of interest.
insert @Object
(
	SchemaName,
	ObjectName,
	TypeDesc
)
select
	OBJECT_SCHEMA_NAME(o.object_id),
	OBJECT_NAME(o.object_id),
	o.type_desc
from sys.objects as o
where o.type_desc in
(
	--'AGGREGATE_FUNCTION',
	--'CHECK_CONSTRAINT',
	--'CLR_SCALAR_FUNCTION',
	--'CLR_STORED_PROCEDURE',
	--'CLR_TABLE_VALUED_FUNCTION',
	--'CLR_TRIGGER',
	--'DEFAULT_CONSTRAINT',
	--'EXTENDED_STORED_PROCEDURE',
	--'FOREIGN_KEY_CONSTRAINT',
	--'INTERNAL_TABLE',
	--'PLAN_GUIDE',
	--'PRIMARY_KEY_CONSTRAINT',
	--'REPLICATION_FILTER_PROCEDURE',
	--'RULE',
	'SEQUENCE_OBJECT',
	--'SERVICE_QUEUE',
	'SQL_INLINE_TABLE_VALUED_FUNCTION',
	'SQL_SCALAR_FUNCTION',
	'SQL_STORED_PROCEDURE',
	'SQL_TABLE_VALUED_FUNCTION',
	--'SQL_TRIGGER',
	'SYNONYM',
	--'SYSTEM_TABLE',
		-- UD types are not easily handled through sys.objects.
		-- Will be pulled from sys.types
		--'TABLE_TYPE',			-- From the documentation
		--'TYPE_TABLE',			-- From observation in sys.objects
	--'UNIQUE_CONSTRAINT',
	'USER_TABLE',
	'VIEW'
);


insert @Object
(
	SchemaName,
	ObjectName,
	TypeDesc
)
select
	SCHEMA_NAME(t.schema_id),
	t.name,
	'TABLE_TYPE'
from sys.types as t
where is_user_defined = 1
and is_table_type = 1;



/*
sys.sysdepends (deprecated use sys.sql_expression_dependencies)

Contains dependency information between objects (views, procedures, and
triggers) in the database,  and the objects (tables, views, and procedures)
that are contained in their definition.
*/


/*
sys.sql_dependencies (deprecated use sys.sql_expression_dependencies)

Contains a row for each dependency on a referenced entity as referenced in the
Transact-SQL expression or statements that define some other referencing object.

Observations:
This table's columns are object_id values. It will not reveal unresolved
objects say deferred SPs.

If an object is referenced multiple times there will be multiple rows here.
*/



/*
sys.sql_expression_dependencies

Contains one row for each by-name dependency on a user-defined entity in the
current database. This includes dependences between natively compiled, scalar
user-defined functions and other SQL Server modules. A dependency between two
entities is created when one entity, called the referenced entity, appears by
name in a persisted SQL expression of another entity, called the referencing
entity. For example, when a table is referenced in the definition of a view,
the view, as the referencing entity, depends on the table, the referenced
entity. If the table is dropped, the view is unusable.

Observations:
If an object is referenced as a one-part name e.g. dbo.TableX in the statement
`select * from TableX` then ReferencedSchema will be NULL. To avoid this I'll
use referenced_id to produce the schema.

If referencing_id is NULL we have a deferred reference and will fail the process.
If the referenced object is subsequently created referencing_id is populated
when this table is re-read (checked for SP referencing a table).

XPATH queries will produce rows here where the referenced object is the resultset
alias e.g. x.query('/Path/To/Object') will produce a referenced scheam "x" and
object "query".

A filtered index creates a row where the column(s) in the filter
become referenced_minor_name.

User-defined table types, for table-valued parameters to SPs, report the correct
schema name in referenced_schema_name but the wrong value from OBJECT_SCHEMA_NAME().
*/

if exists	(	
				select 1
				from sys.sql_expression_dependencies
				where referenced_id is NULL
			)
begin
	-- Code references an object which does not exist in the DB. Ergo there
	-- cannot be a definition for it. Fail the process.
	raiserror('An unresolved references exists in sys.sql_expression_dependencies', 18, 0);
	return;
end

insert @Link
(
	ReferencingSchema,
	ReferencingName,
	ReferencedSchema,
	ReferencedName
)
select distinct
	referencing_schema	= OBJECT_SCHEMA_NAME(referencing_id),
	referencing_object	= OBJECT_NAME(referencing_id),
	referenced_schema_name = COALESCE
								(
									referenced_schema_name,				-- for user-defined table types
									OBJECT_SCHEMA_NAME(referenced_id),	-- for one-part names of other types
									SCHEMA_NAME(t.schema_id)			-- for UDTTs referenced by one-part names.
								),
	referenced_entity_name
from sys.sql_expression_dependencies as ed
left outer join sys.types as t
	on t.user_type_id = ed.referenced_id
	and ed.referenced_class_desc = 'TYPE'
	and ed.referenced_schema_name is NULL		-- short circuit the lookup
where referenced_id is not NULL
--order by 3



/*
sys.dm_sql_referenced_entities 

Returns one row for each user-defined entity that is referenced by name in the
definition of the specified referencing entity in SQL Server.

Observations:
Would have to cycle through objects or CROSS APPLY to use this.
*/

/*
sys.dm_sql_referencing_entities

Returns one row for each entity in the current database that references another
user-defined entity by name.

A table is tracked as a referencing entity only when it references a Transact-
SQL module, user-defined type, or XML schema collection in the definition of a
computed column, CHECK constraint, or DEFAULT constraint.

Observations:
Would have to cycle through objects or CROSS APPLY to use this.
*/


/*
sys.foreign_keys

Contains a row per object that is a FOREIGN KEY constraint, with sys.object.type = F.
*/

insert @Link
(
	ReferencingSchema,
	ReferencingName,
	ReferencedSchema,
	ReferencedName
)
select distinct	-- there may be many FKs between any two tables. Remove dupes to keep the PK happy.
	ReferencingObject	= OBJECT_SCHEMA_NAME(parent_object_id),
	ReferencingObject	= OBJECT_NAME(parent_object_id),
	ReferencedObject	= OBJECT_SCHEMA_NAME(referenced_object_id),
	ReferencedObject	= OBJECT_NAME(referenced_object_id)
from sys.foreign_keys
-- omit self-referencing tables e.g. adjacency list hierarchies.
where parent_object_id <> referenced_object_id;






-- Debug
--select 'Link', * from @Link;
--select 'Object', * from @Object;
--return;




--
-- Algorithm
--

-- I want to do this recursively and also want each object to appear only once.
-- Since an object can be referenced from several others I need to tick off each from a
-- list as it is encountered. A recursive CTE will not let this happen.
-- So manual recursion is required.

while 1 = 1	-- if circular dependencies exits rows will remain in @Link at the end.
begin
	-- Skim off those objects which have no dependencies
	insert @Result
	(
		Level,
		SchemaName,
		ObjectName,
		TypeDesc
	)
	select
		@Level,
		o.SchemaName,
		o.ObjectName,
		o.TypeDesc
	from @Object as o
	where not exists
	(
		select 1
		from @Link as l
		where l.ReferencingSchema = o.SchemaName
		and l.ReferencingName = o.ObjectName
	);

	-- No more non-circular dependencies
	IF @@ROWCOUNT = 0 break;


	-- Remove the links where found items are referenced
	delete l
	from @Link as l
	inner join @Result as rlt
		on rlt.SchemaName = l.ReferencedSchema
		and rlt.ObjectName = l.ReferencedName;

	-- Remove found objects from the "look for" list.
	delete o
	from @Object as o
	inner join @Result as rlt
		on rlt.SchemaName = o.SchemaName
		and rlt.ObjectName = o.ObjectName;

	-- Debug at end of cycle
	--select Link = 'Link', @Level, * from @Link;
	--select Object = 'Object', @Level, * from @Object;
	--select
	--	Result = 'Result', @Level, *
	--from @Result as r
	--order by
	--	r.Level,
	--	r.TypeDesc,
	--	r.SchemaName,
	--	r.ObjectName;

	set @Level += 1;
end

-- What's left are in circular dependencies
select
	Circular = 'Circular',
	ReferencingSchema,
	ReferencingName,
	ReferencedSchema,
	ReferencedName
from @Link
order by
	ReferencingSchema,
	ReferencingName,
	ReferencedSchema,
	ReferencedName;


-- The desired output, in object-creation order
select
	'end',
	*
from @Result as r
order by
	r.Level,
	r.TypeDesc,
	r.SchemaName,
	r.ObjectName;