基于rules表从all_values表查找最小公共因子组合

现有两张数据库表 #

rules表（规则表） #

all_values表（值表） #

需求 #

以rules表的所有规则为基准，从all_values表里找出最小的不重复ID组合——即这些ID的集合能覆盖rules里的每一条规则，且不能包含多余ID（像{100,101,102}或者{100,102}这类带无用ID的组合必须排除）。最终期望输出格式如下：

解决方法（SQL实现） #

思路 #

1. 把rules里的每条规则转成唯一标识字符串，再统计每个ID能覆盖哪些规则；
2. 生成1到多个ID的所有可能组合，筛选出能覆盖全部规则的那些；
3. 剔除包含更小有效组合的冗余集合，剩下的就是符合要求的最小组合。

SQL代码 #

WITH rule_set AS (
    -- 将每条规则转换为唯一键，方便后续匹配
    SELECT CONCAT(entity_name, ':', entity_value) AS rule_key
    FROM rules
),
id_covered_rules AS (
    -- 统计每个ID能覆盖的所有规则键
    SELECT 
        av.id,
        STRING_AGG(DISTINCT CONCAT(av.entity_name, ':', av.entity_value), ',') AS covered_rules
    FROM all_values av
    GROUP BY av.id
),
all_valid_combinations AS (
    -- 生成所有可能的ID组合，筛选出能覆盖全部规则的组合
    SELECT 
        c1.id AS id1,
        c2.id AS id2,
        -- 合并当前组合覆盖的所有规则
        STRING_AGG(DISTINCT cr.rule_key, ',') AS total_covered
    FROM rule_set rs
    CROSS JOIN id_covered_rules c1
    -- 生成有序的双ID组合，避免重复组合
    LEFT JOIN id_covered_rules c2 ON c2.id > c1.id
    CROSS JOIN id_covered_rules cr
    WHERE 
        (cr.id = c1.id OR cr.id = c2.id)
        AND rs.rule_key IN (SELECT value FROM STRING_SPLIT(cr.covered_rules, ','))
    GROUP BY c1.id, c2.id
    -- 筛选出覆盖所有规则的组合
    HAVING STRING_AGG(DISTINCT cr.rule_key, ',') = (SELECT STRING_AGG(rule_key, ',') FROM rule_set)
),
minimal_combinations AS (
    -- 排除冗余组合，只保留最小有效集合
    SELECT 
        CASE 
            WHEN id2 IS NULL THEN JSON_QUERY('{"id":["' + CAST(id1 AS VARCHAR) + '"]}')
            ELSE JSON_QUERY('{"id":["' + CAST(id1 AS VARCHAR) + '","' + CAST(id2 AS VARCHAR) + '"]}')
        END AS json_comb
    FROM all_valid_combinations avc
    WHERE 
        -- 单ID组合直接保留；双ID组合需确保没有对应的单ID能覆盖所有规则
        (id2 IS NULL) 
        OR NOT EXISTS (
            SELECT 1 
            FROM all_valid_combinations avc2 
            WHERE avc2.id2 IS NULL 
            AND (avc2.id1 = avc.id1 OR avc2.id1 = avc.id2)
        )
)
-- 生成最终结果，添加组合序号
SELECT 
    ROW_NUMBER() OVER (ORDER BY json_comb) AS combination_id,
    json_comb AS json
FROM minimal_combinations;

代码说明 #

• rule_set：将规则转换为唯一字符串（如abc:true），简化后续覆盖判断；
• id_covered_rules：统计每个ID对应的所有规则，比如ID100能覆盖abc:true,abc:false,xyz:true；
• all_valid_combinations：生成单ID和有序双ID组合，筛选出能覆盖全部规则的集合；
• minimal_combinations：剔除冗余组合，比如如果单ID100能覆盖所有规则，就删掉包含100的双ID组合；
• 最后将结果转换为要求的JSON格式，并添加组合序号。

内容的提问来源于stack exchange，提问作者Jithu