Structured document storage and refined declarative and navigational access mechanisms in HyperStorM

The combination of SGML and database technology allows to refine both declarative and navigational access mechanisms for structured document collection: with regard to declarative access, the user can formulate complex information needs without knowing a query language, the respective document type definition (DTD) or the underlying modelling. Navigational access is eased by hyperlink-rendition mechanisms going beyond plain link-integrity checking. With our approach, the database-internal representation of documents is configurable. It allows for an efficient implementation of operations, because DTD knowledge is not needed for document structure recognition. We show how the number of method invocations and the cost of parsing can be significantly reduced. Edited by Y.C. Tay. Received April 22, 1996 / Accepted March 16, 1997     

Query processing techniques for arrays

Arrays are a common and important class of data. At present, database systems do not provide adequate array support: arrays can neither be easily defined nor conveniently manipulated. Further, array manipulations are not optimized. This paper describes a language called the Array Manipulation Language (AML), for expressing array manipulations, and a collection of optimization techniques for AML expressions. In the AML framework for array manipulation, arbitrary externally-defined functions can be applied to arrays in a structured manner. AML can be adapted to different application domains by choosing appropriate external function definitions. This paper concentrates on arrays occurring in databases of digital images such as satellite or medical images. AML queries can be treated declaratively and subjected to rewrite optimizations. Rewriting minimizes the number of applications of potentially costly external functions required to compute a query result. AML queries can also be optimized for space. Query results are generated a piece at a time by pipelined execution plans, and the amount of memory required by a plan depends on the order in which pieces are generated. An optimizer can consider generating the pieces of the query result in a variety of orders, and can efficiently choose orders that require less space. An AML-based prototype array database system called ArrayDB has been built, and it is used to show the effectiveness of these optimization techniques. Edited by M. Carey. Received: 10 August 2001 / Accepted: 11 December 2001 Published online: 24 May 2002     

Global transaction support for workflow management systems: from formal specification to practical implementation

In this paper, we present an approach to global transaction management in workflow environments. The transaction mechanism is based on the well-known notion of compensation, but extended to deal with both arbitrary process structures to allow cycles in processes and safepoints to allow partial compensation of processes. We present a formal specification of the transaction model and transaction management algorithms in set and graph theory, providing clear, unambiguous transaction semantics. The specification is straightforwardly mapped to a modular architecture, the implementation of which is first applied in a testing environment, then in the prototype of a commercial workflow management system. The modular nature of the resulting system allows easy distribution using middleware technology. The path from abstract semantics specification to concrete, real-world implementation of a workflow transaction mechanism is thus covered in a complete and coherent fashion. As such, this paper provides a complete framework for the application of well-founded transactional workflows. Received: 16 November 1999 / Accepted 29 August 2001 Published online: 6 November 2001     

Analysis of navigation behaviour in web sites integrating multiple information systems

Abstract. The analysis of web usage has mostly focused on sites composed of conventional static pages. However, huge amounts of information available in the web come from databases or other data collections and are presented to the users in the form of dynamically generated pages. The query interfaces of such sites allow the specification of many search criteria. Their generated results support navigation to pages of results combining cross-linked data from many sources. For the analysis of visitor navigation behaviour in such web sites, we propose the web usage miner (WUM), which discovers navigation patterns subject to advanced statistical and structural constraints. Since our objective is the discovery of interesting navigation patterns, we do not focus on accesses to individual pages. Instead, we construct conceptual hierarchies that reflect the query capabilities used in the production of those pages. Our experiments with a real web site that integrates data from multiple databases, the German SchulWeb, demonstrate the appropriateness of WUM in discovering navigation patterns and show how those discoveries can help in assessing and improving the quality of the site. Received June 21, 1999 / Accepted December 24, 1999     

A graphical user interface for Boolean query specification

Online information repositories commonly provide keyword search facilities through textual query languages based on Boolean logic. However, there is evidence to suggest that the syntactic demands of such languages can lead to user errors and adversely affect the time that it takes users to form queries. Users also face difficulties because of the conflict in semantics between AND and OR when used in Boolean logic and English language. Analysis of usage logs for the New Zealand Digital Library (NZDL) show that few Boolean queries contain more than three terms, use of the intersection operator dominates and that query refinement is common. We suggest that graphical query languages, in particular Venn-like diagrams, can alleviate the problems that users experience when forming Boolean expressions with textual languages. A study of the utility of Venn diagrams for query specification indicates that with little or no training users can interpret and form Venn-like diagrams in a consistent manner which accurately correspond to Boolean expressions. We describe VQuery, a Venn-diagram based user interface to the New Zealand Digital Library (NZDL). In a study which compared VQuery with a standard textual Boolean interface, users took significantly longer to form queries and produced more erroneous queries when using VQuery. We discuss the implications of these results and suggest directions for future work. Received: 15 December 1997 / Revised: June 1999     

