leaps算法ruleenginealgorithm资源-CSDN文库

5星 · 超过95%的资源需积分: 34 106 浏览量 2009-06-26 10:38:55 上传评论收藏 49KB PDF 举报

### LEAPS算法：规则引擎模式算法的深度解析在IT领域，规则引擎是处理业务逻辑、决策支持系统的关键组成部分，而LEAPS（Lazy Evaluation Algorithm for Production Systems）算法则是这一领域内的前沿技术。由唐·巴托里（Don Batory）在德克萨斯大学奥斯汀分校计算机科学系所提出的LEAPS算法，旨在为OPS5规则集提供最先进的生产系统编译器，以实现最快的顺序执行。 #### LEAPS算法的核心优势 LEAPS算法之所以能够产生最快的OPS5规则集的可执行版本，关键在于其对复杂数据结构和搜索算法的依赖，这些技术大大加速了规则处理的速度。实验结果表明，与OPS5解释器相比，LEAPS产生的执行时间可以快两个数量级以上，这得益于其高效的数据结构和算法设计，特别是针对规则触发率的优化。 #### 数据结构与算法理解的挑战然而，LEAPS的数据结构和算法因其复杂性而难以理解，部分原因在于传统的关系数据库概念（如关系和选择-投影-连接操作）无法充分表达LEAPS算法中的关键懒惰评估特性。为了克服这一障碍，本文将通过P2数据结构编译器的容器-游标编程抽象来解释LEAPS算法。 #### P2编程抽象：理解LEAPS的基础 P2数据结构编译器提供了四个核心编程抽象，对于理解LEAPS算法至关重要：游标（cursors）、容器（containers）、复合游标（composite cursors）和类型表达式（type expressions）。以下是对这些概念的深入解读： 1. **游标和容器** 游标是运行时对象，用于引用和更新容器中的元素。容器是一种数据结构，例如数组、二叉树或有序列表，它们包含一系列同类型的数据项。容器中的元素只能通过游标进行访问和修改，这种机制确保了数据的安全性和一致性。 2. **复合游标** 复合游标是多个游标的组合，允许同时操作和管理多个容器中的元素。这在处理复杂的规则引擎场景时特别有用，可以更高效地遍历和筛选多维数据。 3. **类型表达式** 类型表达式是用于描述数据类型的语法结构，它允许定义和操作复杂的数据结构，如数组、记录或自定义类型。在LEAPS算法中，类型表达式有助于定义和操纵规则引擎中涉及的各种数据类型，从而实现对规则的灵活处理。 #### LEAPS算法的重新实现通过将LEAPSalgorithms的概念转换为P2编程抽象，作者们不仅加深了对该算法的理解，还基于这些规格进行了RL（Reengineered-LEAPS）项目，验证了其实现的有效性。因此，本文不仅介绍了LEAPS算法的理论基础，还展示了如何利用P2数据结构编译器的抽象来重新实现这一先进算法，从而进一步推动了规则引擎技术和应用的发展。 LEAPS算法通过依赖复杂数据结构和搜索算法，在规则引擎的性能提升方面取得了显著成就。借助P2编程抽象的解释，我们不仅能够更好地理解LEAPS算法的工作原理，还能探索其在实际应用中的无限潜力，为IT行业中的决策支持系统和智能应用提供强大动力。

资源推荐

资源详情

资源评论

The LEAPS Algorithms

Don Batory

Department of Computer Sciences

The University of Texas

Austin, Texas 78712

Abstract

LEAPS is a state-of-the-art production system compiler that produces the fastest sequential execut-

ables of OPS5 rule sets. The performance of LEAPS is due to its reliance on complex data struc-

tures and search algorithms to speed rule processing. In this paper, we explain the LEAPS

algorithms in terms of the programming abstractions of the P2 data structure compiler.

1 Introduction

OPS5 is a forward-chaining expert system [McD78, For81]. LEAPS (Lazy Evaluation Algorithm for Pro-

duction Systems) is a state-of-the-art production system compiler for OPS5 rule sets [Mir90].

Experimen-

tal results have shown that LEAPS produces the fastest sequential executables of OPS5 rule sets; execution

