SAC 2000: Electronic Proceedings

Database Technology Track

Track chair:Ramzi A. Haraty, Lebanese American University
The following papers submitted to the Database Technology Track in SAC 2000 are available on-line:
DIRTRIBUTED QUERY OPTIMIZATION USING PERF JOINS
 
Ramzi HaratyLebanese American University
Rola Fany Lebanese American University
Abstract

The advent of telecommunication era and the constant development of hardware and network structures have encouraged the decentralization of data while increasing the needs to access information from different sites. Query optimization strategies aim to minimize the cost of transferring data across networks. Many techniques and algorithms have been proposed to optimize queries. Perhaps one of the more important algorithms is the AHY algorithm using semi-joins that is implemented by Apers, Hevner and Yao. Nowadays, a new technique called PERF (Partially Encoded Record Filters), presented by Kenneth Ross seems to bring some improvement over semi-joins. PERF joins are two-way semi-joins using a bit vector as their backward phase. Our research encompasses applying PERF joins to the AHY algorithm and producing the AHYPERF algorithm. Programs were designed to implement both the AHY and AHYPERF. Several experiments were conducted and the results showed a very considerable enhancement of AHYPERF over the original AHY.

Full paper
An Approach to Integration of Web Information Source Search and Web Information Retrieval
 
Yuichi IizukaNTT Cyber Space Laboratories
Mitsuaki TsunakawaNTT Software corporation
Shin-ichiro SeoNTT Cyber Space Laboratories
Tetsuo IkedaNTT Cyber Space Laboratories
Abstract

As a result of the explosive spread of the WWW, many information sources are now being accessed through open networks. The information on the WWW covers various fields and the number of source is always increasing because more enterprises and individuals are becoming information sources. Users, on the other hand, want to obtain just the right information efficiently from the huge supply of information available. When we want to retrieve information from the WWW, it is useful to be able to search for the information sources and to retrieve information from these sources by using integrated operations. Various methods through which one can search for or retrieve information from the WWW, such as mediator methods and URL search engines have been proposed. However, using those methods, it is difficult to search for the information sources and retrieve information from those sources in an integrated way. When we use a mediator type method, it is necessary to specify the sources explicitly. When we use URL search engines (e.g., AltaVista, Lycos, Yahoo), URLs i.e. locations of information sources are returned as a result. So, it is necessary to access each individual source based on the listed URL to obtain the desired information. This paper proposes an integrated method of searching for information sources and retrieving information from these sources. The proposed method adopts a universal relation as a user interface. The other features of this method are as follows. - Template mechanism through which users can treat HTML pages as if they were tables of relational database(RDB). - Information resource management that resolves the heterogeneity among information sources. - A new application programming interface (API) by mean of which users can issue on inquiry and obtain results values.

Full paper
AN APPROACH TO DISCOVERING TEMPORAL ASSOCIATION RULES
 
Juan AleUNLM
Gustavo RossiLIFIA-UNLP
Abstract

The goal of discovering association rules is to discover all possible associations that accomplish certain restrictions (minimum support and confidence and interesting). However, it is possible to find interesting associations with a high confidence level but with little support. This problem is caused by the way support is calculated, as the denominator represents the total number of transactions in a time period when the involved items may have not existed. If, on the other hand, we limit the total transactions to the ones belonging to the items' lifetime, those associations would be now discovered, as they would count on enough support. Another difficulty is the large number of rules that could be generated, for which many solutions have been proposed. Using age as an obsolescence factor for rules helps reduce the number of rules to be presented to the user. In this paper we expand the notion of association rules incorporating time to the frequent itemsets discovered. The concept of temporal support is introduced and, as an example, the known algorithm A priori is modified to incorporate the temporal notions

Full paper
OORF: AN OBJECT-ORIENTED ROUTE FINDER
 
Muhammad Abaidullah AnwarKyushu Institute of Technology Japan
Takaichi Yoshida Kyushu Institute of Technology Japan
Abstract

