Mapping fields of loosely coupled tables in SQL

Question

I am looking for SQL-Query that can match a set of individual size elements with a set of individual size buckets.

I would like to satisfy the following conditions:

• The bucket size must be greater than or equal to the size of the item.
• Each bucket can contain only one item or it remains empty.
• Each item can only be placed in one bucket.
• No element can be divided into several buckets.
• I want to fill the buckets so that the smallest unused buckets are filled first.
• Then the initial elements and the elements of the set can be ordered by size or id, but are not incremental
• The sizes and identifiers of the initial set of bucket and elements may be arbitrary and not begin with a known minimum value
• The result should always be correct if a valid mapping exists.
• The result may be incorrect if the match is invalid (for example, if there are more elements than buckets), but I would be grateful if the result would be empty or have another property / signal that indicates an incorrect result.

To give you an example, let's say the tables of my carpets and elements look like this:

Bucket:                     Item:
+---------------------+     +---------------------+
| BucketID | Size     |     | ItemID   | Size     |
+---------------------+     +---------------------+
| 1        | 2        |     | 1        | 2        |
| 2        | 2        |     | 2        | 2        |
| 3        | 2        |     | 3        | 5        |
| 4        | 4        |     | 4        | 11       |
| 5        | 4        |     | 5        | 12       |
| 6        | 7        |     +---------------------+
| 7        | 9        |
| 8        | 11       |
| 9        | 11       |
| 10       | 12       |
+---------------------+

Then I would like to have a mapping that returns the following table of results:

Result:
+---------------------+
| BucketID | ItemID   |
+---------------------+
| 1        | 1        |
| 2        | 2        |
| 3        | NULL     |
| 4        | NULL     |
| 5        | NULL     |
| 6        | 3        |
| 7        | NULL     |
| 8        | 4        |
| 9        | NULL     |
| 10       | 5        |
+---------------------+

-, ( Bucket.Size >= Item.Size) SQL . , , , (, 2 12, 2 ), .

, , , SQL, , .

, SQL? , , .

: , , Oracle, Postgres SQLite

Edit II: SQL , , , http://sqlfiddle.com/#!15/a6c30/1

Answer 1

@SoulTrain ( ):

; WITH ORDERED_PAIRINGS AS (
    SELECT i.ITEMID, b.BUCKETID, ROW_NUMBER() OVER (ORDER BY i.SIZE, i.ITEMID, b.SIZE, b.BUCKETID) AS ORDERING, DENSE_RANK() OVER (ORDER BY b.SIZE, b.BUCKETID) AS BUCKET_ORDER, DENSE_RANK() OVER (PARTITION BY b.BUCKETID ORDER BY i.SIZE, i.ITEMID) AS ITEM_ORDER
    FROM @ITEM i
    JOIN @BUCKET b
      ON i.SIZE <= b.SIZE
), ITEM_PLACED AS (
    SELECT ITEMID, BUCKETID, ORDERING, BUCKET_ORDER, ITEM_ORDER, CAST(1 as int) AS SELECTION
    FROM ORDERED_PAIRINGS
    WHERE ORDERING = 1
    UNION ALL
    SELECT *
    FROM (
        SELECT op.ITEMID, op.BUCKETID, op.ORDERING, op.BUCKET_ORDER, op.ITEM_ORDER, CAST(ROW_NUMBER() OVER(ORDER BY op.BUCKET_ORDER) as int) as SELECTION
        FROM ORDERED_PAIRINGS op
        JOIN ITEM_PLACED ip
          ON op.ITEM_ORDER = ip.ITEM_ORDER + 1
         AND op.BUCKET_ORDER > ip.BUCKET_ORDER
    ) AS sq
    WHERE SELECTION = 1
)
SELECT *
FROM ITEM_PLACED

Answer 2

... , recursive CTE, SQL

, , , Bucket Item .

