論文 / 著書情報
Article / Book Information
Title

Treatment of Rules in Individual Metadata of Flexible Contents
Management

AuthorKensuke OTA, Dai Kobayashi, Takashi Kobayashi, Ryo Taguchi, Haruo
YokotaJournal/Book nameProc. of International Special Workshop on Databases For Next
Generation Researchers (SWOD 2006), Vol. , No. , pp. 77-82

Issue date

2006, 4DOI

10.1109/ICDEW.2006.153

URL

http://www.ieee.org/index.html

Copyright(c)2006 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other users, including
reprinting/republishing this material for advertising or promotional
purposes, creating new collective works for resale or redistribution toservers or lists, or reuse of any copyrighted components of this work inother works.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

Treatment of Rules in Individual Metadata of Flexible Contents Management

1

2

3

4

Kensuke Ohta , Dai Kobayashi , Takashi Kobayashi , Ryo Taguchi , and Haruo Yokota
1

3,2Faculty of Engineering

Tokyo Institute of Technology
2Grad. School of Info. Sci. and Eng.
Tokyo Institute of Technology
4

3

Global Scientic Info. and Comp. CenterTokyo Institute of Technology

Science and Technical Research Laboratories
Japan Broadcasting Corporation{ohta@de.cs,daik@de.cs,tkobaya@gsic}.titech.ac.jp, taguchi.r-cs@nhk.or.jp, yokota@cs.titech.ac.jp

Abstract

between storage devices having different cost-performancefeatures, based on given system-wide policies for access

The properties of contents stored in a computer systemfrequencies and time information.

However, the strategy

are very wide while the data volume treated in the systemdetermined by the system-wide policies is less exible forbecomes very large. It is important to treat each stored ob-

the diversity of actual contents. The ner grained control

ject in different manners to reect its properties in the dataconsidering each content is required.

management for the large amount of stored data. To satisfy

To satisfy the requirement, we propose a method that is

the requirement, we propose a method for the autonomousto specify the control strategy for each stored object in its

management based on ECA rules stored in metadata of themetadata. We use the ECA (Event-Condition-Action) rules

contents. We study the feasibility of treating a large number

to express the control strategy in the metadata. The ECA ar-of ECA rules corresponding to the number of stored objects.

chitecture was originally proposed for the active databases

Because the cost for evaluating conditions in the rules be-

to move the reactive behavior from database applications

comes dominant to the system performance when the num-

into the DBMS using declarative rule denitions [4, 8]. The

ber of objects increases, we divide the conditions into twoframework of declarative specication to invoke actions un-

types, previously evaluable conditions and runtime evalu-

der predened conditions for a certain event is also usefulable conditions, and construct a discrimination network forfor managing stored contents. The desired actions for man-the previously evaluable conditions of each event to reduce

aging them can be invoked if the state of storages or stored

the cost for processing the rules. We implement the methods

objects satises given conditions when a specied event oc-

in the autonomous disk system, a high functional storage

curs. Our methods enable the ne-grain exible control cor-system we proposed, and evaluate the efficiency of them.

responding to each content.
To implement the ECA-rule based contents manage-

1

Introduction

ment, we have to consider the cost of processing the rules.

The efficient management for large amount of data has

The cost for evaluating conditions in the rules becomes

been strongly required because the data volume stored in adominant to the system performance when the number ofcomputer system increases explosively. At the same time,

stored objects increases. It is important to reduce the costthe variety of stored contents has also been very wide. Toof condition evaluation.

realize the efficient data management, these various stored

To make the rule processing for stored contents efficient,objects should be treated in different manners to reect their

we propose a method of dividing the conditions of an ECA

properties.

rule into two types, previously evaluable conditions (PEC)

As an approach for reecting the property of stored con-and runtime evaluable conditions (REC), and construct atents in data management, the concept of Information Life-

discrimination network for the PEC of each event. It omits

cycle Management (ILM) [1, 2, 9] has been proposed. The

the redundant condition evaluation, and reduces the number

