In this paper, we study the problem of processing continuous range queries in a hierarchical wireless sensor network. Recently, as the size of sensor networks increases due to the growth of ubiquitous computing environments and wireless networks, building wireless sensor networks in a hierarchical configuration is put forth as a practical approach. Contrasted with the traditional approach of building networks in a "flat" structure using sensor devices of the same capability, the hierarchical approach deploys devices of higher-capability in a higher tier, i.e., a tier closer to the server. While query processing in flat sensor networks has been widely studied, the study on query processing in hierarchical sensor networks has been inadequate. In wireless sensor networks, the main costs that should be considered are the energy for sending data and the storage for storing queries. There is a trade-off between these two costs. Based on this, we first propose a progressive processing method that effectively processes a large number of continuous range queries in hierarchical sensor networks. The proposed method uses the query merging technique proposed by Xiang et al. as the basis. In addition, the method considers the trade-off between the two costs. More specifically, it works toward reducing the storage cost at lower-tier nodes by merging more queries and toward reducing the energy cost at higher-tier nodes by merging fewer queries (thereby reducing "false alarms"). We then present how to build a hierarchical sensor network that is optimal with respect to the weighted sum of the two costs. This allows for a cost-based systematic control of the trade-off based on the relative importance between the storage and energy in a given network environment and application. Experimental results show that the proposed method achieves a near-optimal control between the storage and energy and reduces the cost by 1.002 -- 3.210 times compared with the cost achieved using the flat (i.e., non-hierarchical) setup as in the work by Xiang et al.

MEMS storage devices are new non-volatile secondary storages that have outstanding advantages over magnetic disks. MEMS storage devices, however, are much different from magnetic disks in the structure and access characteristics in the following ways. They have thousands of heads called probe tips and provide the following two major access facilities: (1) flexibility : freely selecting a set of probe tips for accessing data, (2) parallelism: simultaneously reading and writing data with the set of probe tips selected. Due to these characteristics, it is nontrivial to find data placements that fully utilize the capability of MEMS storage devices. In this paper, we propose a simple logical model called the Region-Sector (RS) model that abstracts major characteristics affecting data retrieval performance, such as flexibility and parallelism, from the physical MEMS storage model. We also suggest heuristic data placement strategies based on the RS model. To show the usability of the RS model, we derive new data placements for relational data and two-dimensional spatial data by using these strategies. Experimental results show that the proposed data placements improve the data retrieval performance by up to 4.7 times for relational data and by up to 18.7 times for two-dimensional spatial data of approximately 320 Mbytes compared with those of existing data placements. Further, these improvements are expected to be more marked as the database size grows.

A top-k keyword query in relational databases returns k trees of tuples — where the tuples containing the query keywords are connected via primary key-foreign key relationships — in the order of relevance to the query. Existing works are classified into two categories: 1) the schema-based approach and 2) the schema-free approach. We focus on the former utilizing database schema information for more effective ranking of the query results. Ranking measures used in existing works can be classified into two categories: 1) the size of the tree (i.e., the syntactic score) and 2) ranking measures, such as TF-IDF, borrowed from the information retrieval field. However, these measures do not take into account semantic relevancy among relations containing the tuples in the query results. In this paper, we propose a new ranking method that ranks the query results by utilizing semantic relevancy among relations containing the tuples at the schema level. First, we propose a structure of semantically strongly related relations, which we call the strongly related tree (SRT). An SRT is a tree that maximally connects relations based on the lossless join property. Next, we propose a new ranking method, SRT-Rank, that ranks the query results by a new scoring function augmenting existing ones with the concept of the SRT. SRT-Rank is the first research effort that applies semantic relevancy among relations to ranking the results of keyword queries. To show the effectiveness of SRT-Rank, we perform experiments on synthetic and real datasets by augmenting the representative existing methods with SRT-Rank. Experimental results show that, compared with existing methods, SRT-Rank improves performance in terms of four quality measures — the mean normalized discounted cumulative gain (nDCG), the number of queries whose top-1 result is relevant to the query, the mean reciprocal rank, and the mean average precision — by up to 46.9%, 160.0%, 61.7%, and 63.8%, respectively. In addition, we show that the query performance of SRT-Rank is comparable to or better than those of existing methods.

Web caching has become an important problem when addressing the performance issues in Web applications. The expiration time of the Web data item is useful a piece of information for performance enhancement in Web caching. In this paper, we introduce the notion of the effective reference probability that incorporates the effect of expiration time for Web caching. For a formal approach, we propose the continuous independent reference model extending the existing independent reference model. Based on this model, we define formally the effective reference probability and derive it theoretically. By simply replacing the reference probability in the existing cache replacement algorithms with the effective reference probability, we can take the effect of expiration time into account. The results of performance experiments show that the replacement algorithms using the effective reference probability always outperform existing ones. In particular, when the cache fraction is 0.05 and data update is comparatively frequent (i.e., the update frequency is more than 1/10 of the reference frequency), the performance is enhanced by more than 30% in LRU-2 and 13% in Aggarwal's method. The results show that the effective reference probability significantly enhances the performance of Web caching when the expiration time is given.

