An approach for high-yield requirements capture for e-commerce and its application

Web-based e-commerce software is typically real-time, responsive, and distributed software that must meet high quality requirements. Moreover, because of its Internet-based operating environment, e-commerce software must deal with concurrency, synchronization, and non-deterministic issues (such as delays) primarily caused by the heavy usage load and underlying network conditions. In this paper, we introduce a generic, cost-effective approach to optimize requirements capture (and subsequent development and testing) with respect to functional coverage and customer perception of quality. This high-yield approach is presented and illustrated by application to an e-commerce online shopping system and used to explain the principles of use-case requirements captured in the unified modeling language. Published online: 25 July 2001     

A survey of approaches to automatic schema matching

Schema matching is a basic problem in many database application domains, such as data integration, E-business, data warehousing, and semantic query processing. In current implementations, schema matching is typically performed manually, which has significant limitations. On the other hand, previous research papers have proposed many techniques to achieve a partial automation of the match operation for specific application domains. We present a taxonomy that covers many of these existing approaches, and we describe the approaches in some detail. In particular, we distinguish between schema-level and instance-level, element-level and structure-level, and language-based and constraint-based matchers. Based on our classification we review some previous match implementations thereby indicating which part of the solution space they cover. We intend our taxonomy and review of past work to be useful when comparing different approaches to schema matching, when developing a new match algorithm, and when implementing a schema matching component. Received: 5 February 2001 / Accepted: 6 September 2001 Published online: 21 November 2001     

An Internet-based negotiation server for e-commerce

This paper describes the design and implementation of a replicable, Internet-based negotiation server for conducting bargaining-type negotiations between enterprises involved in e-commerce and e-business. Enterprises can be buyers and sellers of products/services or participants of a complex supply chain engaged in purchasing, planning, and scheduling. Multiple copies of our server can be installed to complement the services of Web servers. Each enterprise can install or select a trusted negotiation server to represent his/her interests. Web-based GUI tools are used during the build-time registration process to specify the requirements, constraints, and rules that represent negotiation policies and strategies, preference scoring of different data conditions, and aggregation methods for deriving a global cost-benefit score for the item(s) under negotiation. The registration information is used by the negotiation servers to automatically conduct bargaining type negotiations on behalf of their clients. In this paper, we present the architecture of our implementation as well as a framework for automated negotiations, and describe a number of communication primitives which are used in the underlying negotiation protocol. A constraint satisfaction processor (CSP) is used to evaluate a negotiation proposal or counterproposal against the registered requirements and constraints of a client company. In case of a constraint violation, an event is posted to trigger the execution of negotiation strategic rules, which either automatically relax the violated constraint, ask for human intervention, invoke an application, or perform other remedial operations. An Event-Trigger-Rule (ETR) server is used to manage events, triggers, and rules. Negotiation strategic rules can be added or modified at run-time. A cost-benefit analysis component is used to perform quantitative analysis of alternatives. The use of negotiation servers to conduct automated negotiation has been demonstrated in the context of an integrated supply chain scenario. Received: 30 October 2000 / Accepted: 12 January 2001 Published online: 2 August 2001     

Universal Access in the Information Society: Methods, Tools, and Interaction Technologies

Accessibility and high quality of interaction with products, applications, and services by anyone, anywhere, and at any time are fundamental requirements for universal access in the emerging Information Society. This paper discusses these requirements, and their relation to the concept of automated adaptation of user interfaces. An example application is presented, showing how adaptation can be used to accommodate the requirements of different user categories and contexts of use. This application is then used as a vehicle for discussing a new engineering paradigm appropriate for the development of adaptation-based user interfaces. Finally, the paper investigates issues concerning the interaction technologies required for universal access. Published online: 23 May 2001     

Active rules for XML: A new paradigm for E-services

XML is rapidly becoming one of the most widely adopted technologies for information exchange and representation. As the use of XML becomes more widespread, we foresee the development of active XML rules, i.e., rules explicitly designed for the management of XML information. In particular, we argue that active rules for XML offer a natural paradigm for the rapid development of innovative e-services. In the paper, we show how active rules can be specified in the context of XSLT, a pattern-based language for publishing XML documents (promoted by the W3C) which is receiving strong commercial support, and Lorel, a query language for XML documents that is quite popular in the research world. We demonstrate, through simple examples of active rules for XSLT and Lorel, that active rules can be effective for the implementation of e-commerce services. We also discuss the various issues that need to be considered in adapting the notion of relational triggers to the XML context. Received: 30 October 2000 / Accepted: 19 December 2000 Published online: 27 April 2001     

Creating word-level language models for large-vocabulary handwriting recognition