Travelling is a part of human beings day-to-day life. The huge and complicated road network in a country makes it difficult to find a shortest (best) route for travelling from one place to another. Many shorter route finding algorithms have been designed. Since route finding involves a massive and complicated road network data therefore, it is necessary to arrange the data in such a way that it's retrieval, especially a part of the road or road sub-network in a specific part of the country, should be efficient and unnecessary data processing is avoided. This paper presents and object-oriented road network data model in which we divide the road into road segments and road network into road sub-networks, into levels in which a country is divided administratively, i.e. prefectures, cities, etc. We have implemented the model for shortest route finding.

Full paper
Static Detection of Sources of Dynamic Anomalies in a Network of Referential Integrity Restrictions
 
LAURA CELIA RIVEROISISTAN-UNIVERSIDAD NACIONAL DEL CENTRO, BUENOS AIRES, ARGENTINA
JORGE HORACIO DOORNISISTAN-UNIVERSIDAD NACIONAL DEL CENTRO, BUENOS AIRES, ARGENTINA
DANIEL LOUREIROUNIVERSIDAD NACIONAL DEL CENTRO, BUENOS AIRES, ARGENTINA
Abstract

Under certain circumstances, basic operations over tables in a relational database, where integrity restrictions such as referential and null restrictions have been specified, may produce unpredictable results, not detectable by means of a static analysis of the schema. When the design includes redundancies or when the set of restrictions is contradictory it is easy to detect and prevent future errors, but there are situations that require a dynamic analysis. In this paper, the properties of networks of referencial integrity restrictions that contain irregularities are analyzed, and the anomalies that may appear when data actualization in such environment is done are studied in order to define criteria and develop an algorithm to generate rules for proper handling of inconsistencies.

Full paper
THE APPLICATION OF ASSOCIATION RULE MINING TO REMOTELY SENSED DATA
 
Jianning DongDigital Impact Co.
William PerrizoNorth Dakota State Univ.
Qin DingNorth Dakota State Univ.
Zhou JingkaiNorth Dakota State Univ.
Abstract

The explosive growth in data and database has generated an urgent need for new techniques and tools that can intelligently and automatically transform the processed data into useful information and knowledge. Data mining is such a technique. In this paper, we consider the mining of association rules from remotely sensed data and its application in precision. Based on the characteristics of the remotely sensed data and the problem itself, we present a bit oriented formal model and discuss the issues of partitioning quantitative attributes into equal, unequal and discontinuous partitions. We propose two new pruning techniques and compare the performances with a base algorithm. An improvement in performance is shown when using these pruning techniques.

Full paper
The GOLD Definition Language (GDL): An Object Oriented Formal Specification Language For Multidimensional Databases
 
Juan TrujilloUniversity of Alicante
Manuel PalomarUniversity of Alicante
Jaime GomezUniversity of Alicante
Abstract

The GOLD Definition Language (GDL) is an Object Oriented (OO) formal specification language for the modeling of multidimensional databases. The OO multidimensional data model called GOLD is based on the OO paradigm, which allows us to consider key issues in multidimensional modeling that are hardly considered by other multidimensional models such as derived measures, derived dimension attributes, the additivity of measures and multiple classification hierarchies. In this paper, we define the GDL for the GOLD model and demonstrate that its power of expression enables us to consider all the peculiarities of multidimensional modeling.

Full paper
Maximizing Reusability: Seeking Appropriate Positions for Derived Classes within the Class Hierarchy
 
Reda AlhajjAmerican University of Sharjah
Faruk PolatMiddle East Technical University
Abstract

This paper addresses reusability maximization by investigating the proper location of a derived class in the class hierarchy. We categorize derived classes into four groups, depending on whether their superclasses and subclasses are known, and present two algorithms that investigate reusability maximization. The first algorithm decides on the possibility of adapting some existing related classes in the lists of superclasses of derived classes. The second algorithm checks the possibility of adding derived classes to the lists of superclasses of some other existing related classes to have the latter classes inheriting things instead of duplication.

Full paper
Active Services for Federated Databases
 
Genoveva VARGAS-SOLAR"University if Grenoble + Laboratory LSR"
Christine COLLET"INPG France + Laboratory LSR"
Helena RIBEIRO-GRAZZIOTIN"University if Grenoble + Laboratory LSR"
Abstract