basic mechanism of the ILM is to migrate the stored objectsof rules to be evaluated when the event occurs.

We alsopropose a method that is to prepare true rule tables and false

and the condition has been evaluated to true. We assume

rule tables to reduce the cost for updating the discriminationthat users know the commands of the high functional stor-

network.

age system to be written in the ECA rules.

We implement the proposed methods on the autonomous
disk system, a high functional storage system we proposed[10], and show efficiency of the proposed methods by experiments on the autonomous disk system.
The rest of the paper is organized as follows. At rst,

3

ECA Rule for Contents Management
To apply the ECA rules to management of stored con-tents, we have to consider what kind of information shouldbe specied in the rules.

in Section 2, we describe assumptions related to the storage
system, metadata and the ECA architecture we use. Then,• In event, basic operations for stored contents, such

we explain the ECA rules for managing stored contents in

as insertion and deletion, the timer interrupt and theSection 3. Section 4 describes a na¨ve approach for process-events dened by applications are written.

ing rules and the proposed methods. Then, the effectivenessof the proposed method is considered through the experiment on the autonomous disk system in Section 5. The related works is described in Section 6, and the conclusions
and future work are described in Section 7.

2of contents, presence of contents, and condition of parameter decided when an event occurs are written.

• In action, the tasks using the internal command offeredby the high functional storage system are written. If

Assumptions
At rst, in this section, we briey describe assumptionsof a storage system, metadata and ECA architecture to prepare the consideration of ECA rules in metadata to expressthe ne-grain control strategy.

2.1• In condition, the restrictions concerning the metadata

the internal commands that touch the system directly
are being offered enough, the range of describable processing will become wide.
The following are example rules for handling stored con-Storage Systemtents.

We assume a high functional storage system to handle
We have proposed the au-

Example 1 This is a rule for changing the permission of

tonomous disk system as a high functional storage system

opening web contents to the public. When the image[10]. It has an instruction set for handling the internal rule.

used by Web contents is open to the public at limited

Flexible descriptions become possible for content manage-

period by the reason of copyright, this rule is used toments by combining those instructions in ECA rules. How-release the inspection limitation on the day of opening

ever, the proposed method can be also applied to other typeto the public:

the ECA rules in metadata.

of high functional storage systems.

2.2

Metadata

The metadata is an attribute information for a stored object. In other words, each stored object has its own metadata. We assume that the metadata contains the le attributesupported by standard le systems, such as POSIX1003.1

Event At 2006/12/31 24:00
Condition If the permission of inspection from theoutside is denied
Action Change the permission of the content to allow
access from outside

specication and NFS version 3 [3]. It may also contains

Example 2 This is a rule to delete contents that relates toinformation dened by users, such as copyright expiration

the deleted image content when the image content isdate and relationship to other objects. In this paper, we dodeleted. If there are one or more voice contents and ti-

not describe about the details of metadata, but assume thattle text whose access frequencies are below the thresh-

ECA rules can also be stored in metadata of each object.

old related to the deleted image content, they will be

2.3

deleted when the image content is deleted:

ECA Rule

The ECA architecture was originally proposed for the ac-

Event When image content is deleted

tive databases [4]. It has a number of variants [8]. Here, we

Condition If there are one or more voice contents andassume that an ECA rule has three components: an event, a

title text whose access frequencies are below thecondition, and an action. The event part of the rule describes

threshold related to the deleted image content

a happening to which the rule may be able to respond. The
condition part of the rule examines the context in which theevent has taken place. The action describes the task to be
carried out by the rule if the relevant event has taken place

Action Delete the concerned contents
Thus, the exible contents management is expressed by
the rules in the metadata of each stored object.

4

Rule Processing

Rule 1

iffore explaining the proposed method, we describe a na¨vewhen Time(currentTime)Time(currentTime)

Content1.type == “log”
and Content1.size >= 200KB
and currentTime <= Content1.etime

for evaluating the condition in a large amount of rules. Beapproach to process rules for comparison.

Rule 2when

In this section, we propose methods to reduce the time

then

if

