科學工作流中的正則查詢與關(guān)鍵字檢索技術(shù)研究.pdf

1、隨著計算機技術(shù)的日新月異和自然科學領(lǐng)域的不斷發(fā)展，科學工作流作為面向數(shù)據(jù)的工作流旨在利用計算機技術(shù)幫助人們解決科學實驗的數(shù)據(jù)再現(xiàn)和有效性驗證等問題，并進一步減輕科學實驗設(shè)計與分析的人力成本。作為一個剛剛起步的新研究領(lǐng)域，需要探索其具體應(yīng)用場景，歸納應(yīng)解決的實際問題。
　　本文正是在這種背景下，調(diào)研問題的應(yīng)用場景與實際需求，從最基本的科學工作流建模開始，研究科學工作流中數(shù)據(jù)起源正則查詢與關(guān)鍵字檢索的若干關(guān)鍵問題。一方面，現(xiàn)有科學工作

2、流中數(shù)據(jù)起源研究停留在可達性查詢階段，主要回答“某數(shù)據(jù)點d1是否依賴于數(shù)據(jù)點d2?”等類似問題。本文研究更為復(fù)雜的查詢——正則查詢，回答諸如“某數(shù)據(jù)點d1是否經(jīng)過技術(shù)a1或者技術(shù)a2重復(fù)處理過，然后由技術(shù)s處理過的，最終輸出數(shù)據(jù)d2?”等問題，這個查詢可以由正則查詢R=(a1|a2)*.s.(_)*表征。另一方面，科學工作流中的關(guān)鍵字檢索不同于普通的文本檢索，需要考慮科學工作流模式構(gòu)建科學工作流運行實例的表征能力?？茖W工作流中的關(guān)鍵字檢

3、索是對科學工作流模式共享庫進行檢索。科學工作流模式庫中科學工作流模式的每個模塊（包括復(fù)雜模塊與原子模塊）都由一個或多個關(guān)鍵字標注。當用戶需要設(shè)計新的科學工作流時，可以通過輸入關(guān)鍵字對科學工作流模式共享庫進行檢索，進而可以重用部分共享庫中已有科學工作流模式或模塊，從而減輕實驗設(shè)計的人力成本。
　　本文對自然科學領(lǐng)域科學實驗中遇到的實際問題進行調(diào)研分析，在此基礎(chǔ)上，結(jié)合數(shù)據(jù)管理技術(shù)，對科學工作流中的正則查詢和關(guān)鍵字檢索兩大問題進行深入

4、研究，主要貢獻和創(chuàng)新包括:
　　第一，提出基于上下文無關(guān)包文法的科學工作流模型。基于上下文無關(guān)文法的科學工作流模型使用文法表征科學工作流模式，文法的語言對應(yīng)科學工作流運行實例。上下文無關(guān)圖文法用以描述科學工作流中的數(shù)據(jù)依賴關(guān)系并用于進行數(shù)據(jù)起源的正則查詢。而上下文無關(guān)包文法通過將科學工作流模塊的關(guān)鍵字建模到文法的產(chǎn)生式中，使得關(guān)鍵字檢索更為簡潔，關(guān)鍵字匹配的語義更為清晰。
　　第二，提出一種基于節(jié)點編碼的科學工作流數(shù)據(jù)起源正

5、則查詢方法。本文提出的正則查詢方案基于一類特殊查詢——穩(wěn)定正則查詢。將點對點穩(wěn)定查詢的時間復(fù)雜度降低到常數(shù)級，是最優(yōu)算法;將多點穩(wěn)定查詢的時間復(fù)雜度做到僅與輸入節(jié)點表的大小有關(guān)而與數(shù)據(jù)起源圖的大小無關(guān)，附加地將多點可達查詢的時間復(fù)雜度降低到線性于輸入輸出，是最優(yōu)算法;最后本文將穩(wěn)定正則查詢擴展到通用正則查詢，顯著地提升了查詢效率。
　　第三，提出一種新型的科學工作流關(guān)鍵字檢索方案。本文定義了科學工作流中關(guān)鍵字檢索的匹配語義，并將上