40447136
On Designing Relational Database Schemes for Efficient Query Processing
In relational databases, operations including joins sometimes become a cause of performance problems. We study scheme transformations to reduce the number of joins used by a class of routine database activities whose access patterns are fixed. Two scheme operations, merge and copy, are defined to transform relation schemes. The former merges two relation schemes into one, and the latter copies a functional dependency of a relation scheme to its tightly related relation scheme. Necessary and sufficient conditions are shown for applying these operations to a database scheme such that no new anomalies occur. From the necessity of the conditions, the database scheme obtained by exhaustive applications of these operations as long as the conditions hold, is optimal in the sense that further application of one of the scheme operations to the database scheme would cause anomalies. It is also proved that the resulting view of a retrieval on the original database scheme is equivalent to that of the corresponding retrieval on the new database scheme.
32882610
Membership Problems for Data Dependencies in Relational Expressions
In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied). 
 
Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E. 
 
Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in R1⋈⋯⋈Rs, where R1,…,Rs are relation schemes with FDs and MVDs, and Ri⋈Rj is the natural join of Ri and Rj.
5334322
Performance analysis of disk allocation method using error-correcting codes
The problem of distributing a Cartesian product file on multiple disks to maximize the parallelism for partial match queries is addressed. C. Faloutsos et al. (1989) have proposed an allocation method for Cartesian product files on multiple disks by using linear error-correcting codes. The performance of the allocation method is analyzed. Some conditions under which the allocation method is strictly optimal for queries with a given number of unspecified attributes are presented. A necessary and sufficient condition for a linear code to give a strictly optimal allocation method is discussed. Formulas for the average response time on queries with w unspecified attributes, denoted T/sub w/, in terms of the weight distribution of the code or its dual code, and formulas for the average response time Ton all queries, are given. Several examples whose average response times T/sub w/ or T are close to theoretical lower bounds are presented. >
31816332
Source location problems considering vertex-connectivity and edge-connectivity simultaneously
Let G = (V, E) be an undirected multigraph, where V and E are a set of vertices and a set of edges, respectively. Let k and l be fixed nonnegative integers. This paper considers location problems of finding a minimum-size vertex-subset S ⊆ V such that for each vertex x ∈ V the vertex-connectivity between S and x is greater than or equal to k and the edge-connectivity between S and x is greater than or equal to l. For the problem with edge-connectivity requirements, that is, k = 0, an O(L(|V|, |E|, l)) time algorithm is already known, where L(|V|, |E|, l) is the time to find all h-edge-connected components for h = 1, 2, … , l and O(L(|V|, |E|, l)) = O(|E| + |V|2 + |V|min{|E|, l|V|}min{l, |V|}) is known. In this paper, we show that the problem with k ≥ 3 is NP-hard even for l = 0. We then present an O(L(|V|, |E|, l)) time algorithm for 0 ≤ k ≤ 2 and l ≥ 0. Moreover, we prove that the problem parameterized by the size of S is fixed-parameter tractable (FPT) for k = 3 and l ≥ 0. © 2002 Wiley Periodicals, Inc.
7115154
MTcast: Robust and Efficient P2P-Based Video Delivery for Heterogeneous Users
In this paper, we propose a new video delivery method called MTcast (Multiple Transcode based video multicast) which achieves efficient simultaneous video delivery to multiple users with different quality requirements by relying on user nodes to transcode and forward video to other user nodes. In MTcast, each user specifies a quality requirement for a video consisting of bitrate, picture size and frame rate based on the user's environmental resource limitation. All users can receive video with the specified quality (or near this quality) along a single delivery tree. The main characteristics of MTcast are in its scalability, high user satisfaction degree in received video quality, short startup latency and robustness against node failure. Through simulations, we have confirmed that MTcast can achieve much higher user satisfaction degree and robustness against node failure than the layered multicast method.
29071607
Eigenvector Algorithms with Reference Signals for Frequency Domain BSS
This paper describes blind source separation (BSS) problems in the frequency domain using an eigenvector algorithm (EVA) with reference signals. The proposed EVA has such an attractive feature that all source signals are separated simultaneously from their mixtures. This is an advantage against the methods using deflation process (e.g., super-exponential method), because those methods sometimes do not work so as to converge to desired solutions, due to deflation failure. Computer simulation demonstrates the validity of the proposed EVA.
18174475
Implication Problems for Functional Constraints on Databases Supporting Complex Objects
Virtually all semantic or object-oriented data models assume that objects have an identity separate from any of their parts and allow uses to define complex object types in which part values may be any other objects. In G. E. Weddell (ACM Trans. Database Systems17, No. 1 (1992), 32-64), a more general form of functional dependency is proposed for such models in which component attributes may correspond to descriptions of property paths, called path functional dependencies (PFDs). The main contribution of the reference is a sound and complete axiomatization for PFDs when databases may be infinite. However, a number of issues were left open which are resolved in this paper. We first prove that the same axiomatization remains complete if PFDs are permitted empty left-hand sides, but that this is not true if logical consequence is defined with respect to finite databases. We then prove that the implication problem for arbitrary PFDs is decidable. The proof suggests a means of characterizing an important function closure which is then used to derive an effective procedure for constructing a deterministic finite state automaton representing the closure. The procedure is further refined to efficient polynomial time algorithms for the implication problem for cases in which antecedent PFDs are a form of complex key constraint.
16000193
Cheat detection for MMORPG on P2P environments
In this paper, we propose a new method for detecting cheat in P2P-based MMORPG. We suppose a typical P2P-based event delivery architecture where the entire game space is divided into subareas and a responsible node (selected from player terminals) delivers each event happened in the sub-area to player nodes there every predetermined time interval called timeslot. In the proposed method, we introduce multiple monitor nodes (selected from player terminals) which monitor the game state and detect cheat when it happens. In order to allow monitor nodes to track the correct game states for the corresponding subarea, we let monitor nodes and a responsible node retain a random number seed and player nodes send their events not only to responsible node but also monitor nodes so that the monitor nodes and the responsible node can uniquely calculate the latest game state from the previous game state and game events which happened during the current timeslot. Either responsible node, monitor nodes or player nodes can detect cheat by comparing hash values of game state which are retained by those nodes periodically, and role back events happened since the last correct game state. Through experiments in PlanetLab, we show that our method achieves practical performance to detect cheats.