Recently, a large amount of work has been done in XML data mining. However, we observed that most of the existing works focus on the snapshot XML data, while XML data is dynamic in real applications. To the best of our knowledge, none of the existing works has addressed the issue of mining the history of changes to XML documents. Such mining results can be useful in many applications such as XML change detection, XML indexing, association rule mining, and classification etc. In this paper, we propose a novel approach to discover the frequently changing structures from the sequence of historical structural deltas of unordered XML. To make the structure discovering process efficient, an expressive and compact data model, Historical-Document Object Model (H-DOM), is proposed. Using this model, two basic algorithms, which can discover all the frequently changing structures with only two scans of the XML sequence, are presented. Experimental results show that our algorithms, together with the optimization techniques, are efficient and scalable.

This presentation gives a new SPFD-based method to make a target wire redundant with higher possibility than the previous rewiring methods. After placement and routing, we obtain or estimate how much the existing and candidate wires interferes such physical design, and thus, we find out the most critical one of the existing wires. In order to remove it, the previous methods add new input wires to only one LUT. Actually, in the context of gate/cell-based logic optimization, it is well-known that input wire addition to many gates/cells is likely to make the critical one redundant. However, in an FPGA circuit, since an LUT can realize an arbitrary function for a specified number of inputs, such wire addition has never been considered to be useful. In this presentation, we provides with an SPFD-based condition for such wire addition to improve the FPGA circuit performance. We also present several experimental results to show the effectiveness of the proposed condition.

This paper proposes an innovative method for SPFD-based rewiring in Look-Up-Table-based (LUT-based) FPGA circuits. The new method adds new input wires to two or more LUT's in order to remove or to replace a target wire. There have been a few rewiring methods for FPGA circuits so far, such as the original SPFD-based optimization sometimes called Local Rewiring (LR), SPFD-based Global Rewiring (GR) and SPFD-based Enhanced Rewiring (ER). However, all of them replace one wire with other new input wire to one LUT but not with those to two or more LUT's. Moreover, the LR removes or replaces input wires with new one to the same LUT only, and the GR and ER topologically limit the LUT's where new input wires are added. Our new method, called One-to-Many Rewiring (OMR), loosens such topological constraints for more flexible FPGA circuit transformation so that it is easier to import constraints on physical design to the logic optimization. The experimental results show our OMR can transform FPGA circuits more flexibly than the LR, GR and ER, by introducing the new manipulation, wire addition. The OMR can rewire 1.2 times as many wires as the existing methods, especially, the ER. The computation time is as short as the existing methods.

We have been developing a mobile passenger guide system for public transports. Passengers can make their travel plans and purchase necessary electronic tickets using mobile terminals via Internet. During the travel, the mobile terminal, which also works as an electronic ticket, compares the stored travel plan with the passenger's actual activities and offers appropriate guide messages. To execute this task, the mobile terminal collects various kinds of information about the travel fields (routes, fares, area maps, station maps, operation schedule, timetables, facilities of stations and vehicles etc.) using multi-channel data communications. The mobile terminal contains a personal database for the passenger by selecting and integrating necessary data according to the user's situation and characteristics.

Access control policies of XML documents are often specified based on user roles and data content of the documents. Content-based authorization is crucial for providing fine-grained access control to data in XML document. Since authorization rules (authorizations, for short) use path expressions of XPath for locating data in documents, authorization definition is related to structure of the document. However, the structure of XML documents tends to change by various reasons such as application extension and information exchange between organizations. Therefore, authorizations must be revised whenever they become incompatible with a new structure of the document. As far as we know, no previous work has discussed the problem of transforming content-based authorizations for XML documents by using schema mapping information. We define classes for schema and document transformations that allow transforming authorizations without access to source and target XML documents. We propose an algorithm that computes authorizations of role-based access control (RBAC) model for a target DTD instance from given RBAC authorizations of a source DTD instance and schema mapping information under the specified classes of schema and document transformations while preserving the authorization policy of the source DTD instance.

