Intelligent fuzzy queries for multimedia databases

Multimedia databases have emerged to cope up with the huge amount of multimedia data, which comes up as a result of technological advancement. However, more intelligent techniques are required to satisfy different query requirements of multimedia users. This study extends the query capability of a multimedia database through the integration of a fuzzy rule‐based system. In addition to fuzzy semantic rules, which deduce new information from the data stored in the database, fuzzy spatial and temporal relations, which are inherent to multimedia applications, are defined in the rule‐based system. Users can formulate fuzzy semantic, spatial, temporal, and spatiotemporal queries, resulting in the deduction of new information using the rules defined in the rule‐based system. With some practical examples, the paper presents how a fuzzy rule‐based system integrated to a fuzzy multimedia database improves the query capabilities of the database system intelligently. © 2011 Wiley Periodicals, Inc.     

Efficient Query Execution Techniques in a 4DIS Video Database System for eLearning

In this paper, we describe our work on developing an eLearning video database system. The eLearning video database provides a temporal modeling framework for describing eLearning video data and it supports data distribution by applying vertical class partitioning techniques. Building on top of our previous work on Four Dimensional Information System (4DIS)—an object-oriented temporal modeling framework, we apply vertical class partitioning techniques onto a 4DIS eLearning video database system as a means for efficient query execution. We further describe our work on dynamic fetching of multimedia eLearning video on the Internet. A detailed cost model for query execution through vertical class partitioning is developed. Finally, we demonstrate through the use of a running example the effectiveness of our vertical class partitioning approach.     

PressBase : a presentation synchronization database for distributed multimedia systems

Multimedia presentations are the basic objects of multimedia databases. Since a multimedia presentation is not an instant display of a query result, the control knowledge (or synchronization requirements) has to be incorporated into the database and necessary precautions have to be taken for a lengthy presentation. Active databases provide a mechanism for incorporation of control knowledge by using event-condition-action (ECA) rules. In this paper, we describe how multimedia synchronization can be handled within a database using ECA rules. We present a prototype presentation synchronization database, named as PressBase, for distributed multimedia systems. We have adopted one of the synchronization models, SynchRuler, and then incorporated into a relational database system.     

An efficient query optimization strategy for spatio-temporal queries in video databases

The interest for multimedia database management systems has grown rapidly due to the need for the storage of huge volumes of multimedia data in computer systems. An important building block of a multimedia database system is the query processor, and a query optimizer embedded to the query processor is needed to answer user queries efficiently. Query optimization problem has been widely studied for conventional database systems; however it is a new research area for multimedia database systems. Due to the differences in query processing strategies, query optimization techniques used in multimedia database systems are different from those used in traditional databases. In this paper, a query optimization strategy is proposed for processing spatio-temporal queries in video database systems. The proposed strategy includes reordering algorithms to be applied on query execution tree. The performance results obtained by testing the reordering algorithms on different query sets are also presented.     

Effective scheduling of detached rules in active databases

While triggers have become a classical ingredient of relational database systems, research in active databases is aiming at extending the functionality and expressive power of active rules beyond the scope of relational triggers. One of the most important current trend concerns the support of detached active rules, i.e., of rules which are executed as separate transactions, running outside of the scope of the transaction which generates the triggering event. Detached rules have important applications in workflow management and global integrity maintenance across transactions. One of the main issues in designing the rule engine for detached rules is determining their optimal scheduling. In this paper, we study the performance of a detached rule scheduler whose objective is to minimize the interference of detached rule execution with regard to the normal transactional load. This objective is achieved by executing detached rules at given periods of time and by assigning them a fixed amount of dedicated threads; we study the performance of the scheduler relative to the two most critical design parameters, the frequency of execution of the scheduler, and the number of dedicated execution threads.     

A Hybrid Fragmentation Approach for Distributed Deductive Database Systems

Fragmentation of base relations in distributed database management systems increases the level of concurrency and therefore system throughput for query processing. Algorithms for horizontal and vertical fragmentation of relations in relational, object-oriented and deductive databases exist; however, hybrid fragmentation techniques based on variable bindings appearing in user queries and query-access-rule dependency are lacking for deductive database systems. In this paper, we propose a hybrid fragmentation approach for distributed deductive database systems. Our approach first considers the horizontal partition of base relations according to the bindings imposed on user queries, and then generates vertical fragments of the horizontally partitioned relations and clusters rules using affinity of attributes and access frequency of queries and rules. The proposed fragmentation technique facilitates the design of distributed deductive database systems. Received 4 August 1999 / Revised 30 March 2000 / Accepted in revised form 6 October 2000     

基于统计的关系数据库查询优化器模型分析与研究

如果没有良好的查询优化器,即使是小型的数据库也会表现出非常明显的性能低下。由于实际优化器的内部结构所涉及的功能和过程异常复杂,通常的商业数据库的查询优化器至少需要50人/年的开发量。主要分析研究关系数据库中的查询优化技术,提出基于统计的、适应于关系数据库的查询优化器设计模型。     

