跳到主要內容

臺灣博碩士論文加值系統

(3.234.211.61) 您好!臺灣時間:2021/10/18 17:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:余美伶
研究生(外文):Mei-Ling Yu
論文名稱:利用區間索引有效處理DAG之路徑可達性查詢
論文名稱(外文):Efficient DAG Reachability Query Processing Using Nested Intervals
指導教授:陳耀輝陳耀輝引用關係
指導教授(外文):Yaw-Huei Chen
學位類別:碩士
校院名稱:國立嘉義大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:94
語文別:中文
論文頁數:85
中文關鍵詞:路徑可達性測試巢狀式區間索引生成樹遞移封包矩陣以角色為基礎的存取控制以資料夾為基礎的存取控制多重繼承
外文關鍵詞:testing reachabilitynested intervalsspanning treetransitive closure matrixRBACDBACmultiple inheritance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:276
  • 評分評分:
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
在諸多領域中,有許多的應用都是架構在有向無循環圖形上,所以系統必須經常地去判斷檢查在圖形中的任意兩節點是否有路徑可到達。為了使系統能夠有效地處理路徑可達性的查詢問題,本論文運用了區間索引的編碼方式將遞移封包矩陣中的路徑關係記錄下來,並且發展出一套測試方法能夠有效地判斷節點彼此間的路徑關係為何。主要的概念是先對有向無循環圖形任意取出一棵生成樹,並且利用數值區間索引對生成樹做編碼,接著再將圖形中未走訪到的非樹邊路徑關係記錄在遞移封包矩陣中。若是兩節點間的路徑關係可藉由生成樹的樹邊路徑到達,則系統僅需比對節點的區間索引便可得知兩節點彼此的包含關係。若是兩節點彼此間要透過樹邊路徑與非樹邊路徑才能到達,則系統除了比對索引之外還要檢查遞移封包矩陣中相關的非樹邊路徑端點(Tails與Heads)關係記錄方能知道結果。本研究所提出的方法只需要常數時間就可以完成圖形中任意兩節點的路徑關係測試,另外對於圖形結構的新增與刪除處理,也只需要針對局部的範圍作路徑關係記錄調整,不必對整個結構重新編碼。最後,本論文還以結合角色與資料夾的存取管控機制為應用,說明在多重繼承結構中如何能夠有效且精確地檢測出使用者與物件彼此間的權限存取關係。
Testing reachability between nodes in a graph is a frequently asked query in many applications that would be modeled using directed acyclic graph (DAG). In order to support efficient reachability testing on DAGs, this thesis devises a new encoding scheme to record the transitive closure information and develops an efficient strategy to test the reachability relationships between nodes. The main idea is to label a spanning tree with numerical intervals first and then generate a transitive closure matrix for the tails and heads of non-tree edges. The existence of a tree edge path between two nodes can be verified by a containment relationship between the label intervals. On the other hand, testing the reachability through both tree and non-tree edges needs to use the numerical intervals to identify the relevant tails and heads and examine their relationships in the transitive closure matrix. The testing operations would be done in constant time, and moreover, the proposed approach supports updates to the underlying graph by locally adjusting the encoding information. In addition, the thesis proposes an access control mechanism that combines role-based and directory-based access control (RBAC and DBAC) mechanisms, and takes the mechanism as an example to test accessible relationships between users and objects, which would have multiple inheritance relationships among them.
第一章 緒論 1
1.1 研究動機、背景與目標 1
1.2 論文架構 4
第二章 相關研究 5
2.1 Bit-Vector方法 5
2.2 Interval方法 9
2.3 其他方法 18
第三章 利用區間索引查詢路徑關係 21
3.1生成樹(Spanning Tree) 22
3.1.1數值區間索引(Numerical Intervals) 22
3.1.2樹邊與非樹邊(Tree and Non-tree Edges) 23
3.3 非樹邊端點(Heads and Tails) 25
3.4 遞移封包矩陣(Transitive Closure Matrix) 27
第四章 有效地記錄與比對路徑關係 30
4.1 代理節點範圍值(Representing Nodes Ranges) 30
4.2 矩陣記錄 37
第五章 圖形結構的更新處理 42
5.1 新增處理 42
5.1.1新增節點 42
5.1.2新增樹邊 43
5.1.3新增非樹邊 44
5.2 刪除處理 55
5.2.1刪除節點 55
5.2.2刪除樹邊 58
5.2.3刪除非樹邊 61
第六章 時間與空間複雜度分析 63
6.1 圖形取樹並編碼 63
6.2 遞移封包矩陣製作 64
6.3 代理節點範圍值 64
6.4 HTM矩陣製作 65
6.5 DAG之路徑可達性查詢 66
6.6 更新處理 69
6.6.1 新增處理 69
6.6.2 刪除處理 70
第七章 應用:以結合RBAC與DBAC為例 72
7.1 以角色為基礎之存取控制(RBAC) 73
7.2 以資料夾為基礎之存取控制(DBAC) 75
7.3 結合RBAC與DBAC的存取控制 76
7.4 記錄與比對權限 77
第八章 結論與未來研究 81
參考文獻 83
[1] R. Agrawal, A. Borgida, H. V. Jagadish, “Efficient Management of Transitive Relationships in Large Data and Knowledge Bases,” Proceedings of ACM SIGMOD International Conference on Management of Data, 1989.
[2] H. Ait-Kaci, “An Algebraic-semantic Approach to the Effective Resolution of Types Equations,” Theor. Comput. Sci. vol. 45, pp. 185-215, 1986.
[3] H. Ait-Kaci, R. Boyer, P. Lincoln, R. Nasr, “Efficient Implementation of Lattice Operations,” ACM Transactions on Programming Languages and Systems, Vol. 11, No. 1, pp. 115-146, 1989.
[4] Y. Caseau, “An Object-oriented Deductive Language,” Annals of Mathematics and Artificial Intelligence, 1991.
[5] Y. Caseau, “Efficient Handling of Multiple Inheritance Hierarchies,” Proceedings of the International Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 271-287, 1993.
[6] E. Cohen, E. Halperin, H. Kaplan, U. Zwick, “Reachability and Distance Queries via 2-hop Labels,” Proceedings of the 13th ACM-SIAM SODA, 2002.
[7] Y.-H. Chen, J.-L. Tsai, M.-L. Yu, M.-C. Ho, “Managing Multi-version XML Documents Using Relational Databases,” Proceedings of IACIS Pacific Conference, 2005.
[8] V. Christophides, D. Plexousakis, M. Scholl, S. Tourtounis, “On Labeling Schemes for the Semantic Web,” WWW, 2003.
[9] G. Coulouris, J. Dollimore, M. Roberts, “Role and Task-based Access Control in the PerDiS Groupware Platform,” Proceedings of the 3rd ACM Workshop on Role-Based Access, 1998.
[10] P. F. Dietz, “Maintaining Order in a Linked List,” Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982.
[11] A. Fall, “Sparse Term Encoding for Dynamic Taxonomies,” Proceedings of the Fourth International Conference on Conceptual Structures, 1996.
[12] D. Ganguly, C. Mohan, S. Ranka, “A Space-and-time-efficient Coding Algorithm for Lattice Computations,” IEEE Transactions on Knowledge and Data Engineering, pp. 819-829, 1994.
[13] J. Y. Gil, Y. Zibin, “Efficient Subtyping Tests with PQ-Encoding,” ACM Transactions on Programming Languages and Systems, Vol. 27, No. 5, pp. 819-856, 2005.
[14] F. Hansen, V. Oleshchuk, “SRBAC: A Spatial Role-Based Access Control Model for Mobile Systems,” Proceedings of Esorics Nordsec, 2003.
[15] H. He, H. Wang, J. Yang, P.S. Yu, “Compact Reachability Labeling for Graph-Structured Data,” Proceedings of Conference on Information and Knowledge Management, 2005.
[16] H. V. Jagadish, “A Compression Technique to Materialize Transitive Closure,” ACM Transactions on Database Systems, Vol. 15, No. 4, 1990.
[17] J. B. D. Joshi, E. Bertino, U. Latif, and A. Ghafoor, “A Generalized Temporal Role-Based Access Control Model,” IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 1, 2005.
[18] Q. Li, B. Moon, “Indexing and Querying XML Data for Regular Path Expressions,” Proceedings of the 27th International Conference on Very Large Data Bases, 2001.
[19] A. Ott, S. Fischer-Hübner, “The Rule Set Based Access Control (RSBAC) Framework for Linux,” http://www.rsbac.org/documentation/, 2004.
[20] J. S. Park, K. P. Costello, T. M. Neven, J. A. Diosomito, “A Composite RBAC Approach for Large, Complex Organizations,” Proceedings of Symposium on Access Control Models and Technologies, 2004..
[21] R. S. Sandhu, E. J. Coyne, H. L. Feinstein, C. E. Youman, “Role-Based Access Control Models,” IEEE Computer, Vol. 29, No. 2, 1996.
[22] G. Saunders, M. Hitchens, V. Varadharajan, “Role-Based Access Control and the Access Control Matrix,” ACM SIGOPS Operating Systems Review, 2001.
[23] I. Tatarinov, S.D. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, C. Zhang, “Storing and Querying Ordered XML Using a Relational Database System,” Proceedings of ACM SIGMOD International Conference on Management of Data, 2002.
[24] H. Wang, J. Cao, Y. Zhang, “A Flexible Payment Scheme and Its Role-Based Access Control,” IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 3, 2005.
[25] H. Wang, R. H. He, J. Yang, P. S. Yu, J. X. Yu, “Dual Labeling: Answering Graph Reachability Queries in Constant Time,” Proceedings of the 22nd International Conference on Data Engineering, 2006.
[26] M. L. Yu, Y. H. Chen, L. C. Chen, “Role and Directory Based Access Control for E-learning Systems,” Technical Report, Department of Computer Science and Information Engineering, National Chiayi University, 2005.
[27] 李銘桀, 針對多重路徑查詢建構XML文件索引機制, 碩士論文, 國立嘉義大學資訊工程研究所, 2002.
[28] 陳耀輝, 蔡政霖, 余美伶, 何銘啟, “用關聯式資料庫儲存多版本XML文件,” 第三屆數位典藏技術研討會, 2004.
[29] 余美伶, 曾柏銜, 黃文彬, 陳耀輝, 林菁, “結合角色和資料夾的存取控制模組設計-以數位學習系統為例,” 第一屆台灣軟體工程研討會, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文