Two different approaches in the iterative development process have been proposed for development projects using object technologies: the modeling intensive approach and the implementation intensive approach. The differences between the two approaches arise partly from differences in strategies to suppress productivity degradation by trial and error with unknown issues in development projects. Strategies of a typical modeling intensive approach, the UP (Unified Process), and those of a typical implementation intensive approach, XP (extreme programming), are discussed. To investigate the effectiveness of these strategies, implementation productivity and interface change rate are measured on a development project under the UP. A high interface change rate and low implementation productivity are observed in classes related to the solution domain. These measurement results support the effectiveness of the "suppression of rework" strategy and "suppression of change propagation" strategy, of the UP.

This paper gives a simple but nontrivial set of local transformation rules for Control-NOT(CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S1 and S2, there is a sequence of transformations, each of them in the rule set, which changes S1 to S2. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT based circuits. As a preliminary example, we give a design procedure based on our transformation rules which reduces the cost of CNOT-based circuits.

Web based services and applications have increased the availability and accessibility of information. XML has recently emerged as an important standard in the area of information representation. XML documents can represent information at different levels of sensitivity. However, XML access control models proposed in the literature enforce access restrictions directly on the structure and content of an XML document. Therefore the authorizations, which specify access rights of users on information within an XML document, must be revised whenever the structure of the XML document is changed. We present two approaches that translate the authorizations for the transformed XML document. The first approach translates instance-level authorizations by using instance-level mapping between instance nodes of source document and those of transformed document. The second approach translates schema-level authorizations by using schema mapping between schema elements of the source schema and those of the target XML schema.

A novel system, Project Data Warehouse, for the measurement of changes in development artifacts based on data warehouse technology is reported. The new system is based on an architecture that is extendable to store various kinds of UML based development artifacts and flexible to apply the various types of measurements to quantify the changes in those artifacts. Also, it provides multi-dimensional analysis of the measurement results. An application result of Project Data Warehouse to the development artifacts of a commercial development project is also reported.

This paper presents LRU-SP, a size-adjusted and popularity-aware extension to Least Recently Used (LRU) for caching web objects. The standard LRU, focusing on recently used and equal sized objects, is not suitable for the web context because web objects vary dramatically in size and the recently accessed objects may possibly differ from popular ones. LRU-SP is built on two LRU extensions, namely Size-Adjusted LRU and Segmented LRU. As LRU-SP differentiates object size and access frequency, it can achieve higher hit rates and byte hit rates. Furthermore, an efficient implementation scheme is developed and trace-driven simulations are performed to compare LRU-SP against Size-Adjusted LRU, Segmented LRU and LRV caching algorithms.

Large-scale Web caches are, in fact, localized sources of Web contents. Besides replacement policies, which decide the contents of a cache, the management of such contents is an issue of special significance to Web caching. This paper introduces our ongoing work on the research of cache content management. We propose a multi-cache-based content management scheme in which Web contents are distributed to several subcaches rather than maintained in a monolithic priority queue. This scheme is suitable for managing a large cache space and is capable of implementing sophisticated control logic. The efficiency of this scheme is demonstrated by the design and implementation of a new replacement policy. Trace-driven simulations are used to evaluate these results.

One of the serious problems of distance learning systems is how to teach many students on an individual basis. The authors design an educational method, dynamic group guidance using quiz functions for network based lecturing, and present an implementation method. Using the dynamic group guidance function, the system groups students automatically according to the results of quizzes and a teacher can guide each group individually. Supported by the system, therefore, a teacher can guide every student in a lecture efficiently according to his/her own level of understanding. We have realized the system using two technologies: user profiling and software agents.

Due to the development of computer systems and computer networks such as the Internet, people are taking advantage of these systems for distance learning. We have been developing an advanced distance learning system called VIEW Classroom. In conventional systems communication from a lecturer to students is considered to be the most important function. Although communication from students to a lecturer is also essential, most systems ignore the importance of communication among students. Students can study through discussion among themselves. Conventional chat systems are not suitable for such purposes, since proper guidance of discussion from a lecturer cannot be realized. A lecturer has to observe and control discussions among students. For this purpose we need to develop various kinds of visualization functions for distributed discussion systems. Visualization and control functions are introduced in order to satisfy these requirements. A prototype system is developed for VIEW Classroom and the usefulness of these functions are shown.

Since it is necessary to realize virtual organizations in networks, to develop systems to be used for realizing various kinds of cooperation support among users is very important as a basis of virtual organizations. VIEW Media has been developed for such a purpose, utilizing CSCW (Computer Supported Cooperative Work) and database technologies. By introducing the concept of environment, VIEW Media supports flexible information sharing mechanisms. The major purpose of this paper is to show the advantages of the environment model for flexible sharing. Several well-known models are compared and then a representative model, the room model, is selected for comparison to develop the same application. Since the environment model is more general than the room model, we decided to develop "debate systems" which are rather complicated yet can be realized by both models. Debate systems can be regarded as generalization of conference systems and thus we believe the comparison is appropriate. By real usage of debate systems developed by VIEW Media (the environment model) and TeamWave (the room model), the environment model is shown to be suitable for such applications.

Business processes such as workflows are software too. However, development, evolution, and deployment of business processes have different difficulties to general software. Control, introduction, evaluation, and testing of business processes are difficult because multiple processes are related to each other and many people are involved in the processes. To solve these problems, we propose BPT/BPR/BPS (Business Process Tactics, Reengineering, and Simulation) lifecycle, based on a multi-agent groupware model. BPT means activities to control processes dynamically which have already been proposed. The simulation phase is mainly focused upon. A simulation model is presented which has some original aspects, and a prototype simulation tool is shown.

With rapid growth of recent development of computer and network technologies, the amount of data produced, transmitted and stored is growing enormously. The variety of data to be processed is widely spreading all over the world. We are facing the third communication revolution after the invention of printing technology and mass-communication. Databases are key technology for the coming network-age. To promote such research areas, Japanese Ministry of Education, Science, Sports and Culture had decided to sponsor the Scientific on Priority Areas entitled Research and Development of Advanced Database Systems for Integration of Media and User Environments (Research Project on Advanced Databases, in short.).

VIEW Media is a cooperative hypermedia system, which supports cooperative work utilizing hypermedia documents. It provides fundamental functions for cooperative work support systems and enables developers to construct various groupware such as distributed presentation systems, education systems, conference systems, and so forth. This system provides a powerful and flexible mechanism of customization. The mechanism can alter presentation, structure, behavior and authority of hypermedia documents and workspace, which supports dynamic change of roles of users. This paper describes the purpose of VIEW Media, its basic model and implementation, and a user interface which supports conferences among users who have different access rights to shared documents.

In order to support the interaction betweeen coexisting traditional short transactions and long cooperative transactions, we propose a novel timestamp ordering approach. With this timestamp ordering method, short transactions can be processed in the traditional way, as if there were no cooperative transactions. Therefore they will not be blocked by cooperative transactions. Cooperative transactions will not be aborted when there is a conflict with short transactions. Rather, they will incorporate the recent updates into their own processing. The serializabilities, among short transactions, and between a cooperative transaction (group) and other short transactions, are all preserved.

For computer-supported cooperative work (CSCW), it is very important to understand the activities of users in a group. To support this understanding, we propose a mechanism called an "action history view" which shows the past actions of a user to other users for the purpose of letting them know what he/she has done, without revealing secret or useless information. The mechanism is coordinated among users who are distributed in terms of time. In this paper, the concept of the action history view mechanism is applied to hypermedia systems based on an object-oriented model to support users in viewing or reviewing past presentations in a short amount of time in hiding specified actions which it is not appropriate to show to other users. The generation of views is executed by removing a series of actions that correspond with the component to be hidden. The system also has a function for supporting users to select actions interactively while the user is viewing the replay. To qualify those kinds of views, the actions performed in a presentation are recorded in an action history stream, which consists of multiple logs. Finally, the application and implementation of a prototype of the action history view mechanism to a distance education system based on hypermedia is described.

In order to support both traditional short transaction and long cooperative transactions, we propose a novel timestamp ordering approach. With this timestamp ordering method, short transactions can be processed in the traditional way, as if there are no cooperative transactions, therefore not be blocked by long transactions; cooperative transactions will not be aborted when there is a conflict with short transactions, rather it will incorporate the recent updates into its own processing; and the serializabilities, among short transactions, and between a cooperative transaction (group) and other short transactions, are all preserved.

In conventional computer supported cooperative work (CSCW) systems, usually only one video-based environment is shared by all the users. In this paper, we show that multiple environments are required and they can be realized by utilizing object-oriented database technology. A cooperative work environment can be regarded as a room where users work together by sharing documents and equipment through available communication facilities. In one environment, users, documents and equipment are handled as objects, and these different types of objects have some attributes and methods in common, such as location attributes and layout methods. However, using the existing concepts of the conventional object-oriented model, such as classes, complex objects and collection objects, it is difficult to define one environment: namely, a set with different types of elements but having some attributes and methods in common. The object deputy model, introduced by the authors, can be extended to formulate such environments. Since the object deputy model can uniformly handle object views, roles, migration and multiple inheritance, we can realize flexible, dynamic and powerful environments based on object-oriented databases.

Distributed multi-user hypermedia environments provide not only information-sharing mechanisms but also user collaboration/communication facilities. The provision of integrated views of heterogeneous information resources is necessary to create a common understanding among the users, who are possibly distributed in terms of geography and time. However, the requirements of customization must also be considered, since such diverse users would want to personalize their views of shared information. In order to integrate these views while considering the requirements of flexible customization, we propose cooperative view mechanisms of Dexter-based hypermedia systems, introducing environmental objects and their participation relationships. The mechanisms instantiate hypermedia deputies on the screen using participation relationships of the users, hypermedia components and environments. The relationships are also used for the purpose of supporting awareness. Using a novel user collaboration facility, the relationships are visualized so that users can easily recognize other users and/or user groups having the same, slightly different or very different views. Attributes of environment objects are discussed so that the mechanisms can be effectively utilized in computer-supported cooperative work settings such as distance presentations, virtual offices and virtual classrooms.

We have been developing an important application of distributed systems: a distance education system called VIEW Classroom. Conventional distance education systems use video images of teachers and selected students when required. From its initial stages, this system has taken a non-video base (although video function can be utilized) and tried to use database technology extensively in order to assist the whole range of teaching and learning activities. Typical features of VIEW Classroom are presented. (1) Asynchronous interaction support: many conventional education systems are based on synchronous interaction, though asynchronous interaction can be also realized by object oriented database functions. (2) Database views: teacher and student can see different teaching materials if required. (3) Question-answer database: in order to answer questions issued by students, previously asked questions are stored together with corresponding answers in question-answer databases for such a purpose. (4) Database to analyze student achievement: we store abstracted information of student actions during the lecture, which can be used to improve the teaching material. The database can be regarded as a kind of temporal database which also stores past achievement data on each student. Extensive use of such database technology is a promising way for next generation distance education systems.

No abstract available.

Concepts of deputy objects and deputy classes for object-oriented databases (OODBs) are introduced. They can be used for unified realization of object views, roles and migration. The previous researches on these concepts were carried out separately, although they are very closely related. Objects appearing in a view can be regarded as playing roles in that view. Object migration is caused by change of roles of an object. Deputy objects can be used for unified treatment of them and generalization of these concepts. The schemata of deputy objects are defined by deputy classes. A set of algebraic operations are developed for deputy class derivation. In addition, three procedures for update propagation between deputy objects and source objects have been designed, which can support dynamic classification. The unified realization of object views, roles and migration by deputy mechanisms can achieve the following advantages. (1) Treating view objects as roles of an object allows them to have additional attributes and methods so that the autonomous views suitable for OODBs can be realized. (2) Handling object roles in the same way as object views enables object migration to be easily realized by dynamic classification functions of object views. (3) Generalization of object views, roles and migration makes it possible that various semantic constraints on them can, be defined and enforced uniformly.>

A continuous-backup mechanism for main-memory databases that transmits data to archive storage during utilization of main memory without any software assistance is described. It is suggested that flash memory-based storage can improve the efficiency of conventional disk systems since it can realize faster read and write operations. As sequential access is performed by a series of direct accesses, the overhead caused by scheduling to utilize sequential access is not required. One serious drawback of flash memory is the limit of the number of rewrite operations. Mechanisms that have a five-year lifetime have been developed using existing technology. Results of a performance evaluation of the backup system are presented.>

An approach for unifying subject-specific data grouping and knowledge grouping through derived database patterns is proposed. As database patterns can be specified in terms of nested relations, a nested relation based knowledge representation framework is developed to support this approach. The proposed framework is characterized by extending the fundamental notions at set theory level to underlie the notions at LP theory level. As a result, it has strong expressive power of dealing with hierarchically nested tuples and sets and is canonical and analogous to first-order LP framework.>

Efficient procedures for producing nested relations from networks are considered. Various types of nested relations are defined according to the interaction between the networks' and nested relations' schemas. Among these types, partitional normal form (PNF) and accordant nested relations are shown to be produced by an extended navigation, called touch information display (TID) navigation, which requires time proportional to the number of tuples in the relation. It is demonstrated that a network can effectively produce a variety of nested relations by navigation. The efficiency of production is classified according to the interaction between the schemas of networks and targets. Non-PNF and/or non-accordant targets are generated using duplicate depletion. On the other hand, PNF and accordant targets can be generated using only navigation, which requires linear time in the number of tuples in the relation. Furthermore, for the cases on non-PNF and non-accordant targets, the TID method exploits the existence of links, so that the size of the region of the subrelation upon which deletion of duplicated values should be performed is limited.>

article Free Access Share on Nested relation based database knowledge representation Authors: Qiming Chen Computer Science Dept., University of California, Los Angeles Computer Science Dept., University of California, Los AngelesView Profile , Yahiko Kambayashi Computer Science Dept., University of Kyoto, Kyoto, Japan Computer Science Dept., University of Kyoto, Kyoto, JapanView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 328–337https://doi.org/10.1145/119995.115849Online:01 April 1991Publication History 15citation658DownloadsMetricsTotal Citations15Total Downloads658Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Based on the new concept of permissible functions, a heuristic procedure to design logic networks with as few gates as possible, without guaranteeing the minimality of designed networks, is developed. This procedure, which is drastically different from conventional logic-design procedures, is called the transduction method, because an initial network designed by any conventionally known logic-design method is first transformed into a different network configuration and then reduced to a simpler network by calculating permissible functions at the outputs of gates and connections throughout the network.>

When we design networks with NOR or NAND gates which are implemented with bipolar and MOS transistors, wired logic is usually allowed. The usage of wired logic reduces the network cost and possibly improves the speed because of shorter delays on wired logic than on a gate. Typical logic functions performed by wired logic are AND and OR, which are called wired-AND and wired-OR, respectively. Properties of networks with NOR gates and wired-AND (or wired-OR) are discussed. Some of these properties are used in developing synthesis procedures of optimum networks by the integer programming logic design method. For all three-variable functions, the optimum networks with NOR gates and wired-OR's, designed by this synthesis approach, are shown.

Since join operations are expensive, usually join scheduling is very important for query processing. In this paper we will discuss new procedures to handle cyclic queries utilizing dependencies and horizontal decompositions. There are three known procedures for cyclic query processing: (1) Relation merging, (2) Tuple-wise processing, (3) Attribute addition. As join operations are applied to relations which are processed by selection operations, the number of tuples is usually less than the original relation and thus there are situations in which temporary FDs are satisfied. Such FDs can be used to simplify the given query. To convert a given cyclic query into a tree, some relations must satisfy a set of FDs. This can be attained by horizontal decomposition. Tuple-wise processing and attribute addition are shown to be special cases of the FD-based procedure. We have also developed MVD-based procedures which are generalized from the FD-based procedure.

In distributed database systems, the cost to process a query is mainly determined by the amount of communication. Semi-join is a very useful tool to reduce the cost of joins in such systems. There are, however, queries called cyclic ones which cannot be processed by semi-joins only. In this paper the concept of generalized semi-joins is introduced to solve such a problem. To handle an arbitrary cyclic query, first a spanning tree is selected in the corresponding query graph and then generalized semi-joins are applied in the order determined by the tree. Processing of cyclic queries, however, requires more communication cost than processing of tree queries, since in the former case we need to transmit attribute values which are not required in the latter case. A procedure to reduce the communication cost of such additional data is developed, which will make the generalized semi-join based procedures practical.

In this paper, we mainly discuss the semantic aspects of functional and multivalued dependencies in order to choose a better logical design of a relational database. We clarify the differences between a conceptual design and a logical design of a relational database. For example, a multivalued dependency does not always capture a conceptual dependency such that a data element semantically determines a set of other data elements. Moreover, some transitively specified multivalued dependencies are shown to often impose a semantically unnatural constraint. A sufficient condition for these multivalued dependencies to hold in a natural sense is provided. A mixed design approach of a conceptual and a logical designs is introduced, in which each design approach is compensated for its deficiency by the other one. Some generalization of a relational model is also suggested to handle some interface problems between a logical design and a conceptual design, such as a null value problem and an entity identification problem.

In the database field, the requirement of high level facilities for retrieval/update operations is now increasing rapidly. Our approach from the relational database point of view for contribution to this problem is to provide 1) efficient processing of relational retrieval/ update operations, and 2) a high level user interface. In order to achieve this goal, a new concept concerning "abstracted characteristics" is presented. Abstracted characteristics are defined to be characteristics abstracted from sets of tuples in relations stored in the database. A classification of abstracted characteristics is presented. Functional dependencies, which play an important role in relational database design, and time-dependent functional dependencies are pointed out to be useful in processing retrieval/update operations. Some important applications of abstracted characteristics are discussed. Among them: 1) efficient processing of retrieval/update operations, 2) powerful view update checking facilities, 3) providing some rough meanings of null responses and 4) a high level user interface.

Compared with random logic circuits, memory-type circuits are more suitable for LSI realization since their iterated structure of identical cells results in higher transistor density and higher yield. A programmable logic array (PLA) is a read only memory (ROM) with programmable addresses and it is suitable for realizing logic functions with many unspecified input combinations. For such a function, reduction of the number of input is possible in many cases. Since the cost of a PLA is mainly determined by the number of pins and the chip, both of which are affected by the number of inputs, the reduction of the number of inputs is very important in PLA design. On the other hand, the reduction of the number of product terms in a sum-of-product expression is important in conventional random logic synthesis. Since there is a tradeoff problem between the number of inputs and the number of product terms, we give a design procedure by the following preference order: 1) minimizing the number of pins, 2) minimizing the number of product terms, 3) minimizing the number of circuits used in the PLA. These factors also determine the area required for a chip.

This paper shows that 1) there exist at least four types of binary-input binary-output maximum-memory n-state machines for any n; 2) there exist binary-input ternary-output maximum output -memory n-state machines for any n; and 3) there exists a binary- input binary-output maximum output-memory n-state machine for n≤5.