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

usr

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

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include "./StoneValley/src/svstring.h"
   
5. 
   
6. P_MATRIX CreateCartesianProduct(P_MATRIX pma, P_MATRIX pmb, size_t size)
   
7. {
   
8.         size_t m, n;
   
9.         P_MATRIX pmr = strCreateMatrix(m = pma->ln * pmb->ln, n = pma->col + pma->col, size);
   
10.         if (NULL != pmr)
    
11.         {
    
12.                 REGISTER size_t i, x, y;
    
13.                 for (i = 0, x = 0, y = 0; i < m; ++i)
    
14.                 {
    
15.                         /* Fill tuples of pma to pmr. */
    
16.                         memcpy(strGetValueMatrix(NULL, pmr, i, 0, size), strGetValueMatrix(NULL, pma, x, 0, size), size * pma->col);
    
17.                         /* Fill tuples of pmb to pmr. */
    
18.                         memcpy(strGetValueMatrix(NULL, pmr, i, pma->col, size), strGetValueMatrix(NULL, pmb, y, 0, size), size * pmb->col);
    
19.                         if (0 == (i + 1) % pmb->ln)
    
20.                                 ++x;
    
21.                         if (++y == pmb->ln)
    
22.                                 y = 0;
    
23.                 }
    
24.         }
    
25.         return pmr;
    
26. }
    
27. 
    
28. int cbftvs(void * pitem, size_t size)
    
29. {
    
30.         static i = 1;
    
31.         printf("%s ", (char *)pitem);
    
32.         if (0 == i % size)
    
33.                 printf("\n");
    
34.         ++i;
    
35.         return CBF_CONTINUE;
    
36. }
    
37. 
    
38. int main()
    
39. {
    
40.         P_MATRIX pmb = NULL, pmc = NULL;
    
41.         P_MATRIX pma = strCreateMatrix(3, 3, sizeof(char *));
    
42.         strSetValueMatrix(pma, 0, 0, "a1", sizeof(char *));
    
43.         strSetValueMatrix(pma, 0, 1, "b1", sizeof(char *));
    
44.         strSetValueMatrix(pma, 0, 2, "c1", sizeof(char *));
    
45. 
    
46.         strSetValueMatrix(pma, 1, 0, "a1", sizeof(char *));
    
47.         strSetValueMatrix(pma, 1, 1, "b2", sizeof(char *));
    
48.         strSetValueMatrix(pma, 1, 2, "c2", sizeof(char *));
    
49. 
    
50.         strSetValueMatrix(pma, 2, 0, "a2", sizeof(char *));
    
51.         strSetValueMatrix(pma, 2, 1, "b2", sizeof(char *));
    
52.         strSetValueMatrix(pma, 2, 2, "c1", sizeof(char *));
    
53. 
    
54.         pmb = strCreateMatrix(3, 3, sizeof(char *));
    
55.         strSetValueMatrix(pmb, 0, 0, "a1", sizeof(char *));
    
56.         strSetValueMatrix(pmb, 0, 1, "b2", sizeof(char *));
    
57.         strSetValueMatrix(pmb, 0, 2, "c2", sizeof(char *));
    
58. 
    
59.         strSetValueMatrix(pmb, 1, 0, "a1", sizeof(char *));
    
60.         strSetValueMatrix(pmb, 1, 1, "b3", sizeof(char *));
    
61.         strSetValueMatrix(pmb, 1, 2, "c2", sizeof(char *));
    
62. 
    
63.         strSetValueMatrix(pmb, 2, 0, "a2", sizeof(char *));
    
64.         strSetValueMatrix(pmb, 2, 1, "b2", sizeof(char *));
    
65.         strSetValueMatrix(pmb, 2, 2, "c1", sizeof(char *));
    
66. 
    
67.         pmc = CreateCartesianProduct(pma, pmb, sizeof(char *));
    
68. 
    
69.         strTraverseArrayZ(&pma->arrz, sizeof(char *), cbftvs, 3, FALSE);
    
70.         printf("\n");
    
71.         strTraverseArrayZ(&pmb->arrz, sizeof(char *), cbftvs, 3, FALSE);
    
72.         printf("\n");
    
73. 
    
74.         strTraverseArrayZ(&pmc->arrz, sizeof(char *), cbftvs, 6, FALSE);
    
75. 
    
76.         strDeleteMatrix(pma);
    
77.         strDeleteMatrix(pmb);
    
78.         strDeleteMatrix(pmc);
    
79.         return 0;
    
80. }
    

复制代码

运行结果如下：
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相关知识或者笛卡尔积的优化技巧。