科學工作流中的正則查詢與關鍵字檢索技術研究.pdf

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

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

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

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

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