[發明專利]使用優化的位圖表示來管理大規模關聯集

有效

• 申請號: 201880006890.3
• 申請日: 2018-02-20
• 公開（公告）號: CN110178128B
• 公開（公告）日: 2023-05-12
• 發明（設計）人: R·拉斐爾;R·德塞;G·瓦倫西亞;J·L·佩雷茲;M·加亞潘迪安;I·V·梁
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 酆迅;李崢宇

處理數據集的數據庫查詢包括將整數空間中的唯一標識符分配給數據內的每個實體，并創建一個或多個實體集，每個實體集屬于數據內的相應實體。然后，在磁盤上為每個實體集生成表示，其中每個表示包含并適合于對應集內的實體的唯一標識符的范圍，并指示該對應集內的實體的存在。最后，基于每個實體集的表示來處理查詢以檢索滿足查詢的數據，其中該表示為關聯和解離操作提供恒定時間，該操作是僅附加操作，在查詢時具有延遲合并以及自動過濾已刪除和重復的實體。

技術領域

本發明涉及關聯和解離數據集，更具體地，涉及利用位圖表示來管理關聯和解離數據集。

背景技術

企業內容管理中的常見問題是將大量的第一類型實體與一個或多個第二類型實體相關聯。例如，在法律領域，公司或組織通常需要將大量文檔(例如電子郵件、報告、通知、備忘錄等)與大量人員(例如員工、承包商、經理等)或一個或更多其他實體(例如法律事務、審計、組織單位等)相關聯。

關聯集是兩個實體之間的一對多或多對多關系。例如，員工發送和接收電子郵件可以建模為員工與文檔之間的關聯。這里，與一個員工關聯的所有文檔集可以被視為關聯集。一封電子郵件的所有發件人和收件人的集合也可以被視為關聯集。如果公司涉及某種訴訟，并且被要求出示與一組員工(或訴訟中的“利益相關者”)相關的所有文檔，生成所需文件集要求對關聯進行建模和持久化，以便快速準確地檢索所需文檔。

一旦關聯集變得非常大就會變得非常難以管理，具有數十萬員工和數億文檔的大公司通常是這樣的情況。因此，對于大公司而言，文檔、法律事務、保管人、通知等的數量可能非常大，并且它們之間關聯的數量可能更大。存儲和查詢這些關聯集是現代企業中的難題，并且需要能夠正確且有效地大規模執行的解決方案。

在典型的解決方案中，第一標識號用于表示實體，而第二標識號可用于跟蹤其與其他實體的每個關聯。例如，電子郵件和雇員之間的關聯可以被建模為電子郵件的ID和雇員的ID之間的關系。但是這可能導致非常大量的關系，導致在發現過程的各個階段期間需要存儲、管理、檢索和查詢的大量關系對象。管理、存儲、檢索和查詢這些大型關系對象可能非常昂貴。對于擁有數萬名員工和數百萬文檔的大型公司或組織，關聯集的規模變得非常大。如果采用傳統方法，這些大型關聯集的持久性可能會占用大量存儲空間。

除了存儲成本之外，在創建和管理這些關聯所花費的時間方面也存在成本。如果使用事務完成關聯的創建，則在實現期間需要保持的鎖可能使系統不可用于可能需要同時發生的其他操作(例如，從關聯集添加或移除實體)。

另外，與存儲大關聯集的問題直接相關的是從眾多其他關聯集中檢索感興趣的關聯的問題。要查詢n元關聯，可能需要二進制關聯集的n路連接(join)。這需要快速、靈活和可擴展的解決方案。

傳統數據庫存儲使用鏈接表來表示和查詢實體之間的關聯。以這種方式存儲、索引和查詢關聯不是最佳的，并且可能導致涉及關聯的用戶查詢的響應時間長，尤其是在同時創建和管理關聯的情況下。如果提供了事務性保證，則在創建或刪除操作發生時，大部分數據庫可能無法使用，這可能使整個系統在很長時間內即使對于只讀查詢也無法使用，例如幾小時甚至幾天。

例如，面臨訴訟的公司通常需要收集與案件相關的數據。這通常需要創建案例、關聯大量(相關)文檔并將這些文檔(可能是數百萬個)文檔置于保留狀態。在同一事務中，還可能需要將大量保管人與案件相關聯。以可在發生錯誤時回滾系統的方式管理此類事務可能非常具有挑戰性。同樣，如果案件需要刪除，同一事務可能涉及將大量文件和保管人與案件分離并釋放任何保留。要在保證事務語義的同時有效地這樣做是很困難的。

如果文檔的壽命超過其法定時效(例如，取決于聯邦法律、州法律、當地市政法律、公司政策等)，則可以創建、修改甚至刪除關聯。因此，管理這些關聯集需要能夠隨著時間的推移處理這些更改，而不會顯著降低查詢性能。

發明內容