RBE: A Rule-by-example Active Database System

In an active database system, rules are used to monitor and respond to events that happen inside the database. This paper presents the implementation of an active database system called RBE. The system loosely couples an OPS5 production system and an INGRES database management system to efficiently monitor databases on complex conditions. In this system, atable-based Rule-By-Example (RBE) language, is designed. The internal representations of the RBE rule language are production rules; therefore, rules can be stored, managed and tested efficiently by using the well-developed pattern matching algorithm in a production system. In other words, the system applies a production system and a special production system program to the task of query rewrite trigger processing. Moreover, a user-friendly interface is used to loosely couple the OPS5 rule system with the INGRES DBMS. The architecture used in this system shows the applicability of constructing an active database system by integrating any production system and any database system. Moreover, the proposed technique could be used as an implementation method for a query-rewrite rule system inside a DBMS server, not using a layered approach. © 1997 by John Wiley & Sons, Ltd.     

A stock recommendation system exploiting rule discovery in stock databases

This paper addresses an approach that recommends investment types to stock investors by discovering useful rules from past changing patterns of stock prices in databases. First, we define a new rule model for recommending stock investment types. For a frequent pattern of stock prices, if its subsequent stock prices are matched to a condition of an investor, the model recommends a corresponding investment type for this stock. The frequent pattern is regarded as a rule head, and the subsequent part a rule body. We observed that the conditions on rule bodies are quite different depending on dispositions of investors while rule heads are independent of characteristics of investors in most cases. With this observation, we propose a new method that discovers and stores only the rule heads rather than the whole rules in a rule discovery process. This allows investors to impose various conditions on rule bodies flexibly, and also improves the performance of a rule discovery process by reducing the number of rules to be discovered. For efficient discovery and matching of rules, we propose methods for discovering frequent patterns, constructing a frequent pattern base, and its indexing. We also suggest a method that finds the rules matched to a query from a frequent pattern base, and a method that recommends an investment type by using the rules. Finally, we verify the effectiveness and the efficiency of our approach through extensive experiments with real-life stock data.     

Let''s talk about it: dialogues with multimedia databases: Database support for human activity

We describe two scenarios of user tasks in which access to multimedia data plays a significant role. Because current multimedia databases cannot support these tasks, we introduce three new requirements on multimedia databases: multimedia objects should be active objects, querying is an interaction process, and query processing uses multiple representations. We discuss three techniques to handle multimedia objects as active objects. Also, we introduce a promising database architecture to meet the new user requirements. Agents within the database handle objects' representations, and a search engine on top of a conventional database handles relevance feedback and multiple representations.     

DMajor—Application Programming Interface for Database Mining

In the process of rule generation from databases, the volume of generated rules often greatly exceeds the size of the underlying database. Typically only a small fraction of that large volume of rules is of any interest to the user. We believe that the main challenge facing database mining is what to do with the rules after having generated them. Rule post-processing involves selecting rules which are relevant or interesting, building applications which use the rules and finally, combining rules together to form a larger and more meaningful statements. In this paper we propose an application programming interface which enables faster development of applications which rely on rules. We also provide a rule query language which allows both selective rule generation as well as retrieval of selected categories of rules from the pre-generated rule collections.     

An adaptable vertical partitioning method in distributed systems

Vertical partitioning is a process of generating the fragments, each of which is composed of attributes with high affinity. The concept of vertical partitioning has been applied to many research areas, especially databases and distributed systems, in order to improve the performance of query execution and system throughput. However, most previous approaches have focused their attention on generating an optimal partitioning without regard to the number of fragments finally generated, which is called best-fit vertical partitioning in this paper. On the other hand, there are some cases that a certain number of fragments are required to be generated by vertical partitioning, called n-way vertical partitioning in this paper. The n-way vertical partitioning problem has not fully investigated.In this paper, we propose an adaptable vertical partitioning method that can support both best-fit and n-way vertical partitioning. In addition, we present several experimental results to clarify the validness of the proposed algorithm.     

A practical mandatory access control model for XML databases

A practical mandatory access control (MAC) model for XML databases is presented in this paper. The label type and label access policy can be defined according to the requirements of different applications. In order to preserve the integrity of data in XML databases, a constraint between a read-access rule and a write-access rule in label access policy is introduced. Rules for label assignment and propagation are presented to alleviate the workload of label assignments. Furthermore, a solution for resolving conflicts in label assignments is proposed. Rules for update-related operations, rules for exceptional privileges of ordinary users and the administrator are also proposed to preserve the security of operations in XML databases. The MAC model, we proposed in this study, has been implemented in an XML database. Test results demonstrated that our approach provides rational and scalable performance.     

Data mining in deductive databases using query flocks