actionThen, we de-thenscribe the methods to shorten the evaluation and update op-

Content2.type = “avi”
and Content2.size >= 500MB
and Content2.mtime<= 2005.12.09 17:00:00
and currentTime <= Content2.etime
actiontransformationtransformation

erations.

4.1

Naı̈ve Approachroot node

Event : Time

A rule manager is required to register and execute rules

table node

type

true rule table

to implement a system. When a rule is added to the system,

size

mtime

the rule manager registers the rule. At this time, this rule ismapped to the event in the rule manager. When the event

beforefalse rule tableEventoccurs, this rule becomes one of the candidate rules to beafter

invoked for the event.

RuleID

sub Condition (sPEC)

Rule1

Content1.type == “log”

Rule2

Content2.type == “avi”

rules related to this event. The condition of each rule is eval-::uated. If the evaluation result of the condition is true, the:tasks described in the action are executed. In this approach,related to the event whenever the event occurs. However,scanning all rules may waste of many resources.

4.2

Proposed Method

4.2.1

Division of Condition

join
firing node

Rule1

Rule2

(Pre-Evaluable
Condition is true.)(Pre-Evaluable
Condition is true.)

Evaluate Runtime
Evaluable Condition
if true…

the cost to evaluate the condition in a large amount of rules
is expensive. We should evaluate the condition for all rules

joinjoin node

When an event occurs, we get the invocation candidate

Rule1 is firing!

Evaluate Runtime
Evaluable Condition
if true…

Rule2 is firing!

Figure 1. Execution Outline of proposed
methodgenerated, and it has a true rule table on which rules areregistered rules when the sPEC evaluation is true, and a

A conditions of a rule can be divided into two parts: pre-false rule table on which rules are registered rules when

viously evaluable condition (PEC) and runtime evaluable

the sPEC evaluation is false. In the join node, two true rulecondition (REC). PEC can be evaluated regardless of thesets passed from table nodes or other join nodes are joined.

event occurrence. REC should be evaluated when the event

When registering or deleting a rule, the join node is gen-occurs. PEC can exist as a condition of contents that haveerated or deleted. In the ring node, RECs of rules passed

already been stored. REC can be generated because of thefrom the join nodes are evaluated, and the actions of rules

parameter decided for the rst time when the event occurs.

will be executed when their REC evaluations are true.

For example, the condition If the permission of inspection from the outside is denied in the rule of Example 1 isa PEC. The condition If the voice contents or the title text
whose access frequency is below the threshold exists in apart of the rule in Example 2 is a REC.
PEC may be composed of multiple conditional expres-

4.2.3

Operation on Event Occurrence

The discrimination network is generated according to thenumber of event types. In the discrimination network corresponding to the occurred event, the following operations
are executed.

sions. It can be divided into partial conditions, sPEC(sub-1. Each table node passes a true rule set to the join node.

PEC)s including a single metadata item. We evaluate sPECs

This true rule set is a rule group registered in the true

when the metadata of contents is updated, and evaluate REC

rule table.

of the rule whose evaluation of PEC is true when an event
occurs. Because the invocation candidate rules are reduced,
the rule invocation time is shortened when an event occurs.
4.2.2

Outline of Execution

Discrimination network constructed by registered rules decides invocation candidate rules and evaluates RECs of
those rules when an event occurs. Figure 1 is the outline

2. In the join node, rules included in two rule sets are
extracted.
3. These rules are passed to the ring node.
4. In the ring node, RECs of the passed rules are evaluated. If the results are true, the actions are executed.

of the process using the discrimination network. The dis-For example, in Figure 1, the true rule sets of the tablecrimination network is composed of one root node, tablenodes type and size are passed to the join nodes whennodes, join nodes, ring nodes and arcs that connect nodes.

the event is generated.

In the root node, the condition of the registered rule isdivided.

The table node of each kind of the metadata is

Rules included in those true rulesets are extracted and passed to the ring nodes. In the ring nodes, rules passed from the join node are invoked iftheir REC evaluation are true. If Rule 1 is included in those

