【作者】 左万利；

【导师】 孙吉贵；

【作者基本信息】 吉林大学 ， 计算机软件与理论， 2005， 博士

【摘要】 本文研究了主动数据库的理论问题,具体包括:(1)对ADBMS 的产生历史、发展现状、原型系统等进行了分析,明确了尚未完全解决的理论问题;(2)研究了事件描述语言,通过引入一元时序算子,将事件代数拓展到时序空间,并根据最近发生事件消耗语义提出了标志取代Petri 网TR-Petri,用TR-Petri 网解决了复合时序事件的检测问题;(3)研究了主动规则执行终止性问题,发现了基于TG 和AG 的主动规则终止性静态分析算法的错误,并通过定义触发可达修改了原算法。进一步,引入了DG 图,并结合TG 图和AG 图定义了关联图RG,基于RG 给出了更为精确的主动规则终止性静态分析算法;(4)研究了主动规则执行语义问题,根据immediate 耦合方式的语义,提出了传递冲突和完可交换的概念,解决了多种耦合方式下主动规则正确性和合流性问题。文中给出了支持多种耦合方式的主动规则正确执行的形式化语义,证明了任何正确执行必然导致合流性执行结果;(5)根据改进和扩展的嵌套事务模型,给出了支持完整耦合方式集的主动规则合流性调度算法和并发控制算法,以及基于事务森林的高效死锁检测与恢复算法;(6)在OODB 环境上建立了一个主动数据库原型系统Petri-AOODBMS,对文中提出的核心算法进行了验证。更多还原

【Abstract】 Active database management system (ADBMS) is a natural extension and enhancement of traditional passive database, with a salient feature of being reactive in response to event inside or outside of the DBMS system. The reactive nature of ADBMS is achieved by the definition and processing of active rules, which is also called ECA (event-condition-action) rules. When event occurs and condition holds, action will be executed automatically by the ADBMS system. Active DBMS can automatically and effectively maintain data integrity and consistency constrains, satisfying advanced and real-time database applications. The idea of active database can be traced back as early as the later 70’s, in QBE, CODASYL, and System R. The sophisticated pioneer work in active database is HiPAC of the later 80’s, in which the term active database is nailed. There has been a surge of research in active database area in the early and later 90’s, with substantial research results published and more than 10 prototype active database systems developed. The most influential institutions contributed to the area include The CCA Company (HiPAC project), The University of Florida (Sentinel), University of Zurich (SAMOS), IBM Almaden Research Center (Satrburst), etc. Domestic institutions devoted to active database area include Wuhan University, Huazhong Poly-technical University, Fudan University, Zhejiang Yniversity, Shandong University, Harbin Poly-Technical University and Jilin University. Although quite a few active database prototype systems have been developed, and some simplified (restricted) active rules have been integrated into commercial DBMS in the form of triggers or assertions, it is too early to say that active DAMS is mature. This not only lead to remarkable divergence in active database semantics, but also restricted active database applications. As such, top-level international database conferences, such as VLDB2006, still solicit active database contributions as one of the main topics. The ultimate goal of this dissertation is to clarify problems inadequately or incompletely solved in the area, conduct an in-depth study in related topics towards the goal of establishing a complete and sound theoretical foundation of active database theory. The work reported in this dissertation is based on Petri net. Following a comprehensive survey of the state-of-the art in ADBMS, theoretical problems inadequately or incompletely solved in the area are identified one by one, which determined directions of our research efforts. Instead of building rule and prototype systems to start, the ongoing study is mainly devoted to theoretical problems, with emphasis on temporal event-rule language extension, incremental composite event detection, termination analysis, formal semantics of active rule execution supporting multiple coupling modes, rule scheduling and concurrency control of active rule execution in the framework of database transactions, deadlock detection and recovery algorithms. The main contributions and research results are of the following: (1) A comprehensive survey in active database research is reported, which covers active database history, development process, terminologies and techniques, as well as current research status. Our emphasis is placed on theoretical problems remain to be resolved, which constitute our further research background and foundation. (2) The syntax and semantics of event language is investigated. Three novel unary event operators, pre, at, post are proposed, which can be arbitrarily nested with other event operators such as sequential, or, and, not, etc to express any complex temporal relations. Based on this, temporal event algebra and temporal event language are defined, along with time semantics for any event expression, which extends traditional event language to temporal space, realizing the Stella Gatziu’s hypothesis of regarding event as a specific point in time. Some good properties of the extended temporal event algebra are also proved. (3) Petri net is studied for adoption in temporal event detection. In accordance with event consumption semantics, token replace Petri net (Token Replace Petri net, TRPN) is defined. The extended TR Petri Net can note only detect the occurrence of composite event, but also forward the time when the component event occurs. This not only provides a quantitative basis for rule scheduling, but also initiates a new way for confluent rule execution. Because of the existence of auxiliary place in TR Petri Net, the algorithm is incremental in nature, efficient in implementation. (4) In the area of rule termination, we analyzed existing algorithm based on triggering and activation graphs, and draw conclusion that current algorithms are conservative. We first identified an incorrect result in static rule termination analysis based on triggering graph (TG) and activation graph (AG) in the presence of rule priorities. By introducingtriggering reachable (instead of reachable of TE and AE), we corrected the current analysis result. Furthermore, based on the observation that the execution of one rule may definitely falsify another rule’s condition, a new type of graph, named deactivation graph (DG), is introduced. By integrating TG, AG and DG, a more generalized graph, named Relationship graph (RG) is defined. The most accurate termination analysis algorithm based on RG is thus proposed. Some non-termination rule set estimated by TG and AG can be judged as termination, avoiding false alarms. (5) In rule execution semantics aspect, we analyzed the incompleteness of current research results in the area: existing confluence algorithms only support deferred (not immediate as some paper claim) coupling mode, whereas execution models supporting multiple coupling modes (immediate, deferred, detached, and their combination) don’t guarantee confluent execution result. In order to handle various coupling modes properly, we first introduced the concepts of transitive dependency (indirect dependency) and totally commute. It is first identified that whenever rule triggering involves rules with immediate or/and detached coupling mode, not only direct, but also indirect dependencies need to be declared, and thus relative priorities between indirectly conflicting rule pairs need to be specified. Based on the above, this thesis first established a formal correct rule execution semantics in the form of sequential rule processing, and proved that any correct rule execution leads to the same final database state (confluent). (6) In rule execution model, we put forward the notion of hierarchical serializability (nested serializability), and proved that nested serializability is equivalent to correct rule execution. Under the framework of extended nested database transactions, a confluent rule scheduling and concurrency control algorithm supporting multiple coupling modes with maximal parallelism is established, along with efficient deadlock detection and recovery algorithms based on transaction tree and transaction forest. (7) A framework of active database system Petri-AOODBMS is proposed. The system integrates with an open OODBMS system. Active components and their interaction with underlying database system are explained. Most theoretical algorithms proposed in this dissertation are tested on the prototype system. It is expected that the present work consummate active database theory, constituting a significant step forward towards a complete and sound active database theory for further enrichment in commercial database management systems.更多还原