times can be over two orders of magnitude faster than OPS5 interpreters. This phenomenal speedup is due

to the reliance of LEAPS on complex data structures and search algorithms to greatly increase rule ﬁring

rates. It is well-known that LEAPS data structures and algorithms are difﬁcult to comprehend; this is due,

in part, to the inability of relational database concepts (i.e., relations and select-project-join operators) to

capture critical lazy-evaluation features of LEAPS algorithms.

In this paper, we explain the LEAPS algorithms in terms of the container-cursor programming abstractions

of the P2 data structure compiler [Sir93, Bat93]. Our speciﬁcations of the LEAPS algorithms were used as

the basis for the RL (Reengineered-LEAPS) project [Bat94] and have been validated through implementa-

tion. Thus, this paper describes a reimplementation of LEAPS using P2. We begin by reviewing relevant

P2 abstractions.

2 P2 Programming Abstractions

There are four programming abstractions that are offered by P2 that are critical to the understanding of

LEAPS algorithms: cursors, containers, composite cursors, and type expressions. Each concept is

explained in the following sections.

2.1 Cursors and Containers

Many common data structures—arrays, binary trees, ordered lists—implement the container abstraction. A

container is a sequence of elements, where all the elements are instances of a single data type. Elements

can only be referenced and updated by a run-time object called a cursor (see Figure 1).

1. This research was supported in part by the Applied Research Laboratories at the University of Texas and Schlum-

berger.

2. Actually, OPS5c version 5 is the name of the production system compiler; LEAPS is the name of the algorithms.

We will use OPS5c/LEAPS and LEAPS interchangably in this paper.

The P2 programming language is a superset of C. P2 introduces statements for cursor and container decla-

rations, along with special operations on cursors and containers. An abbreviated declaration of a container

of EMPLOYEE_TYPE instances is shown below, along with declarations of a cursor (all_employees)

that references all elements of this container and another cursor (selected_employees) that refer-

ences only those elements whose deptno ﬁeld has the value 10:

// Declaration of the employee container.

container <EMPLOYEE_TYPE> employee;

// Cursor that references all elements in the employee container.

cursor <employee> all_employees;

// Cursor that references selected elements of employee container.

cursor <employee> where “$.deptno == 10” selected_employees;

P2 offers an (extensible) set of container and cursor operations. For example, the foreach construct is

used to iterate over qualiﬁed elements of a container. The foreach loop below prints the names of

selected employees:

// For each element whose deptno field has the value 10.

foreach( selected_employees )

{

// Print the employee name.

printf( “%s\n”, selected_employees.name );

}

2.2 Composite Cursors

Complex data structures consist of multiple containers whose elements are interconnected by pointers. A

relationship among containers C

, C

, ..., C

is a set of n-tuples <e

, e

, …, e

> where element e

is a mem-

ber of container C

. Figure 2 depicts a relationship for containers A, B, and C whose 3-tuples are:

{(a3,b1,c1), (a3,b1,c3), (a1,b2,c4), (a2,b3,c2), (a2,b3,c4)}

A composite cursor enumerates the n-tuples of a relationship. More speciﬁcally, a composite cursor k is an

n-tuple of cursors, one cursor per container of a relationship. A particular n-tuple <e

, e

, ..., e

> of a rela-

tionship is encoded by having the ith cursor of k positioned on element e

. By advancing k, successive n-

tuples of a relationship are retrieved.

As an example, a composite cursor c that joins elements of the department and employee containers

that share the same value of the deptno ﬁeld is speciﬁed in P2 as:

3. Note that predicates in P2 are expressed by strings. Field F of the element referenced by a cursor is denoted “$.F”. A cursor

over container with alias

x is denoted “$x”.

Figure 2. A Multicontainer Relationship

cursor

container

elements

Figure 1. Basic P2 Abstractions

compcurs < d department, e employee > where “$d.deptno == $e.deptno” c;

d and e are aliases for container names. (As we will see in Section 3.2, aliases are useful for expressing the

joins of containers with themselves in an unambiguous way). The foreach loop below prints (

employee

name, department name) pairs. Readers may recognize this loop as a natural join between depart-

ment and employee containers:

foreach( c )

{ printf( “%s %s\n”, c.e.name, c.d.name ); }