Table 1. Experimental Environment

rules, the action of Rule 1 will be executed. Similarly, Rule
2 can be executed in the same way.
4.2.4

Operation for Registered or Deleted Rules

When a rule is registered:
1. In the root node, the condition is divided into PECs

CPU

AMD Athlon XP-M1800+ (1.53GHz)

MemoryPC2100 DDR SDRAM 1GB

Disk

TOSHIBA MK3019GAX (30GB，5400rpm，2.5inch)

OSLinux 2.4.20

Java VM

Sun J2SE SDK 1.5.0 03 Server VM

and RECs, and a PEC is divided to sPECs. The sPECs

when

are mapped to the rule including themselves, and theytime(currentTime)are passed to the corresponding table nodes depended

if

on metadata item included in their sPECs.
2. In the table node, the passed sPEC is evaluated, and if
its result is true, it will be registered to the true rule
table; otherwise, it will be registered to the false rule
table.

then

3. The join node is generated if it does not exist.

this.item == “video”
and o1.item == “audio”
and this.title == o1.title
and currentTime <= this.etimeand currentTime <= o1.etime
actionFigure 2. Rule used in the experiment

For instance, in Figure 1 , sPEC The le type of Content
1 is log is registered in the table node type, and sPEC
The size of Content 1 is 200KB or more is registered in
the table node size when Rule 1 is registered. The joinnode will be newly generated, if there is no join node thatjoins type and size.
When the rule is deleted, the corresponding sPECs will
be deleted from the table node, and the corresponding join

To set the rule used in the experiment, the following situations are assumed. When various stream data are stored,
we would like to store those data in one container format asmuch as possible. If there are video data and voice data of
the same title and the expiration date of each data is not due
when the event occurs, the system will move those data toother storages and edit them there automatically.
Figure 2 shows the rule used in the experiment. Eachnode will be deleted.

one of the rst three conditions represents a sPEC, and the
4.2.5

Operation for Updated Content

whole three conditions in Figure 2 corresponds to a PEC,

When a sPEC of the condition concerning updated con-and the last two ones denote RECs. We describe a rule intents exists, in the table nodes including the sPEC, it is re-

Figure 2 to each content. To avoid the uctuation of pro-evaluated and registered to the true rule table or false rulecessing time by the difference of the action, the action istable according to the result of the re-evaluation. The rule

not executed in the experiment.

does not need to be restructured at the update by doing man-

5.3

agement of sPEC with two kinds of tables. Thus, the update

Comparison of Rule Processing Time

We compare the rule processing time of our method withprocessing time can be reduced.

that of the processing method by scanning all rules. The

5

ExperimentThe

proposedmethodrule processing time when an event occurs is measured withisimplemented

on

the

au-

tonomous disk system to show their effectiveness.

5.1

Environment

The experiment is conducted on the autonomous diskchanging the ratio of the rule when its PEC evaluation istrue.
We provide a rule to each content, and show the effect ofnarrowing by evaluation of PEC. All the REC evaluations
are assumed to be true.

We measure the rule processing

system as a decentralized storage technology proposed.

time when the number of registration rules is 100, 1000,

An autonomous disk is imitated by using Java on Linux

3000, 5000, 8000 and 10000.

cluster.

The experimental environment is composed of a

network switch having enough backbone performance andeight Linux boxes shown in Table 1.

5.2

Scenario

Figure 3 and Figure 4 show the rule processing time
when the probability of the its PEC evaluation to be true is10%, and 5% among rules with the possibility of invocatingwhen the event occurs.
The rule processing time of the proposed method de-

We measured the rule processing time when the event

pends on the ratio of PEC and REC in the condition of rule.

occurs by the proposed method and the delay time when

Therefore, we measure the rule processing time when thecontents are updated by using the proposed method.

ratio of PEC and REC changes.

     


 

)
%(
'
%&
#$

*,+.-/102 3

 

)

457698;:<>=@?A<576

 ,.-0/213547686
