Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

This should probably be easier than I'm making it, but I'm scratching my head coming up with an efficient way to query the results I want. I'm working with a table that has a source field and a destination field (along with some other unimportant fields). What I'm looking for are unique source-destination pairs, but only ones where exactly one source matches to exactly one destination. The basic rules involved in the selection process are:

  • One source must match to exactly one destination
  • One destination can have only a single source
  • A destination must not be a source for another group
  • There may be more than one record containing the desired source-destination pair (but we only want to return a distinct pair)

So, given this dataset:

Source   Destination
Grp10    Grp20
Grp11    Grp21
Grp11    Grp22
Grp12    Grp23
Grp12    Grp23
Grp13    Grp24
Grp24    Grp25

I would want the following results:

Source   Destination
Grp10    Grp20
Grp12    Grp23

I've gotten something close with a single query, using multiple levels of SELECT DISTINCT sub-queries joining back on the original table, but the performance began to drop off drastically (> 1 second for less than 200 rows).

I'm wondering if it would more appropriate to do grouping on Source, then, on Destination, store those in temporary tables, and join on those to reduce the data to the results I'm looking for? Some feedback would be great in case I'm missing some really trivial way to get the results I'm looking for.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I don't know all of your source data (or why there isn't any type of unique constraint that would prevent full-on duplicates or a source with multiple destinations), but given only the sample data supplied:

;WITH s AS 
(
  -- first let's eliminate duplicates
  SELECT DISTINCT Source, Destination 
    FROM dbo.MyTable
)
SELECT Source, Destination
FROM s
WHERE NOT EXISTS
(
  SELECT 1 FROM s AS d WHERE 

  -- eliminate chains in either direction:
    d.Destination = s.Source OR d.Source = s.Destination

  -- eliminate any source with multiple destinations:
    OR (d.Source = s.Source AND d.Destination <> s.Destination)

  -- eliminate any destination with more than one source
    OR (d.Destination = s.Destination AND d.Source <> s.Source)
);

SQL fiddle demo

share|improve this answer
    
Close, but it violates the third rule above about only a single source for each destination (which I see I didn't allow for in the test set in my question). You pointed me in the right direction, the query works with the addition of this: OR (d.Source <> s.Source AND d.Destination = s.Destination). I'll take another look at indexes as well to make sure they're set appropriately. –  Michael R Apr 1 at 23:58
    
@MichaelR Great, I had that initial WHERE clause in my fiddle but I removed it because it didn't seem to be a case you needed to cover, based on the sample data. –  Aaron Bertrand Apr 2 at 0:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.