Data mining can be defined as a process for finding trends and patterns in large data. An important technique for extracting useful information, such as regularities, from usually historical data, is called as association rule mining. Most research on data mining is concentrated on traditional relational data model. On the other hand, the query flocks technique, which extends the concept of association rule mining with a ‘generate-and-test’ model for different kind of patterns, can also be applied to deductive databases. In this paper, query flocks technique is extended with view definitions including recursive views. Although in our system query flock technique can be applied to a data base schema including both the intensional data base (IDB) or rules and the extensible data base (EDB) or tabled relations, we have designed an architecture to compile query flocks from datalog into SQL in order to be able to use commercially available data base management systems (DBMS) as an underlying engine of our system. However, since recursive datalog views (IDB's) cannot be converted directly into SQL statements, they are materialized before the final compilation operation. On this architecture, optimizations suitable for the extended query flocks are also introduced. Using the prototype system, which is developed on a commercial database environment, advantages of the new architecture together with the optimizations, are also presented.     

Managing Conflicts between Rules

Rules are used as a programming paradigm in several application domains, including active databases, planning, expert systems, and billing. For example, active databases have rules that execute upon the occurrence of particular events if specified condition predicates are satisfied. It is often the case that multiple rules are fireable when a particular event occurs. We propose a declarative mechanism to control the interaction and execution of multiple rules. The mechanism is based upon logical meta-rules that can express various types of relationships between rules. The meta-rules allow us to reason statically about the rule behavior. We can determine, in polynomial time, whether a rule will never execute, whether two rules can ever be executed together, and whether a rule system is guaranteed to have a unique execution set for all possible rules that become fireable. In this paper, we illustrate our techniques using rules in an active database. A system based upon the meta-rules and the static analysis presented here has been found to be of value in a billing application at AT & T to control interactions between discount plans.     

Discovering Robust Knowledge from Databases that Change

Many applications of knowledge discovery and data mining such as rule discovery for semantic query optimization, database integration and decision support, require the knowledge to be consistent with the data. However, databases usually change over time and make machine-discovered knowledge inconsistent. Useful knowledge should be robust against database changes so that it is unlikely to become inconsistent after database updates. This paper defines this notion of robustness in the context of relational databases and describes how robustness of first-order Horn-clause rules can be estimated. Experimental results show that our estimation approach can accurately identify robust rules. We also present a rule antecedent pruning algorithm that improves the robustness and applicability of machine discovered rules to demonstrate the usefulness of robustness estimation.     

基于BaseX数据库的OWL本体存储查询研究

针对目前基于关系型数据库等存储模式的本体存储查询效率较低的情况,提出使用XML数据库BaseX进行本体的存储,并设计了相应的本体存储查询架构。在对BaseX存储结构与接口的研究基础上,实现对OWL本体的存储。利用BaseX的查询接口和XQuery查询语言对OWL本体进行检索,在建立推理规则库基础上,实现本体查询扩展与推理。实验将提出的存储查询方法与基于关系型数据库的存储查询方法进行对比,验证了提出的方法具备高效的存储查询性能,同时具备本体查询的推理能力。     

Early active database efforts: a capsule summary

Over the past few years, the topic of active databases has become an important area of research. A number of efforts-both research prototypes and commercial database management systems (DBMSs)-have addressed support for event-condition-action (ECA) rules in databases. This paper examines the motivations for providing this capability, identifies features that form the basis for supporting active functionality, and provides a capsule summary of active database features of early commercial systems as well as research prototypes. Three broad categories-rule expressiveness, execution semantics and efficiency-are used for the capsule summary     

Combining Fuzzy Information from Multiple Systems

In a traditional database system, the result of a query is a set of values (those values that satisfy the query). In other data servers, such as a system with queries based on image content, or many text retrieval systems, the result of a query is a sorted list. For example, in the case of a system with queries based on image content, the query might ask for objects that are a particular shade of red, and the result of the query would be a sorted list of objects in the database, sorted by how well the color of the object matches that given in the query. A multimedia system must somehow synthesize both types of queries (those whose result is a set and those whose result is a sorted list) in a consistent manner. In this paper we discuss the solution adopted by Garlic, a multimedia information system being developed at the IBM Almaden Research Center. This solution is based on “graded” (or “fuzzy”) sets. Issues of efficient query evaluation in a multimedia system are very different from those in a traditional database system. This is because the multimedia system receives answers to subqueries from various subsystems, which can be accessed only in limited ways. For the important class of queries that are conjunctions of atomic queries (where each atomic query might be evaluated by a different subsystem), the naive algorithm must retrieve a number of elements that is linear in the database size. In contrast, in this paper an algorithm is given, which has been implemented in Garlic, such that if the conjuncts are independent, then with arbitrarily high probability, the total number of elements retrieved in evaluating the query is sublinear in the database size (in the case of two conjuncts, it is of the order of the square root of the database size). It is also shown that for such queries, the algorithm is optimal. The matching upper and lower bounds are robust, in the sense that they hold under almost any reasonable rule (including the standard min rule of fuzzy logic) for evaluating the conjunction. Finally, we find a query that is provably hard, in the sense that the naive linear algorithm is essentially optimal.