In order to enhance the performance, many database management systems (DBMSs) execute transactions at isolation level 2 rather than at isolation level 3, the strict two phase locking, even if it sacrifices consistency to a certain degree. Cursor stability, a variant of isolation level 2 in relational DBMSs (RDBMSs), has been widely used as a useful technique for obtaining concurrency achievable at level 2 without much sacrificing consistency. However, cursor stability is much less usable in object-relational DBMSs (ORDBMSs) because navigational applications in ORDBMSs can suffer from critical inconsistency problems such as dangling pointers, lost updates, and reading inconsistent complex objects. In this paper, we propose a new isolation level, navigation stability, that prevents the inconsistency problems of cursor stability for navigational applications, while avoiding significant degradation of the concurrency of level 3. First, we analyze the inconsistency problems of cursor stability for navigational applications. Second, we define navigation stability as an extension of cursor stability and show that it solves those inconsistency problems of cursor stability in ORDBMSs. Third, through extensive simulation, we show that navigation stability significantly enhances the performance compared with level 3. For workloads consisting of transactions of long duration, compared with level 3, the throughput of navigation stability is enhanced by up to 200%; the average response time reduced by as much as 55%; and the abort ratio reduced by as much as 77%. From these results, we conclude that navigation stability is a useful isolation level in ORDBMSs that can be used in place of isolation level 3 to improve the performance and concurrency without significant sacrifice of consistency.

In this paper, we consider linearization of nonlinear datalog programs with multiple bilinear rules and multiple linear rules. If a nonlinear program can be linearized, it is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. We define a transformation, called Right-Linear-First (RLF) transformation, for linearizing such nonlinear programs. A nonlinear program is RLF-linearizable if it is logically equivalent to its RLF-transformed program. We present three sufficient conditions, called LCR-consistency, LCRN1-consistency, and LCRN2-consistency, for identifying such RLF-linearizable programs. These conditions can be tested in polynomial time. Our work presented in this paper extends the work on ZYT-linearizability in a sense that RLF-linearizability considers multiple bilinear rules with multiple linear rules.

In this paper, we describe the design and implementation of a hypermedia system that has the following characteristics. First, being designed according to the Dexter hypertext reference model, it has a layered architecture and thus maintains commonality with other hypermedia systems based on the Dextermodel. Second, being designed based on the MHEG standard, it has data structures that are inherently suitable for data interchange and synchronization. Third, adopting the MIME protocol, it provides multimedia mail services. Finally, being built on top of an object-oriented DBMS, it makes it easy to represent Dexter and MHEG models and also provides efficient storage and search capabilities. The contribution of this paper is combining these characteristics to build an integrated hypermedia system reflecting reference architectures and international standard efforts.

Many object-oriented database systems have used the notion of implicit authorization to avoid the overhead caused by explicitly storing all authorizations for each object. In implicit authorization, it is very important to detect efficiently conflicts between existing authorizations and new authorizations to be added. In this article we propose a conflict detection mechanism in the OODBMSs using implicit authorization with the notion of intention type authorization. When we grant an authorization on a node n in the database granularity hierarchy, the existing method is inefficient in determining the conflicts since it needs to examine all authorizations on the descendants of the node n. In contrast, our mechanism has the advantage of detecting the conflicts at the node n where an explicit authorization is to be granted without examining any authorizations below the node n. Thus, the proposed mechanism can detect a conflict with the average time complexity of O(d), which is smaller than O(md) of existing methods, where m is the number of children nodes at an arbitrary level and d is the difference of levels between the node with an existing explicit authorization and the higher node where an explicit authorization is to be granted. We also show that the additional storage overhead of storing all authorizations is negligible when compared with the total number of all explicit authorizations.

In this paper we propose a subsequence matching algorithm that supports moving average transform of arbitrary order in time-series databases. Moving average transform reduces the effect of noise and has been used in many areas such as econometrics since it is useful in finding the overall trends. The proposed algorithm extends the existing subsequence matching algorithm proposed by Faloutsos et al. (SUB94 in short). If we applied the algorithm without any extension, we would have to generate an index for each moving average order and would have serious storage and CPU time overhead. In this paper we tackle the problem using the notion of index interpolation. Index interpolation is defined as a searching method that uses one or more indexes generated for a few selected cases and performs searching for all the cases satisfying some criteria. The proposed algorithm, which is based on index interpolation, can use only one index for a pre-selected moving average order k and performs subsequence matching for arbitrary order m ( k). We prove that the proposed algorithm causes no false dismissal. The proposed algorithm can also use more than one index to improve search performance. The algorithm works better with smaller selectivities. For selectivities less than 10-2, the degradation of search performance compared with the fully-indexed case--which is equivalent to SUB94--is no more than 33.0% when one index is used, and 17.2% when two indexes are used. Since the queries with smaller selectivities are much more frequent in general database applications, the proposed algorithm is suitable for practical situations.