We discuss development of a word-unigram language model for online handwriting recognition. First, we tokenize a text corpus into words, contrasting with tokenization methods designed for other purposes. Second, we select for our model a subset of the words found, discussing deviations from an N-most-frequent-words approach. From a 600-million-word corpus, we generated a 53,000-word model which eliminates 45% of word-recognition errors made by a character-level-model baseline system. We anticipate that our methods will be applicable to offline recognition as well, and to some extent to other recognizers, such as speech recognizers and video retrieval systems. Received: November 1, 2001 / Revised version: July 22, 2002     

ObjectGlobe: Ubiquitous query processing on the Internet

We present the design of ObjectGlobe, a distributed and open query processor for Internet data sources. Today, data is published on the Internet via Web servers which have, if at all, very localized query processing capabilities. The goal of the ObjectGlobe project is to establish an open marketplace in which data and query processing capabilities can be distributed and used by any kind of Internet application. Furthermore, ObjectGlobe integrates cycle providers (i.e., machines) which carry out query processing operators. The overall picture is to make it possible to execute a query with – in principle – unrelated query operators, cycle providers, and data sources. Such an infrastructure can serve as enabling technology for scalable e-commerce applications, e.g., B2B and B2C market places, to be able to integrate data and data processing operations of a large number of participants. One of the main challenges in the design of such an open system is to ensure privacy and security. We discuss the ObjectGlobe security requirements, show how basic components such as the optimizer and runtime system need to be extended, and present the results of performance experiments that assess the additional cost for secure distributed query processing. Another challenge is quality of service management so that users can constrain the costs and running times of their queries. Received: 30 October 2000 / Accepted: 14 March 2001 Published online: 7 June 2001     

Semantic integrity support in SQL:1999 and commercial (object-)relational database management systems

The correctness of the data managed by database systems is vital to any application that utilizes data for business, research, and decision-making purposes. To guard databases against erroneous data not reflecting real-world data or business rules, semantic integrity constraints can be specified during database design. Current commercial database management systems provide various means to implement mechanisms to enforce semantic integrity constraints at database run-time. In this paper, we give an overview of the semantic integrity support in the most recent SQL-standard SQL:1999, and we show to what extent the different concepts and language constructs proposed in this standard can be found in major commercial (object-)relational database management systems. In addition, we discuss general design guidelines that point out how the semantic integrity features provided by these systems should be utilized in order to implement an effective integrity enforcing subsystem for a database. Received: 14 August 2000 / Accepted: 9 March 2001 / Published online: 7 June 2001     

Zero-suppressed BDDs and their applications

In many real-life problems, we are often faced with manipulating sets of combinations. In this article, we study a special type of ordered binary decision diagram (OBDD), called zero-suppressed BDDs (ZBDDs). This data structure represents sets of combinations more efficiently than using original OBDDs. We discuss the basic data structures and algorithms for manipulating ZBDDs in contrast with the original OBDDs. We also present some practical applications of ZBDDs, such as solving combinatorial problems with unate cube set algebra, logic synthesis methods, Petri net processing, etc. We show that a ZBDD is a useful option in OBDD techniques, suitable for a part of the practical applications. Published online: 15 May 2001     

The Context of Information Use in a Hospital as Simultaneous Similarity–Difference Relations

In the light of the developing discourse on the relative merits of ‘hard’ and ‘soft’ approaches to information systems development, we present a case study application of a methodology which attempts to dissolve such dualities. Personal Construct Psychology (PCP) offers, as a unity, the construing person who is both biology and culture. PCP argues that both the world and the person’s construct system are phenomenologically real and that the viability of any particular construct system depends only on its usefulness to the construing person. In this study, we used PCP to explore the organisational context of information use and distribution in a large hospital. We used repertory grids, a PCP technique, to elicit from 16 members of staff their personal construals of information from different sources in the hospital. The results highlight the relationship between meaningful information and meaningfully active relationships, a theme which we discuss in terms of the development of the hospital information system and in terms of the value of PCP in dissolving hard–soft dichotomies.     

Binary decision diagrams in theory and practice

Decision diagrams (DDs) are the state-of-the-art data structure in VLSI CAD and have been successfully applied in many other fields. DDs are widely used and are also integrated in commercial tools. This special section comprises six contributed articles on various aspects of the theory and application of DDs. As preparation for these contributions, the present article reviews the basic definitions of binary decision diagrams (BDDs). We provide a brief overview and study theoretical and practical aspects. Basic properties of BDDs are discussed and manipulation algorithms are described. Extensions of BDDs are investigated and by this we give a deeper insight into the basic data structure. Finally we outline several applications of BDDs and their extensions and suggest a number of articles and books for those who wish to pursue the topic in more depth. Published online: 15 May 2001     

Multimedia mail

