[發(fā)明專利]一種Gaia系統(tǒng)中的多表連接優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011267934.3
• 申請(qǐng)日: 2020-11-13
• 公開（公告）號(hào): CN112256705B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計(jì)）人: 宗楓博;王國(guó)仁;趙宇海;鄭軍
• 申請(qǐng)（專利權(quán)）人: 北京理工大學(xué);東北大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22
• 代理公司: 北京理工大學(xué)專利中心 11120
• 代理人: 劉西云;李微微

1.一種Gaia系統(tǒng)中的多表連接優(yōu)化方法，其特征在于，包括以下步驟：

S1：獲取原連接樹的屬性信息，其中，所述屬性信息包括原連接樹包含的源表的數(shù)量以及中間表的數(shù)量、每個(gè)源表中各列的屬性碼、每個(gè)中間表中各列的屬性碼、原連接樹的健值、原連接樹的輸出表、輸出表各列的屬性碼，其中，健值為用戶指定的屬性碼，則兩個(gè)源表之間、源表與中間表之間按照健值進(jìn)行等值連接，且不同源表之間、不同源表與中間表之間采用的健值不完全相同，并將源表的數(shù)量記為M，中間表的數(shù)量記為N，且N＝M-2；

S2：根據(jù)原連接樹的屬性信息為每個(gè)健值構(gòu)建索引條目，其中，每個(gè)索引條目至少包括兩個(gè)索引位，第一個(gè)索引位用于存儲(chǔ)健值，其余索引位用于存儲(chǔ)列號(hào)，且每個(gè)索引條目存儲(chǔ)的列號(hào)的確定方法為：分別將各健值作為當(dāng)前健值執(zhí)行以下步驟：

S21：確定包含當(dāng)前健值的源表；

S22：從步驟S21確定的各源表中獲取當(dāng)前健值所在列的列號(hào)，并將得到的列號(hào)作為存儲(chǔ)的列號(hào)；

S3：對(duì)各源表進(jìn)行編號(hào)，并根據(jù)各源表編號(hào)構(gòu)建編號(hào)列表，其中，編號(hào)列表包括M列，每一列存儲(chǔ)一個(gè)源表的編號(hào)；

S4：分別將各索引條目作為當(dāng)前索引條目執(zhí)行有向連接操作，建立編號(hào)列表與各索引條目之間的有向連接，得到有向索引圖，所述有向連接操作為：

將當(dāng)前索引條目中用于存儲(chǔ)列號(hào)的各索引位分別作為當(dāng)前索引位執(zhí)行以下步驟：

確定當(dāng)前索引位存儲(chǔ)的列號(hào)對(duì)應(yīng)的源表，并將其記為當(dāng)前源表；

判斷當(dāng)前源表是否已與其他索引條目建立有向連接關(guān)系，若為否，則建立從當(dāng)前源表編號(hào)的所在列到當(dāng)前索引位的直接有向連接；若為是，則建立從當(dāng)前源表編號(hào)的所在列到當(dāng)前索引位的間接有向連接，其中，間接有向連接的建立方法為：

獲取已與當(dāng)前源表建立有向連接關(guān)系的所有索引位，并將所有索引位均記為中間索引位，其中，有向連接關(guān)系包括直接有向連接和間接有向連接；

在各中間索引位中獲取最后與當(dāng)前源表建立有向連接關(guān)系的索引位，并將該索引位作為末尾索引位；

建立從末尾索引位到當(dāng)前索引位的有向連接，實(shí)現(xiàn)從當(dāng)前源表編號(hào)的所在列到當(dāng)前索引位的間接有向連接；

S5：基于有向索引圖，采用動(dòng)態(tài)規(guī)劃法得到各源表的連接關(guān)系表達(dá)式，根據(jù)連接關(guān)系表達(dá)式重新構(gòu)建連接樹，完成多表連接的優(yōu)化。

2.如權(quán)利要求1所述的一種Gaia系統(tǒng)中的多表連接優(yōu)化方法，其特征在于，所述采用動(dòng)態(tài)規(guī)劃法得到各源表的連接關(guān)系表達(dá)式具體包括以下步驟：

S51：分別將各源表作為當(dāng)前源表執(zhí)行以下步驟，得到各源表對(duì)應(yīng)的一階配對(duì)表、與一階配對(duì)表進(jìn)行等值連接而生成的一階中間表：

從有向索引圖中獲取與當(dāng)前源表享有相同健值的所有源表，并將其記為一階備選源表；

分別獲取當(dāng)前源表與各一階備選源表的等值連接代價(jià)，將最小等值連接代價(jià)對(duì)應(yīng)的一階備選源表作為與當(dāng)前源表進(jìn)行等值連接的一階配對(duì)表；

將當(dāng)前源表與一階配對(duì)表進(jìn)行等值連接，得到一階中間表，并將該等值連接關(guān)系記為一階表達(dá)式；

S52：分別將各源表作為當(dāng)前源表執(zhí)行連接更新操作，以得到各源表對(duì)應(yīng)的等值連接代價(jià)最小的連接方式，其中，所述連接更新操作具體為：

在除當(dāng)前源表以外的其他源表于步驟S51得到的一階中間表中，獲取與當(dāng)前源表享有相同健值的所有一階中間表，并將其記為一階備選中間表；

在除當(dāng)前源表和一階配對(duì)表以外的其他源表中，獲取與當(dāng)前源表在步驟S51得到的一階中間表享有相同健值的所有源表，并將其記為二階備選源表；

分別獲取當(dāng)前源表與各一階備選中間表的等值連接代價(jià)、當(dāng)前源表在步驟S51得到的一階中間表與各二階備選源表的等值連接代價(jià)，將最小等值連接代價(jià)對(duì)應(yīng)的一階備選中間表或二階備選源表作為與當(dāng)前源表進(jìn)行等值連接的二階配對(duì)表，并將該等值連接關(guān)系記為二階表達(dá)式；

S53：以此類推，分別將各源表作為當(dāng)前源表，在其他源表于上一次連接更新操作得到的中間表中找出與當(dāng)前源表享有相同健值的中間表，然后獲取找出的中間表與當(dāng)前源表的等值連接代價(jià)；同時(shí)，在除當(dāng)前源表和已與當(dāng)前源表建立等值連接關(guān)系的源表以外的其他源表中，找出與當(dāng)前源表在上一次連接更新操作得到的中間表享有相同健值的源表，然后獲取找出的源表與當(dāng)前源表于上一次連接更新操作得到的中間表的等值連接代價(jià)；最后獲取本步驟得到的最小值等值連接代價(jià)對(duì)應(yīng)的表達(dá)式，直到獲取各源表的連接關(guān)系表達(dá)式。