论坛 › 技巧探讨 › 【C】对矩阵做广义笛卡尔积运算

usr 发表于 2022-5-18 21:20:40

【C】对矩阵做广义笛卡尔积运算

本帖最后由 usr 于 2022-5-18 21:30 编辑

对关系做笛卡尔积是DBMS中一个比较重要的操作。如果有两个关系A和B，A的列数是m，B的列数是n；
A的行数是x，B的行数是y。则，A*B的列数是m+n，行数是x*y。因为关系可以使用矩阵表示。
以下的代码显示了对两个关系矩阵生成笛卡尔积的过程。注意本程序需要StoneValley库的支持。

#include <stdio.h>
#include <string.h>
#include "./StoneValley/src/svstring.h"

P_MATRIX CreateCartesianProduct(P_MATRIX pma, P_MATRIX pmb, size_t size)
{
        size_t m, n;
        P_MATRIX pmr = strCreateMatrix(m = pma->ln * pmb->ln, n = pma->col + pma->col, size);
        if (NULL != pmr)
        {
                REGISTER size_t i, x, y;
                for (i = 0, x = 0, y = 0; i < m; ++i)
                {
                        /* Fill tuples of pma to pmr. */
                        memcpy(strGetValueMatrix(NULL, pmr, i, 0, size), strGetValueMatrix(NULL, pma, x, 0, size), size * pma->col);
                        /* Fill tuples of pmb to pmr. */
                        memcpy(strGetValueMatrix(NULL, pmr, i, pma->col, size), strGetValueMatrix(NULL, pmb, y, 0, size), size * pmb->col);
                        if (0 == (i + 1) % pmb->ln)
                                ++x;
                        if (++y == pmb->ln)
                                y = 0;
                }
        }
        return pmr;
}

int cbftvs(void * pitem, size_t size)
{
        static i = 1;
        printf("%s ", (char *)pitem);
        if (0 == i % size)
                printf("\n");
        ++i;
        return CBF_CONTINUE;
}

int main()
{
        P_MATRIX pmb = NULL, pmc = NULL;
        P_MATRIX pma = strCreateMatrix(3, 3, sizeof(char *));
        strSetValueMatrix(pma, 0, 0, "a1", sizeof(char *));
        strSetValueMatrix(pma, 0, 1, "b1", sizeof(char *));
        strSetValueMatrix(pma, 0, 2, "c1", sizeof(char *));

        strSetValueMatrix(pma, 1, 0, "a1", sizeof(char *));
        strSetValueMatrix(pma, 1, 1, "b2", sizeof(char *));
        strSetValueMatrix(pma, 1, 2, "c2", sizeof(char *));

        strSetValueMatrix(pma, 2, 0, "a2", sizeof(char *));
        strSetValueMatrix(pma, 2, 1, "b2", sizeof(char *));
        strSetValueMatrix(pma, 2, 2, "c1", sizeof(char *));

        pmb = strCreateMatrix(3, 3, sizeof(char *));
        strSetValueMatrix(pmb, 0, 0, "a1", sizeof(char *));
        strSetValueMatrix(pmb, 0, 1, "b2", sizeof(char *));
        strSetValueMatrix(pmb, 0, 2, "c2", sizeof(char *));

        strSetValueMatrix(pmb, 1, 0, "a1", sizeof(char *));
        strSetValueMatrix(pmb, 1, 1, "b3", sizeof(char *));
        strSetValueMatrix(pmb, 1, 2, "c2", sizeof(char *));

        strSetValueMatrix(pmb, 2, 0, "a2", sizeof(char *));
        strSetValueMatrix(pmb, 2, 1, "b2", sizeof(char *));
        strSetValueMatrix(pmb, 2, 2, "c1", sizeof(char *));

        pmc = CreateCartesianProduct(pma, pmb, sizeof(char *));

        strTraverseArrayZ(&pma->arrz, sizeof(char *), cbftvs, 3, FALSE);
        printf("\n");
        strTraverseArrayZ(&pmb->arrz, sizeof(char *), cbftvs, 3, FALSE);
        printf("\n");

        strTraverseArrayZ(&pmc->arrz, sizeof(char *), cbftvs, 6, FALSE);

        strDeleteMatrix(pma);
        strDeleteMatrix(pmb);
        strDeleteMatrix(pmc);
        return 0;
}

运行结果如下：
a1 b1 c1
a1 b2 c2 （关系A）
a2 b2 c1

a1 b2 c2
a1 b3 c2 （关系B）
a2 b2 c1

a1 b1 c1 a1 b2 c2 （笛卡尔积）
a1 b1 c1 a1 b3 c2
a1 b1 c1 a2 b2 c1
a1 b2 c2 a1 b2 c2
a1 b2 c2 a1 b3 c2
a1 b2 c2 a2 b2 c1
a2 b2 c1 a1 b2 c2
a2 b2 c1 a1 b3 c2
a2 b2 c1 a2 b2 c1
对于对关系做传统的集合运算“交并差”笔者会在日后的帖子里补上。
欢迎在本贴讨论DBMS相关知识或者笛卡尔积的优化技巧。

查看完整版本: 【C】对矩阵做广义笛卡尔积运算