9;:=<?>A@B;CADFE:=<GIHJDLK
9;:=<?>A@B;CADFE:=<GMKND8H
9;:=<?>A@B;CADFE:=<GPO DRQ

 
+
%&

'*

  '(   

 





 
 

 







 

!"Figure 3. Rule processing time when probability of PEC evaluation to be ture is 10%   
 

%&

'*

  
'(

 

 



 

)



Figure 5. Rule processing time when ratio of
PEC and REC are changes  +   "!#$,.- /021 3 "4"57698;:=<!>@?AB698%!$#

  

!"&('*),+.-/1020

 

346587:9<;>=@?6AB465







 
 


 
 !"#$





 



Figure 4. Rule processing time when probability of PEC evaluation to be ture is 5% 

Figure 6. Average processing time of insertion, update, and deletion

Figure 5 shows the rule processing time when the ra-

the number of rules whose PEC evaluation is true increases,

tio of the rule that the evaluation of the PEC is true is 5%.

and the join processing time increases according to the in-

We measure the rule processing time when the ratio of PEC

crease of the number of rules.

We intentionally changed

In other experiment, the processing time increases as thethe ratio of PEC and REC included in a rule. The rule ofratio of REC included in the condition increases. However,and REC is 3:2, 2:3, and 1:4.

PEC:REC=3:2 is the same as the rule used in the experi-

because the processing rule number is decreased by narrow-ment (Figure 2).

ing the invocation candidate rules, the rule processing time

5.4of our method is less than that of the method scanning all

Comparison of Contents UpdatingTime

We measured the latency delay by implementing of the
proposed method when the metadata of contents is updated.
In this experiment, we measure three operations (insertion,
update, and deletion of contents). This is because the updating of discrimination network is necessary when the metadata of contents is changed by each operation.
Figure 6 shows the result of the average processing timefor 1000 insertions, updates, and deletions of contents.
These operations are done from one client to an autonomous
disk sequentially.

5.5

Discussion

5.5.1

Rule Processing Performance

In the experiment in Section 5.3, our method always redeuces the rule processing time when an event occurs.
In the rule processing method scanning all rules, the rulerules.
5.5.2

Contents Updating Performance

In the update operation, the latency delay for implementing of the proposed method is only 3ms, because we only
need to re-evaluate the sPECs and register them to the true
rule table or false rule table in the table node including thesPECs that should be changed.
As for the insertion and deletion of contents, the latency
delay for implementing of the proposed method is 15ms and16ms.

This is because not only the renewal of the tablenode but also the registration or deletion of the rule from thediscrimination network, and generation or deletion of thejoin node are needed. However, the delay can be acceptablecompared with the imprement of rule processing time.

6

Related Workprocessing time increases as the number of rules increases.

The research on content-aware storage management isThis is because the condition evaluation for all rules relative

one of hot topics. OSD (Object-Based Storage Device) isto the event must be executed.

the mechanism that the data under storage is treated in eachIn the proposed method, the processing time also in-content [6]. OSD manages the le, not by block unit, increases as the number of rules increases. This is because

each object with high abstraction level. In the description

of the metadata and the control rule in each content, theyond the network. We need to reduce the time of REC eval-compatibility of OSD to our reseach is good.

uation. Moreover, the method of describing a large amount

Policy-based ILM provides the control policy to the en-of rules automatically is crucial. In addition, We need totire system, and the storage management has been proposed

introduce a rule verication technique to prevent the disad-to the automation of ILM using the centralized management

vantage from happening to the user. For example, we need asystem [2]. It is difficult to do the control reecting the statetechnique for discovering rules whose conditions are never

and the access tendency of individual contents in detail be-satised and checking the termination of rules.

cause each policy targets all contents.
The storage management using the ECA rule has been
researched in active databases [8], and the ECA rule itself
has been well studied in the active databases [4, 8].
In the rule-based systems such as a production system[5], the Rete algorithm [7] is widely used to evaluate thecondition of rules at high speed. An rule-based system isdemanded to retrieve a corresponding data set at high speed
from a large amount of data. Therefore, the Rete network
based on the Rete algorithm has been used in the rule-based

