CREATE #TempTable (
  RowID int,
  CatID in
)

DECLARE @MinRow int
DECLARE @MaxRow int
DECLARE @RanRow int

SELECT @MinRow = MIN(ProductID), @MaxRow = MAX(ProductID)
FROM Products

WHILE EXISTS(SELECT * FROM Products WHERE CatID NOT IN (SELECT CatID FROM #TempTable))
BEGIN
  SET @RanRow = ROUND(RAND()*(@MaxRow - @MinRow), 0) + @MinRow

  -- This is done to remove a bias. Note that technically this could
  -- repeat forever, but only theoretically. Highly inefficient, find
  -- a different way if you can :)
  WHILE NOT EXISTS(SELECT * FROM Products WHERE CatID NOT IN (SELECT CatID FROM #TempTable))
  BEGIN
      SET @RanRow = ROUND(RAND()*(@MaxRow - @MinRow), 0) + @MinRow
  END

  INSERT #TempTable
  SELECT ProductID, CatID FROM Products WHERE RowID = @RanID

  SELECT @MinRow = MIN(ProductID), @MaxRow(ProductID) FROM Products
           WHERE CatID NOT IN (SELECT CatID FROM #TempTable)

END

-- Okay, then you can join them to return full details
SELECT Products.*
FROM Products INNER JOIN #TempTable ON (ProductID = RowID)

CREATE TABLE ProductCategories (
  productID int NOT NULL,
  categoryID int NOT NULL,
  PRIMARY KEY (productID, categoryID)
)

DECLARE @p int, @c int

SET NOCOUNT ON
BEGIN TRANSACTION

SET @p = 0
WHILE @p < 100
BEGIN
  SET @c = 0
  WHILE @c < 10
  BEGIN
    IF RAND() < 0.5
      INSERT INTO ProductCategories VALUES (@p, @c)
    SET @c = @c + 1
  END
  SET @p = @p + 1
END

COMMIT TRANSACTION
SET NOCOUNT OFF

SELECT * FROM ProductCategories AS T1
WHERE categoryID = (
    SELECT TOP 1 categoryID
    FROM ProductCategories AS T2
    WHERE T1.productID = T2.productID
    ORDER BY NEWID()
  )