传统的关联规则挖掘算法大都没有对事务数据库进行处理，直接读取事务数据库，即采用水平数据布局数据库形式。当事务平均宽度较长时或设定的支持度阈值较低时，频繁项集数量指数增长，原始的事务数据库中数据量则更加巨大。这种海量数据不可能一次性存入内存中，而只能放在辅助存储器中暂存。挖掘算法需要多次扫描庞大的事务数据库，产生了大量的I／O，这使得挖掘算法的效率低下，很难满足用户的需求。事务数据库表示方法的选择可能影响计算候选项集支持度的I／O开销。设计一种高效的数据结构，使之既能保证信息不丢失，即所存储信息的完整性，又能消除事务数据库中的冗余信息，减少数据存储量，成为提高挖掘算法的关键一步。针对传统关联规则挖掘算法采用水平数据布局数据库不能有效压缩事务数据的数量的缺点，一种新的事务数据的表示方法是采用垂直数据布局数据库。垂直数据布局事务数据库以项集中的每一个项为单位，对项集I＝｛I1，I2，…，Ip｝的每一个项Ij，事务数据库中记录一组支持该项的事务列表，我们称之为项的支持事物列表。每个项的支持事务列表不仅包含了支持该项的事务数量，而且包含了具体支持该项的事务序号。因此，将事务数据库的水平数据布局形式转化为垂直数据布局形式，没有造成信息的丢失，保证了信息的完整性。

为了更清楚地进行关联规则挖掘问题的讨论，假设原始的事务数据库，如表6.9所示，这是一个水平数据布局事务数据库。对原始的事务数据库进行一次遍历，将其转化为如表6.10所示的垂直数据布局事务数据库，每个项对应一个支持事务列表，支持事务列表存储的是支持该项的事务序号，并将项按支持计数排序。

表6.9　原始事务数据库（水平数据布局形式）

表6.10　转化后的事务数据库（垂直数据布局形式）

存储事务数据库。数组存储事务数据库中的所有1－项频繁项集，数据元素按照1－项频繁项集的支持度计数降序排列。每个数组元素包含两个域：

（1）项（Item），存储了元素对应的1－项频繁项集。

（2）支持事务列表（Tid List），存储了项对应的支持事务列表，支持事务列表以整数形式存储。我们将这种存储结构称之为TDA（Two dimensional array）存储结构。(www.daowen.com)

事务数据库的TDA存储结构具有以下性质：

性质1　TDA存储结构中数组元素的项与事务数据库中所有的1－项频繁项一一对应，数组元素的支持事务列表存储了所有支持该1－项频繁项集的事务。

性质2　TDA存储结构中数组元素的项i（项集I的第i项Ii），与任一数组元素的项j（项集I的第j项Ij）组成2－项集｛i，j｝，则｛i，j｝的支持事务列表｛i，j｝.TidList是项i和项j的支持事务列表｛i｝.TidList与j.TidList的交集，即｛i，j｝.TidList＝｛i｝.TidList∩｛j｝.TidList。

性质3若k－项集

则该X的支持事务列表是X的所有项ir1，ir2，…，irk的支持事务列表的交集，即

将原始的事务数据库以TDA存储结构形式存储后，保存了事务数据库中所有的1－项频繁项集和它们的支持事务列表。根据先验原理，如果一个项集是频繁的，则它的所有子集一定也是频繁的。即频繁项集只能由1－项频繁项集通过并操作而得到，而不可能包含1－项非频繁项集，故TDA存储在存储项集时不必存储非频繁项集及其支持事务列表，可以进一步节省存储空间。TDA挖掘算法依然采用Apriori的连接剪枝和计数的方法，我们通过对这种数组存储结构的1－项频繁项集和它们的支持事务列表分别进行交操作，可用于验证算法挖掘中出现的所有候选项集。