Consistent specification of interface suites in UML

The paper motivates and describes a model oriented approach for consistent specification of interface suites in UML. An interface suite is a coherent collection of interfaces defining interactions that transcend component boundaries. The specification of interface suites contains diagrammatic views and documentation, but it is extended with templates for structured specifications deriving from the ISpec approach. To guarantee that the specification views, documentation and templates are consistent, a specification model has been constructed. The model contains both structural and behavioural information, represented in the form of sequences of carefully designed tuples. The model provides the underlying structure for the tool supporting the design process. The tool directs the designer to specify all elements of the model in a consistent way. The specification is collected both by customized specification templates and by diagrams. The documentation and the diagram elements – both derived from the template information – are automatically generated. This prevents errors and provides specification consistency. Initial submission: 15 February 2002 / Revised submission: 20 September 2002 Published online: 2 December 2002 RID="*" ID="*"Supported by PROGRESS grant EES.5141 and ITEA DESS grant IT990211.     

Answering queries using views: A survey

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously defined materialized views over the database, rather than accessing the database relations. The problem has recently received significant attention because of its relevance to a wide variety of data management problems. In query optimization, finding a rewriting of a query using a set of materialized views can yield a more efficient query execution plan. To support the separation of the logical and physical views of data, a storage schema can be described using views over the logical schema. As a result, finding a query execution plan that accesses the storage amounts to solving the problem of answering queries using views. Finally, the problem arises in data integration systems, where data sources can be described as precomputed views over a mediated schema. This article surveys the state of the art on the problem of answering queries using views, and synthesizes the disparate works into a coherent framework. We describe the different applications of the problem, the algorithms proposed to solve it and the relevant theoretical results. Received: 1 August 1999 / Accepted: 23 March 2001 Published online: 6 September 2001     

Algebraic query optimisation for database programming languages

A major challenge still facing the designers and implementors of database programming languages (DBPLs) is that of query optimisation. We investigate algebraic query optimisation techniques for DBPLs in the context of a purely declarative functional language that supports sets as first-class objects. Since the language is computationally complete issues such as non-termination of expressions and construction of infinite data structures can be investigated, whilst its declarative nature allows the issue of side effects to be avoided and a richer set of equivalences to be developed. The language has a well-defined semantics which permits us to reason formally about the properties of expressions, such as their equivalence with other expressions and their termination. The support of a set bulk data type enables much prior work on the optimisation of relational languages to be utilised. In the paper we first give the syntax of our archetypal DBPL and briefly discuss its semantics. We then define a small but powerful algebra of operators over the set data type, provide some key equivalences for expressions in these operators, and list transformation principles for optimising expressions. Along the way, we identify some caveats to well-known equivalences for non-deductive database languages. We next extend our language with two higher level constructs commonly found in functional DBPLs: set comprehensions and functions with known inverses. Some key equivalences for these constructs are provided, as are transformation principles for expressions in them. Finally, we investigate extending our equivalences for the set operators to the analogous operators over bags. Although developed and formally proved in the context of a functional language, our findings are directly applicable to other DBPLs of similar expressiveness. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

The impact of Web self-efficacy,age, and Web experience on bookmark manipulation

This paper presents a study that examines the impact of age, Web experience, and Web self-efficacy across the adult life span on users’ bookmark management behaviors. It was hypothesized that Web self-efficacy would mediate the effect of age and Web experience on bookmark manipulation. Six hundred users, sampled from the Project 2000 and 7th WWW User survey data, were used to examine this model. Using structural equation modeling techniques, it was found that the effect of age on bookmark manipulation was fully mediated by Web self-efficacy. However, the effect of Web experience was not fully mitigated by Web self-efficacy. Published online: 22 May 2002     

Semantic caching of Web queries

Abstract. In meta-searchers accessing distributed Web-based information repositories, performance is a major issue. Efficient query processing requires an appropriate caching mechanism. Unfortunately, standard page-based as well as tuple-based caching mechanisms designed for conventional databases are not efficient on the Web, where keyword-based querying is often the only way to retrieve data. In this work, we study the problem of semantic caching of Web queries and develop a caching mechanism for conjunctive Web queries based on signature files. Our algorithms cope with both relations of semantic containment and intersection between a query and the corresponding cache items. We also develop the cache replacement strategy to treat situations when cached items differ in size and contribution when providing partial query answers. We report results of experiments and show how the caching mechanism is realized in the Knowledge Broker system. Received June 15, 1999 / Accepted December 24, 1999     