Electronic mail for traditional text exchange as asynchronous communication means between computer users is widely built upon in many application areas. Whereas Multimedia-Mail systems – including text, graphics, still images, audio, video and documents – were limited to isolated communities – at least two very promising approaches are being under development: the MIME (Multipurpose Internet Mail Extension), an extension of Internet Mail as well as the Multimedia Teleservice based on CCITT Recommendation X.400(88) being under development within the BERKOM project funded by the German TELEKOM. The store-and-forward mechanism inherent to electronic mail is complemented in the later one by an additional exchange mechanism allowing the resolution of references to message content, e.g. video. Such references may be put into a message in place of the content itself. Internet/MIME and OSI/X.400, their interworking, asynchronous information server access via Multimedia-Mail, as well as possible future developments especially in the area of asynchronous Computer Supported Cooperative Work (CSCW) are discussed.     

Genetic algorithms for clustering in machine vision

The paper presents a genetic algorithm for clustering objects in images based on their visual features. In particular, a novel solution code (named Boolean Matching Code) and a correspondent reproduction operator (the Single Gene Crossover) are defined specifically for clustering and are compared with other standard genetic approaches. The paper describes the clustering algorithm in detail, in order to show the suitability of the genetic paradigm and underline the importance of effective tuning of algorithm parameters to the application. The algorithm is evaluated on some test sets and an example of its application in automated visual inspection is presented. Received: 6 August 1996 / Accepted: 11 November 1997     

Easy concurrency

Advances in technology raise expectations. As far as software engineering is concerned, the common expectation is that coding and deploying applications is going to be simple. It seems, though, that software engineering is not getting easier, and the complexity moves to an application domain. One of the sources of complexity is an application concurrency. It is not an uncommon development practice that concurrency and transaction management in multi-user, multi-threaded, event-driven applications are postponed until after most of the required functionality is implemented. This situation has various explanations. On the one hand, business logic may require access and modification of large sets of inter-connected application objects. On the other, testing and stress-testing of this logic becomes possible only at advanced stages of product development. At these stages, increasing lock granularities may appear to be less "expensive" than debugging race conditions and deadlocks. Coarse-grained locking has, of course, an adverse effect on application scalability. Declaring rules of concurrency outside of the application may solve part of the problem. This paper presents an approach allowing developers to define concurrency in application-specific terms, design it in the early stages of development, and implement it using a documented API of the concurrency engine (CE). Simple notation makes it possible to record concurrency specifications in terms of application operations, relationships between application resources, and synchronization conflicts between operations. These concepts are demonstrated on examples. The final sections include the CE UML diagram, notes on API usage, and performance benchmarks. Published online: 25 July 2001     

Preface by the section editor

The papers in this special section present a sampling of new symbolic approaches for determining whether or not a system satisfies its specification. Abstracts of these articles appeared originally in the Proceedings of the 1999 Symposium on Tools and Algorithms for the Construction and Analysis of Systems (TACAS ’99). Published online: 18 July 2001     

PicoDBMS: Scaling down database techniques for the smartcard

Smartcards are the most secure portable computing device today. They have been used successfully in applications involving money, and proprietary and personal data (such as banking, healthcare, insurance, etc.). As smartcards get more powerful (with 32-bit CPU and more than 1 MB of stable memory in the next versions) and become multi-application, the need for database management arises. However, smartcards have severe hardware limitations (very slow write, very little RAM, constrained stable memory, no autonomy, etc.) which make traditional database technology irrelevant. The major problem is scaling down database techniques so they perform well under these limitations. In this paper, we give an in-depth analysis of this problem and propose a PicoDBMS solution based on highly compact data structures, query execution without RAM, and specific techniques for atomicity and durability. We show the effectiveness of our techniques through performance evaluation. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 23 July 2001     

A tool for model-checking Markov chains

Markov chains are widely used in the context of the performance and reliability modeling of various systems. Model checking of such chains with respect to a given (branching) temporal logic formula has been proposed for both discrete [34, 10] and continuous time settings [7, 12]. In this paper, we describe a prototype model checker for discrete and continuous-time Markov chains, the Erlangen–Twente Markov Chain Checker E⊢MC², where properties are expressed in appropriate extensions of CTL. We illustrate the general benefits of this approach and discuss the structure of the tool. Furthermore, we report on successful applications of the tool to some examples, highlighting lessons learned during the development and application of E⊢MC². Published online: 19 November 2002 Correspondence to: Holger Hermanns     

The Petri Net Kernel An infrastructure for building Petri net tools

The Petri Net Kernel is an infrastructure for building Petri net tools. It relieves the programmer of a Petri net tool from implementing standard operations on Petri nets and a graphical user interface. In this paper, we discuss the motivation, the concepts, and the implementation of the Petri Net Kernel. Published online: 25 July 2001