Occasionally, it is useful to retrieve only n-tuples of a relationship that involve speciﬁc objects. Suppose

we are interested only in the 3-tuples of Figure 2 that involve element b3 of container B (i.e., tuples

(a2,b3,c2) and (a2,b3,c4)). Such a retrieval is called seeding a relationship with b3. Seedings are

expressed in P2 by augmenting the compcurs declaration with a given clause (which lists aliases of all

containers that are to be seeded). Prior to a foreach, the given cursors must be positioned on the seed-

ing elements. The above example with b3 would be expressed by the following compcurs declaration

and foreach code fragment:

// Declare seeded_composite_cursor seeded by b.

compcurs < a A, b B, c C > given < b > seeded_composite_cursor;

// Position seeded_composite_cursor.b

position( seeded_composite_cursor.b, address_of(b3) );

// Iterate over seeded tuples.

foreach( seeded_composite_cursor )

{ ... }

Updating elements within a foreach loop is possible. Such updates may affect the n-tuples that are

retrieved by a composite cursor. Again consider the example of composite cursor c which returns pairs of

related department and employee elements. The foreach of Figure 3a deletes the department

element for each retrieved ordered pair.

Suppose the code fragment of Figure 3a was executed. Figure 3b shows the sequence of tuples that would

be processed by the foreach loop during a “blind” retrieval. Blind or traditional database retrievals do

not take into account changes (e.g., deletions) made to elements since the last composite cursor advance-

ment. What is actually needed is a “validated” retrieval of n-tuples, where tests are performed prior to each

composite cursor advancement to make sure that the next n-tuple is meaningful. Figure 3c shows the tuples

produced during a validated retrieval.

foreach ( c )

{ delete(c.d); }

“blind” join

( d1, e1 )

( d1, e2 )

( d1, e3 )

( d2, e4 )

( d2, e5 )

( d3, e6 )

“valid” join

( d1, e1 )

( d2, e4 )

( d3, e6 )

skip

Figure 3. Updating elements within a foreach loop.

(a)

(b) (c)

剩余14页未读，继续阅读

评论收藏

内容反馈

strcmp

2013-07-22

很不错的算法示例，谢谢了。
Cabinathor

2014-02-08

不错的算法
leslie_kwork

2017-09-26

是The LEAPS Algorithms 算法论文

dongsj8325

粉丝: 3
资源: 4

leaps 算法 rule engine algorithm

最新资源

leaps 算法 rule engine algorithm

LEAPs-开源

数据库算法及Google搜索引擎算法的秘密.rar_algorithm_java search engine_搜索_数据库搜索_

基于Spring的规则引擎

leetcode跳跃-algorithm:算法

Leaps PHP Framework V0.0.2

Drools的进一步研究

Quantum-Leaps-C-Application Notes

drools的进一步研究

动态演化系统中规则引擎的改进Rete算法

Drools引擎的研究与应用

基于PHP的Leaps PHP Framework 轻量级php开发框架.zip

基于PHP的Leaps Framework 轻量级php开发框架.zip

Go-Leaps是一个用go语言实现的用来协作开发的命令行工具

PHP实例开发源码—Leaps Framework 轻量级php开发框架.zip

jboss rules 用户指南

JBoss_Rules学习

Leaps PHP Framework V0.0.2.zip

Leaps PHP Framework V0.0.2.rar

PHP实例开发源码-Leaps PHP Framework 轻量级php开发框架.zip

规则引擎drools-jboss rules

Drools手册译.pdf

jboss rules用户指南（中文）PDF格式

基于SNMP的信息采集系统 (2009年)

Leaps PHP Framework 2.0.1

ZJU_ACM_All_Anwer 搞编程的都知道的浙江大学Ａ 题库．本书 集了所有经 Ｚ 题解集，集合并附 Mathimaticsumerical algorithms 数值算法

Approximate-String-Matching

Python库 | deep-leaps-0.0.8.tar.gz

javaweb 项目中常用的jar包详解.doc

最新资源

ZJU_ACM_All_Anwer 搞编程的都知道的浙江大学Ａ题库．本书集了所有经Ｚ题解集，集合并附 Mathimaticsumerical algorithms 数值算法