Acknowledgements
We thank Mr. Tomohiro Yoshihara for his advice about
implementation on the autonomous disks.
This work is partially supported by the JST CREST,
SRC, MEXT of Japanese Government via Grant-in-Aid for
Scientic Research #16016232 and the MEXT 21st Century
COE Program.

References

system.
The Rete algorithm is suitable for executing the evalua-[1] L. L. Ashton, E. A. Baker, A. J. Bariska, E. M. Dawson,tion whether the condition of the complex rule is satised

R. L. Ferziger, S. M. Kissinger, T. A. Menendez, S. Shyam,each contents at high speed in the situation in which a large

J. P. Strickland, D. K. Thompson, G. R. Wilcock, and M. W.

amount of contents are stored. The proposed method aims

Wood.

to evaluate the condition of rules given to the contents at

for the IBM mainframe computer.

high speed in the situation when the number of rule is more

42(2):302321, 2003.

IBM Systems Journal,[2] M. Beigi, M. V. Devarakonda, R. Jain, M. Kaplan, D. Pease,than that of the contents.

7

Two decades of policy-based storage management

J. Rubas, U. Sharma, and A. Verma. Policy-Based Informa-

Conclusions and Future WorkTo realize the ne-grain exible contents managementin high functional storage systems, we propose a method
to describe the controle rule in the metadata of individualstored object. The rule specication for each object enlarges
the number of rules treated in the system. Because registered rules contain many unsatised conditions, the cost of
scannnig all rules for an event becomes expensive.
In this paper, we proposed a method to shorten rule in-tion Lifecycle Management in a Large-Scale File System. In
POLICY, pages 139148. IEEE Computer Society, 2005.
[3] B. Callaghan, B. Pawlowski, and P. Staubach. NFS Version 3
Protocol Specication. Sun Microsystems, Inc., June 1995.
http://ftp.riken.go.jp/pub/internet-doc/rfcs/rfc1813.txt.
[4] U. Dayal. Active database systems. In Proc. of 3rd Intn'l
Conference on Data and Knowledge Bases, pages 150169,
1988.
[5] T. Ishida. Parallel rule ring in production systems. IEEE
Trans. Knowl. Data Eng., 3(1):1117, 1991.

In the method, we[6] V. Kher and Y. Kim. Decentralized Authentication Mecha-

divided the condition of rule into PECs and RECs, and con-nisms for Object-based Storage Devices. In IEEE Security

structed the discrimination network to evaluate the PEC.

in Storage Workshop, pages 110. IEEE Computer Society,vocation time when an event occurs.

Because the method reduces the number of invocation candidate rules by the discrimination network when the event
occurred, the rule invocation time can be reduced. We also
proposed a method to shorten the update of the descrimination network.
We implemented the proposed methods on the autonomous disk system, and compared the execution time of

2003.
[7] D. P. Miranker.

TREAT : a new and efficient match algo-rithm for AI production systems. Research notes in articial
intelligence. Pitman, Morgan Kaufmann, London, San Mateo, Calif, 1990.
[8] N. W. Paton and O. D´az. Active database systems. ACM
Comput. Surv., 31(1):63103, 1999.
[9] A. Verma, D. Pease, U. Sharma, M. Kaplan, J. Rubas,

the proposed methods with that of the method scanning all

R. Jain, M. V. Devarakonda, and M. Beigi.

rules by experiments. The results indicate that the rule pro-ture for Lifecycle Management in Very Large File Systems.

cessing time can be reduced by using our methods. Comparing with the normal systems, although our proposed system
has a few milli seconds of performance degradation, it canbe hided by implementing an asynchronous descrimination
network update function.
As the future work, it is necessary to consider a rule
which requires the communication excluding storage be-

An Architec-

In MSST, pages 160168. IEEE Computer Society, 2005.
[10] H. Yokota. Autonomous Disks for Advanced Database Applications. In Proc. of International Symposium on Database
Applications in Non-Traditional Environments (DANTE'99),
pages 441448, Nov. 1999.