Personalized, interactive news on the Web

We present Krakatoa Chronicle, an interactive, personalized newspaper on the World Wide Web implemented as a Java applet. The newspaper is similar in appearance to newspapers in the real world, with a multi-column layout and justified text. At the same time, it provides various interaction techniques for browsing the content of articles, giving relevance feedback, and dynamically changing layout. As users interact with the system, individual ‘user profiles’ are built up at the webserver site. These are used to tailor the newspaper's content and layout to each user's declared and inferred preferences. The system allows for a balancing of personal and community interests, allowing the user to navigate through a space of newspapers corresponding to a range of viewpoints.     

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     

Locating and accessing data repositories with WebSemantics

Many collections of scientific data in particular disciplines are available today on the World Wide Web. Most of these data sources are compliant with some standard for interoperable access. In addition, sources may support a common semantics, i.e., a shared meaning for the data types and their domains. However, sharing data among a global community of users is still difficult because of the following reasons: (i) data providers need a mechanism for describing and publishing available sources of data; (ii) data administrators need a mechanism for discovering the location of published sources and obtaining metadata from these sources; and (iii) users need a mechanism for browsing and selecting sources. This paper describes a system, WebSemantics, that accomplishes the above tasks. We describe an architecture for the publication and discovery of scientific data sources, which is an extension of the World Wide Web architecture and protocols. We support catalogs containing metadata about data sources for some application domain. We define a language for discovering sources and querying their metadata. We then describe the WebSemantics prototype. Edited by H. Korth. Received: 15 July 1999 / Accepted: 13 September 2000 Published online: 16 April 2002     

Distributed accessibility control points help deliver a directly accessible Web

This paper describes a set of interfaces and mechanisms to enhance access to the World Wide Web for persons with sensory, cognitive, or motor limitations. Paradoxically, although complex Web architectures are often accused of impeding accessibility, their layers expand the range of points where interventions can be staged to improve it. This paper identifies some of these access control points and evaluates the particular strengths and weaknesses of each. In particular, it describes an approach to enhance access that is distributed across multiple control points and implemented as an aggregation of services. Published online: 6 November 2002     

Intelligent non-visual navigation of complex HTML structures

This paper provides an overview of a project aimed at using knowledge-based technology to improve accessibility of the Web for visually impaired users. The focus is on the multi-dimensional components of Web pages (tables and frames); our cognitive studies demonstrate that spatial information is essential in comprehending tabular data, and this aspect has been largely overlooked in the existing literature. Our approach addresses these issues by using explicit representations of the navigational semantics of the documents and using a domain-specific language to query the semantic representation and derive navigation strategies. Navigational knowledge is explicitly generated and associated to the tabular and multi-dimensional HTML structures of documents. This semantic representation provides to the blind user an abstract representation of the layout of the document; the user is then allowed to issue commands from the domain-specific language to access and traverse the document according to its abstract layout. Published online: 6 November 2002     

RSVP Browser: Web Browsing on Small Screen Devices

In this paper, we illustrate the use of space-time trade-offs for information presentation on small screens. We propose the use of Rapid Serial Visual Presentation (RSVP) to provide a rich set of navigational information for Web browsing. The principle of RSVP browsing is applied to the development of a Web browser for small screen devices, the RSVP browser. The results of an experiment in which Web browsing with the RSVP browser is compared with that of a typical WAP browser suggests that RSVP browsing may indeed offer alternative to other forms of Web browsing on small screen devices.     

基于宣告式网络的网络溯源系统的设计与实现

网络的举证分析、错误诊断在网络管理和安全方面正发挥着越来越重要的作用。这就要求网络管理系统具有网络溯源的功能。网络溯源可以用于跟踪信息在网络上流传的轨迹,确定信息数据来源。提出了一个网络溯源系统(NPS)框架的设计与实现,该框架可以支持在大规模的分布式环境中获得网络溯源,采用了新近提出的宣告式网络技术来有效地维护和查询分布式网络溯源。该框架采用基于引用的方式来传递溯源信息,采用有向无环图来表示溯源信息,在分布式网络中实现了高效的网络溯源。在ns-3构建的模拟网络中进行了仿真实验,实验结果表明该网络溯源系统框架可以有效地支持一个大规模分布式网络的溯源计算,与传统方法相比显著地减少了带宽的开销。