This paper presents an architecture of a component based active mechanism suitable for federated database systems, i.e., a collection of autonomous DBMS with a common understanding of their universe of discourse. The main components of the mechanism are flexible event and rule services that cooperate to execute active rules. The event service specifies and generates event managers that detect, produce and notify events using an event management model. The rule service manages Event-Condition-Action rules global to federated database systems. Rules are triggered by events notified by event managers. They are executed according to an adaptable execution model. Conditions and actions can concern multiple DBMS.

Full paper
DISTRIBUTED QUERY PROCESSING USING ACTIVE NETWORKS
 
Zhili ZhangTibco Co.
William PerrizoNorth Dakota State Univ.
Abstract

In this paper, we present an efficient method for implementing distributed query processing on high speed wide area active networks. A discussion of the characteristics of high-speed wide area networks, traditional low speed networks, their differences and active networks is presented. A set of design criteria for distributed database systems over high speed WANs is derived based on these characteristics and differences. A distributed domain vector acceleration method is extended for distributed multi-way joins in this environment based on these design criteria. We develop a cost model to estimate response time and then compare the response time of our new method to that of a theoretical lower bound. We show that the response time cost for this method is very close to the theoretical lower bound. We further show that active networking can reduce the bandwidth requirement for distributed query meta-data processing by an order of magnitude compared to that of non-active processing.

Full paper
A PERFORMANCE COMPARISON OF QUADTREE-BASED ACCESS METHODS FOR THEMATIC MAPS
 
Eleni TousidouDepartment of Informatics, Aristotle University, 54006 Thessaloniki, Greece
Yannis ManolopoulosDepartment of Informatics, Aristotle University, 54006 Thessaloniki, Greece
Abstract

In this paper, the efficient manipulation of thematic maps that contain multiple non-overlapping features is investigated. New methods based on Linear quadtrees are proposed and their performance is compared to that of similar structures. More specifically, window queries involving multiple features are described and tested having the number of disk accesses as a performance measure. Experimentally, it is shown that the proposed methods have a stable behavior and, in general, outperform the previous structures with respect to time and space complexity.

Full paper
Mechanisms for Specifying Communication Behavior in Object Oriented Database Systems
 
Paulo F. PiresCOPPE - Federal University of Rio de Janeiro
Marta MattosoCOPPE - Federal University of Rio de Janeiro
Mįrio Roberto F. BenevidesCOPPE - Federal University of Rio de Janeiro
Abstract

Most object oriented concurrency control is dedicated to increase method execution concurrency, however they do not consider the inter-object behavior. In this paper we present mechanisms to deal with the communication behavior in OODBMS. We define linguistic constructors that describe both the internal and the external object communication behavior. We also present a decentralized transaction model and a protocol that guarantee the correct method execution for a single object (intra-object) and for a group of objects (inter-object) that cooperate to accomplish an activity.

Full paper
Automatic Generation of RDBMS based Applications from Object Oriented Design Schemes
 
Annamaria MustoDipartimento di Matematica e Informatica, Universitą di Salerno, via S. Allende, 84081 Baronissi, SA, Italy
Giuseppe PoleseDipartimento di Matematica e Informatica, Universitą di Salerno, via S. Allende, 84081 Baronissi, SA, Italy
Antonello PannellaGP Informatica S.A.S. Ctr Collepiano, 82030 Torrecuso, BN, Italy
Genoveffa TortoraDipartimento di Matematica e Informatica, Universitą di Salerno, via S. Allende, 84081 Baronissi, SA, Italy
Abstract

We present the OMAR methodology that allows to provide automatic support for the generation of RDBMS based applications from object oriented specifications. We use inference mechanisms exploiting the data structuring information and the dynamic models produced during the object oriented modeling phases to infer an appropriate relational data schema and the associated manipulation mechanisms. Thus, a designer still benefits from the advantages offered by the object oriented paradigm and receives automated support for the generation of the final relational application.

Full paper
Page generated: 17:59 14 Feb 2000 by R.Inder@ed.ac.uk