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

usr

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

[C] 纯文本查看 复制代码

#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相关知识或者笛卡尔积的优化技巧。