DECLARE @BUCKET TABLE
    (
     BUCKETID INT
     , SIZE INT
    )

    DECLARE @ITEM TABLE
    (
     ITEMID INT
     , SIZE INT
    )
    ;  
    INSERT INTO @BUCKET
    SELECT 1,2 UNION ALL
    SELECT 2,2 UNION ALL
    SELECT 3,2 UNION ALL
    SELECT 4,4 UNION ALL
    SELECT 5,4 UNION ALL
    SELECT 6,7 UNION ALL
    SELECT 7,9 UNION ALL
    SELECT 8, 11 UNION ALL
    SELECT 9, 11 UNION ALL
    SELECT 10,12 

    INSERT INTO @ITEM
    SELECT 1,2 UNION ALL
    SELECT 2,2 UNION ALL
    SELECT 3,5 UNION ALL
    SELECT 4,11 UNION ALL
    SELECT 5,12;

    WITH TOTAL_BUCKETS
    AS (
        SELECT MAX(BUCKETID) CNT
        FROM @BUCKET
        ) -- TO GET THE TOTAL BUCKETS COUNT TO HALT THE RECURSION
        , CTE
    AS (
        --INVOCATION PART
        SELECT BUCKETID
            , (
                SELECT MIN(ITEMID)
                FROM @ITEM I2
                WHERE I2.SIZE <= (
                        SELECT SIZE
                        FROM @BUCKET
                        WHERE BUCKETID = (1)
                        )
                ) ITEMID --PICKS THE FIRST ITEM ID MATCH FOR THE BUCKET SIZE
            , BUCKETID + 1 NEXT_BUCKETID --INCREMENT FOR NEXT BUCKET ID 
            , (
                SELECT ISNULL(MIN(ITEMID), 0)
                FROM @ITEM I2
                WHERE I2.SIZE <= (
                        SELECT SIZE
                        FROM @BUCKET
                        WHERE BUCKETID = (1)
                        )
                ) --PICK FIRST ITEM ID MATCH
            + (
                CASE 
                    WHEN (
                            SELECT ISNULL(MIN(ITEMID), 0)
                            FROM @ITEM I3
                            WHERE I3.SIZE <= (
                                    SELECT SIZE
                                    FROM @BUCKET
                                    WHERE BUCKETID = (1)
                                    )
                            ) IS NOT NULL
                        THEN 1
                    ELSE 0
                    END
                ) NEXT_ITEMID --IF THE ITEM IS PLACED IN THE BUCKET THEN INCREMENTS THE FIRST ITEM ID
            , (
                SELECT SIZE
                FROM @BUCKET
                WHERE BUCKETID = (1 + 1)
                ) NEXT_BUCKET_SIZE --STATES THE NEXT BUCKET SIZE
        FROM @BUCKET B
        WHERE BUCKETID = 1

        UNION ALL

        --RECURSIVE PART
        SELECT NEXT_BUCKETID BUCKETID
            , (
                SELECT ITEMID
                FROM @ITEM I2
                WHERE I2.SIZE <= NEXT_BUCKET_SIZE
                    AND I2.ITEMID = NEXT_ITEMID
                ) ITEMID -- PICKS THE ITEM ID IF IT IS PLACED IN THE BUCKET
            , NEXT_BUCKETID + 1 NEXT_BUCKETID --INCREMENT FOR NEXT BUCKET ID 
            , NEXT_ITEMID + (
                CASE 
                    WHEN (
                            SELECT I3.ITEMID
                            FROM @ITEM I3
                            WHERE I3.SIZE <= NEXT_BUCKET_SIZE
                                AND I3.ITEMID = NEXT_ITEMID
                            ) IS NOT NULL
                        THEN 1
                    ELSE 0
                    END
                ) NEXT_ITEMID --IF THE ITEM IS PLACED IN THE BUCKET THEN INCREMENTS THE CURRENT ITEM ID
            , (
                SELECT SIZE
                FROM @BUCKET
                WHERE BUCKETID = (NEXT_BUCKETID + 1)
                ) NEXT_BUCKET_SIZE --STATES THE NEXT BUCKET SIZE
        FROM CTE
        WHERE NEXT_BUCKETID <= (
                SELECT CNT
                FROM TOTAL_BUCKETS
                ) --HALTS THE RECURSION
        )
    SELECT 
        BUCKETID
        , ITEMID
    FROM CTE

Answer 3

I would say that a single SQL query may not be a tool for the job, since buckets are "consumed" by allocating elements to them. You can use SQL, but not one query. sentence in pseudo code below:

Have a cursor on ITEM: 
    within the FETCH loop for that {
    SELECT in BUCKET the bucket with minimum bucket id and bucket size >= item size 
    INSERT bucket id, item id to MAPPING
}

If you need the NULL (unoccupied) buckets, you can locate them via a further 
INSERT into MAPPING (....)
SELECT <bucket id>, NULL
from    BUCKET 
where <bucket id> not in (SELECT <bucket id> from MAPPING);