资料库反向工程中包含相依性资料探勘之验证Validation and Data Mining

資料庫反向工程中包含相依性資料探勘之驗證／王學亮陳郁青洪宗貝錢炳全資料庫反向工程中包含相依性資料探勘之驗證王學亮、陳郁青、洪宗貝*錢炳全義守大學資管系義守大學資工系{slwang|m883326m|tphong}@[e-mail]摘要本文提出一個結合資料探勘之資料庫反向工程之架構以及利用SQL功能之包含相依性資料探勘之驗證方法。資料庫反向工程之目的是要分析現存的資料庫並從中粹取出其系統之抽象表達式，以便維護及重新設計該資料庫，提升企業中資料庫的使用效能。利用資料探勘的技術挖掘資料之相依性可進一步的提升資料庫反向工程自動化的程度。針對資料庫中包含相依性之探勘，本研究提出三個基於SQL查詢的驗證方法。分析結果顯示本研究的方法具備較少的資料庫查詢次數及計算量。關鍵字：資料庫反向工程，資料探勘，關聯式資料庫，包含相依性ValidationandDataMiningofInclusionDependenciesinDatabaseReverseEngineeringShyue-LiangWang,Yu-ChingChen,Tzung-PeiHongBeen-ChianChienDepartmentofInformationManagementDepartmentofInformationEngineeringI-ShouUniversityI-ShouUniversity{slwang|m883326m|tphong}@[e-mail]tsadata-mining-baseddatabasereverseengineeringframeworkaswellasvalidationmethodsusingSQLfunctionsforthediscoveryofinclusiondependencies.Databasereverseengineeringisaprocessthatobtainsdomainsemanticsaboutalegacydatabase.Itisapartofdatabasemaintenanceandredesignworkforbetterusageofcorporateresources.Integrationofdataminingtechniqueswithdatabasereverseengineeringcanfurtherautomatetheprocess.Threevalidationmethodsfortheminingofinclusiondependenciesarethusproposed.Complexityanalysisshowsthattheproposedmethodsrequirelesscomputationtimeanddatabasequeries.Keyword:databasereverseengineering,datamining,relationaldatabase,inclusiondependency*現任職國立高雄大學電機系1資訊管理展望第3卷第2期民國九十年九月壹、緒論許多組織經過多年的營運，累積了大量的資料庫。這些資料庫的一個主要問題是其資料的含意已被遺忘，因此其資料間之關係已無從得知。此問題造成組織內無法有效利用其資料庫並且無法正確的維護其資料。而要提升對資料瞭解的一個方法是提高資料的抽象層次，並以概念模式來表達資料庫中的資料語意（datasemantics），所以必須要對其進行資料庫反向工程（DatabaseReverseEngineering；DBRE）之處理。資料庫反向工程之主要目標就是要改善對資料庫中，資料語意的瞭解程度，以便改進系統之維護或重新設計新的資料庫系統。已有許多研究提出從階層式資料庫、網路資料庫或關聯式資料庫中粹取出延伸之實體關聯（ExtendedEntityRelationship；EER）模式[2-3,6-8,11-18]。而資料庫反向工程的處理過程，基本上可分為兩大步驟（如圖一）：（1）從現有資料庫中粹取出資料語意，例如從資料庫綱目（schema）、資料記錄及應用程式中粹取主鍵（primarykey）、外鍵（foreignkey）、功能相依性（functionaldependency；FD）、包含相依性（inclusiondependency；IND）等資料語意，即資料結構粹取（datastructureextraction），（2）將粹取出之語意轉換成較高層次之概念模式以表達之，例如將第三正規化（3NF）之關聯資料庫轉換、對映（mapping）成延伸之實體關聯模組，即資料結構概念化（datastructureconceptualization）。圖一、資料庫反向工程之主要處理過程以關聯式資料庫而言，大部分資料庫反向工程的方法[2-3,6-8,11-18]，事先假設資料語意為已知（如專家使用者提供之），因此其研究著重在轉換資料結構概念化的過程，但此種假設往往是不夠實際的。另外一些資料庫反向工程的方法則稍微放寬限制，例如假設部分資料語意為未知，利用資料探勘（datamining）的方式，探勘出其所需的資料語意，然後再利用這些資料語意進行資料結構概念化，轉換成概念模組，如Petit[18]、Ito[6]及Chiang[2-3]…等方法，但是這些研究只是進行簡單的資料語意探勘，並未利用現有的資料庫管理系統之功能來進行資料語意的粹取。因此在本研究中，首先提出一個資料庫反向工程的方法步驟，希望能將其資料語意限制放寬到原始資料庫為第一2資料庫反向工程中包含相依性資料探勘之驗證／王學亮陳郁青洪宗貝錢炳全或第二正規化（1NF，2NF），並且除了專家之啟發式建議及使用者互動之外，別無其他假設。而且為了提高資料庫反向工程處理過程之自動化，本研究引進資料探勘之方法並使用資料庫管理系統（DatabaseManagementSystem；DBMS）的功能來進行資料語意之探勘。之後，利用專家建設之啟發式規則，建議使用者選擇適用之語意關係以進行正規化之處理。資料相依性（datadependencies）為關聯式資料庫中用來描述資料語意或資料完整性限制（integrityconstraints）的一種方法，依定義的不同又分成功能相依性、包含相依性、多值相依性（multi-valueddependency）等。目前已有許多研究在資料庫中探勘功能相依性[1,4-5,9-10]，例如Huhtala等人[4-5]提出逐層搜尋(level-wise)的演算法，他們從關聯式資料庫中利用資料探勘的方式，尋找出所有可能的最小(minimal)且非明顯(non-trivial)的功能相依。另外包含相依性R(X)⊆S(Y)為資料綱目R中之屬性X的值完全包含於另一資料綱目S中之屬性Y的值，其一般是用來定義資料庫中資料綱目彼此之間的關係，讓組織中不部同部門的資料表格能夠緊密結合，共享資料，避免資料庫缺乏彈性、產生不一致的資料及產生多餘的重複性。若能從已存在之資料庫中發掘出資料包含相依性，則有助於資料庫管理師之資料維護、更新與再設計。靜態資料庫是指資料庫之資料固定不變，而動態資料庫是指資料庫之資料會隨時變動，例如新增、刪除或修改值組（tuple）。目前已有許多研究[1-3,6-7,9,14-16]探討在資料庫上探勘包含相依性之各種方法，基本上探勘包含相依性可分成搜尋及驗證兩個工作。在包含相依性的驗證方面，已有Bell&Blockhausen[1]、Chiang[2-3]及Petit[14-16]等學者探討如何使用資料庫管理系統中SQL的功能來驗證屬性之間包含相依性之情況，但其計算量及對資料庫的存取次數皆不甚經濟。因此在本研究中，我們將針對靜態資料庫，改善Bell&Blockhausen[1]的方法，提出一個較有效率的聯集為主之驗證方法。此外本研究認為資料庫之資料會隨時變動，因此進一步的對動態資料庫（新增值組的狀況），依據事先假設的不同已知，提出兩個漸增式包含相依性之驗證方法：一為包含相依性為主之驗證方法，另一為屬性值總數為主之驗證方法。並以計算量的複雜度對所提之三種方法與Bell&Blockhausen[1]的方法作一分析比較。結果顯示本研究所提之方法需要較少的計算量。本文共分為五節。第二節本研究將對資料庫反向工程及探勘包含相依性之各種方法作一回顧探討。第三節提出一個結合資料探勘的資料庫反向工程的方法步驟，且以例子來說明其方法架構。第四節對靜態及動態資料庫提出三個包含相依性之驗證方法，並根據計算量的複雜度作一分析比較。最後在第五節作一簡短之結論。貳、相關文獻本節將對資料庫反向工程的各種方法，及包含相依性的各種資料探勘方法，作一簡短之回顧。首先本研究回顧七種資料庫反向工程的方法[2-3,6-8,11-18]。大部分資料庫反向工程的方法，事先假設資料語意為已知。其研究著重在轉換資料結構概念化的過程。例如：Johannesson[8]的方法主要是以明確的規則說明轉換的步驟，但是事先的輸入（所有的主鍵、包含相依性等）必須是非常完整的。Markowitz等人[11]之方法是從BCNF（Boyce-CoddNormalForm）開始來做轉換，且事先輸入的資料非常多，但是其主要的3資訊管理展望第3卷第2期民國九十年九月貢獻為資料表格間對映的關係定義非常明確。PremerlaniandBlaha’s[17]方法是將資料綱目轉換成以物件導向為主的形式（ObjectModellingTechnique），主要之貢獻為提供指導手冊並使設計的製作能夠最佳化，但是處理的過程需要使用者大部份的參與。Signore等人[18]方法的轉換是根據一些線索來處理稀有的製作技術，且參與的使用者必須要有充足的知識。但上述方法之假設往往是不夠切合實際。另外一些資料庫反向工程的方法則稍微放寬限制，例如假設部分資料語意為未知，利用資料探勘的方式，探勘出其所需的資料語意，然後再利用這些資料語意進行資料結構概念化，轉換成概念模組，例如：Ito等人[6]之方法是先從資料表格中推論出功能相依性，將資料綱目正規化，再找出包含相依性，轉換對映出資料綱目間二元的（binary）關係。Petit等人[14-16]之方法的事先假設並無特別的限制，他們利用相等連結（equi-join）的方式找包含相依性及功能相依性，再做資料綱目的正規化及其之間的對映。此兩種方法皆假設可從資料庫中之資料去尋找出部份之功能相依性或包含相依性。Chiang等人[2-3]之方法則先將資料表格及屬性做分類，再利用SQL的方法探勘包含相依性，並轉換成資料綱目之間的對映。此類之研究，其方法主要是進行資料庫反向工程中資料結構粹取和概念化兩個過程。事實上，進行資料庫反向工程的研究很多，但是大部分之研究探討多集中於提出如何將已知之資料語意對映到各類之實體關聯圖，較未著重在資料庫反向工程處理中前面的資料語意粹取部份，大部分之工作往往假設資料語意為已知，或只是進行簡單的資料語意探勘。因此，在第三節中，本研究希望能將其資料語意限制依據實際的情況，放寬到原始資料庫，為第一或第二正規化，並且除了專家之啟發式建議及使用者互動之外，別無其他輸入假設，且修正提議出結合資料探勘的資料庫反向工程之方法架構。目前已有許多研究針對在靜態資料庫中探勘包含相依性之方法進行探討[1-3,6-7,9,14-18]，其又分為三大類：（1）集合導向為主（set-oriented-based）之研究[1-3,14-16]，例如使用SQL查詢語言，（2）非集合導向為主之研究[6-7]，及（3）啟發式為主之研究[2-3,7]。非集合導向為主之方法直接對資料庫存取資料，所以能較有效率的探勘包含相依性，但是真實的資料庫資料量通常較大，且大多利用資料庫管理系統的功能來進行存取，因此本研究主要針對集合導向為主之探勘包含相依性的文獻作一探討。包含相依性之探勘方法又分成包含相依性之驗證與搜尋。在包含相依