The complexity and diversity of government regulations make understanding the regulations a non-trivial task. One of the issues is the existence of multiple sources of regulations and interpretive guides; the latter are often independent of governing bodies. This work aims to develop an information infrastructure for legal information retrieval with applications to electronic-rulemaking. The pilot study focuses on accessibility regulations from the US Federal government, private organizations and European agencies. A shallow parser is developed to consolidate different regulations into a unified XML format, which is well suited for handling semi-structured data such as legal documents. Handcrafted rules and a text mining tool are developed to extract the important features, such as concepts, measurements, effective dates and so on, and to incorporate them into the corpus.To compare and locate related provisions from different regulatory documents, we employ Information Retrieval techniques to combine generic features with domain knowledge. Structural information from regulations, such as the hierarchical organization of provisions and heavy referencing among provisions, are used to help improve the relatedness analysis. Results are obtained to illustrate the use of regulatory structure and domain knowledge in provision comparisons. Application to an e-rulemaking scenario for a rights-of-way drafted regulation is shown to demonstrate extended capabilities of the prototype system.

The complexity and diversity of government regulations make understanding the regulations a non-trivial task. One of the issues is the existence of multiple sources of regulations and interpretive guides. In this work, we propose an information infrastructure for regulation analysis, which includes a document repository and tools for compliance assistance and similarity analysis. A regulatory repository is developed based on an XML format, and important features, such as concepts and measurements, are extracted using handcrafted rules and a text mining tool. Our framework provides compliance assistance using a reasoning tool based on First Order Predicate Calculus logic, where users are alerted of detected conflicts or otherwise compliance with the regulation. A relatedness analysis is performed by comparing the extracted features as well as structural and referential information from regulations. Examples of an electronic-rulemaking scenario and a compliance checking procedure are shown to demonstrate current capabilities of the prototype system.

This paper presents a loosely coupled service-composition paradigm. This paradigm employs a distributed data flow that differs markedly from centralized information flow adopted by current service integration frameworks, such as CORBA, J2EE and SOAP. Distributed data flows support direct data transmission to avoid many performance bottlenecks of centralized processing. In addition, active mediation is used in applications employing multiple web services that are not fully compatible in terms of data formats and contents. Active mediation increases the applicability of the services, reduces data communication among the services, and enables the application to control complex computations. The benefits of distributed data flow and active mediation are illustrated with various applications, such as dynamic type conversion, result extraction, and engineering application. It is shown that active mediation, combining with distributed data flows, can greatly improve the performance of an application utilizing multiple web services.

Government regulations are semi-structured text documents that are often voluminous, heavily cross-referenced between provisions and even ambiguous. Multiple sources of regulations lead to difficulties in both understanding and complying with all applicable codes. In this work, we propose a framework for regulation management and similarity analysis. An online repository for legal documents is created with the help of text mining tool, and users can access regulatory documents either through the natural hierarchy of provisions or from a taxonomy generated by knowledge engineers based on concepts. Our similarity analysis core identifies relevant provisions and brings them to the user's attention, and this is performed by utilizing both the hierarchical and referential structures of regulations to provide a better comparison between provisions. Preliminary results show that our system reveals hidden similarities that are not apparent between provisions based on node content comparisons.

OntoWebber is a system for managing data on the Web with formally encoded semantics. It aims at solving the problems current technologies are confronted with, namely, the reusability of software components, flexibility in personalization, and ease of maintenance for data intensive Web sites. Based on a domain ontology and a site modeling ontology, site views on the underlying data can be constructed as site models. Instantiation of these models will create a browsable Web site, and manipulation of the site models helps to reduce the high effort of personalizing and maintaining the Web site. In this paper we present the architecture and demonstrate the major components of the system.

We present a clustering and indexing paradigm (called Clindex) for high-dimensional search spaces. The scheme is designed for approximate similarity searches, where one would like to find many of the data points near a target point, but where one can tolerate missing a few near points. For such searches, our scheme can find near points with high recall in very few IOs and perform significantly better than other approaches. Our scheme is based on finding clusters and, then, building a simple but efficient index for them. We analyze the trade-offs involved in clustering and building such an index structure, and present extensive experimental results.

Resolving heterogeneity among the various biological information systems is a crucial problem if we wish to gain value from the many distributed resources available to us. For example, information from multiple protein databases (e.g., Swiss-Prot and PDB) might need to be composed to answer queries posed by end-users. Problems of heterogeneity in hardware, operating systems, interfaces and data structures have been widely addressed, but issues of diverse semantics have been handled mainly in an ad-hoc fashion. This paper highlights the ONION (ONtology compositION) system that enables semantic interoperation among various information sources by articulating the ontologies associated with them. An articulation focuses on the semantically relevant intersection of information resources. Although the generation of articulations (semantic correspondences between the ontologies) cannot be fully automated, we take a semi-automatic approach. ONION uses heuristic algorithms for the automatic generation of suggested articulations. This paper outlines an algebra for ontology composition based on their articulations. We show the properties of the algebraic operators and how they depend upon the articulation functions that generate the articulations. Query optimization is enabled based on the properties of the algebraic operators.

The database and document worlds have traditionally had different approaches to security. Databases provide access controls on structured data, while document security interrogates the outgoing information, based on document markings and actual contents. For the emerging world in which many documents are generated from structured data (and vice versa), the separation can cause failure, implementation-dependence, inconsistency, and wasted effort. After comparing approaches and mechanisms in the two areas, we identify issues in security administration and implementation in military and medical applications. We then present elements of a unifying model.

Unsupervised segmentation of images with low depth of field (DOF) is highly useful in various applications. This paper describes a novel multiresolution image segmentation algorithm for low DOF images. The algorithm is designed to separate a sharply focused object-of-interest from other foreground or background objects. The algorithm is fully automatic in that all parameters are image independent. A multi-scale approach based on high frequency wavelet coefficients and their statistics is used to perform context-dependent classification of individual blocks of the image. Unlike other edge-based approaches, our algorithm does not rely on the process of connecting object boundaries. The algorithm has achieved high accuracy when tested on more than 100 low DOF images, many with inhomogeneous foreground or background distractions. Compared with he state of the art algorithms, this new algorithm provides better accuracy at higher speed.

We present here SIMPLIcity (semantics-sensitive integrated matching for picture libraries), an image retrieval system, which uses semantics classification methods, a wavelet-based approach for feature extraction, and integrated region matching based upon image segmentation. An image is represented by a set of regions, roughly corresponding to objects, which are characterized by color, texture, shape, and location. The system classifies images into semantic categories. Potentially, the categorization enhances retrieval by permitting semantically-adaptive searching methods and narrowing down the searching range in a database. A measure for the overall similarity between images is developed using a region-matching scheme that integrates properties of all the regions in the images. The application of SIMPLIcity to several databases has demonstrated that our system performs significantly better and faster than existing ones. The system is fairly robust to image alterations.

It is sometimes necessary to collaborate with individuals and organizations which should not be fully trusted. Collaborators must be authorized to access information systems some of the data in which, typically, should be withheld. New collaborations require dynamic alterations to security provisions. Solutions based on extending access control to deal with collaborations are either awkward and costly, or unreliable. An alternative approach, complementing basic access control, is results filtering. Content filtering is also costly, but provides a number of benefits not obtainable with access control alone. The most important is that the complexity of setting up and maintaining isolating information cells for every combination of access rights is avoided. New classes of collaborators can be added without requiring a reorganization of the entire information structure. There is no overhead for internal use. Since content of documents, not their labels, is checked, misfiling will not cause inappropriate release. The approach used in the TIHI/SAW projects at Stanford uses simple rules to drive filtering primitives. The filters run on a modest, but dedicated computer managed by a security officer. The rules implement the security policy and balance manual effort and complexity. The functional allocation of responsibilities is good. Result filtering can also be used to implement pure intrusion detection, since it is invisible. The intruder can be given an impression of success, while becoming a target for monitoring or cover stories.

The classification of general-purpose photographs into textured and non-textured images is critical for developing accurate content-based image retrieval systems for large-scale image databases. With the accurate detection of textured images, we may retrieve images based on features tailored for the corresponding image type. In this paper, we present an algorithm to classify a photographic image as textured or non-textured using region segmentation and statistical testing. The application of the system to a database of about 60,000 general-purpose images shows much improved accuracy in retrieval.

Content-based image retrieval using region segmentation has been an active research area. We present IRM (Integrated Region Matching), a novel similarity measure for region-based image similarity comparison. The targeted image retrieval systems represent an image by a set of regions, roughly corresponding to objects, which are characterized by features reflecting color, texture, shape, and location properties. The IRM measure for evaluating overall similarity between images incorporates properties of all the regions in the images by a region-matching scheme. Compared with retrieval based on individual regions, the overall similarity approach reduces the influence of inaccurate segmentation, helps to clarify the semantics of a particular region, and enables a simple querying interface for region-based image retrieval systems. The IRM has been implemented as a part of our experimental SIMPLIcity image retrieval system. The application to a database of about 200,000 general-purpose images shows exceptional robustness to image alterations such as intensity variation, sharpness variation, color distortions, shape distortions, cropping, shifting, and rotation. Compared with several existing systems, our system in general achieves more accurate retrieval at higher speed.

Requirements for continuing progress in Information Systems usability are surveyed and analyzed.

As computers and the Internet become more and more available to families, access of objectionable graphics by children is increasingly a problem that many parents are concerned about. This paper describes WIPE™ (Wavelet Image Pornography Elimination), a system capable of classifying an image as objectionable or benign. The algorithm uses a combination of an icon filter, a graph–photo detector, a color histogram filter, a texture filter and a wavelet-based shape matching algorithm to provide robust screening of on-line objectionable images. Semantically-meaningful feature vector matching is carried out so that comparisons between a given on-line image and images in a pre-marked training data set can be performed efficiently and effectively. The system is practical for real-world applications, processing queries at a speed of less than 2 s each, including the time taken to compute the feature vector for the query, on a Pentium Pro PC. Besides its exceptional speed, it has demonstrated 96% sensitivity over a test set of 1076 digital photographs found on objectionable news groups. It wrongly classified 9% of a set of 10,809 benign photographs obtained from various sources. The specificity in real-world applications is expected to be much higher because benign on-line graphs can be filtered out with our graph–photo detector with 100% sensitivity and nearly 100% specificity, and surrounding text can be used to assist the classification process.

In this work we address the problem of dealing with data inconsistencies while integrating data sets derived from multiple autonomous relational databases. The fundamental assumption in the classical relational model is that data is consistent and hence no support is provided for dealing with inconsistent data. Due to this limitation of the classical relational model, the semantics for detecting, representing, and manipulating inconsistent data have to be explicitly encoded in the applications by the application developer. In this paper, we propose the flexible relational model, which extends the classical relational model by providing support for inconsistent data. We present a flexible relation algebra, which provides semantics for database operations in the presence of potentially inconsistent data. Finally, we discuss issues raised for query optimization when the data may be inconsistent.>

One of the approaches for integrating object-oriented programs with databases is to instantiate objects from relational databases by evaluating view queries. In that approach, it is often necessary to evaluate some joins of the query by left outer joins to prevent information loss caused by the tuples discarded by inner joins. It is also necessary to filter some relations with selection conditions to prevent the retrieval of unwanted nulls. The system should automatically prescribe joins as inner or left outer joins and generate the filters, rather than letting them be specified manually for every view definition. We develop such a mechanism in this paper. We first develop a rigorous system model to facilitate the mapping between an object-oriented model and the relational model. The system model provides a well-defined context for developing a simple mechanism. The mechanism requires only one piece of information from users: null options on an object attribute. The semantics of these options are mapped to non-null constraints on the query result. Then the system prescribes joins and generates filters accordingly. We also address reducing the number of left outer joins and the filters so that the query can be processed more efficiently.>

This paper describes and classifies methods to transform data to information in a three-layer, mediated architecture. The layers can be characterized from the top down as information-consuming applications, mediators which perform intelligent integration of information (I3), and data, knowledge and simulation resources.

The execution of logic queries in a distributed database environment is studied. Conventional optimization strategies, such as the early evaluation of selection conditions and the clustering of processing to manipulate and exchange large sets of tuples, are redefined in view of the additional difficulties due to logic queries, in particular to recursive rules. In order to allow efficient processing of these logic queries, several program transformation techniques that attempt to minimize distribution costs based on the idea of semijoins and generalized semijoins in conventional databases are presented. Although local computation of semijoins is not possible for the general case, classes of programs are indicated for which these transformations succeed in producing set-oriented computation. Processes evaluating the recursive program in a distributed network are described, and an efficient method for testing the termination of the computation is developed. The approach is compared with sequential as well as dataflow-oriented evaluation.>

In general, writing a relational query involving many join predicates is cumbersome and prone to errors. One approach to resolving this problem is the implicit join method. This method derives the unspecified join predicates of an incompletely specified query from the semantic dependency-a set of the pairs of semantically dependent attributes-in the database schema. Although the implicit join method has some advantages over the universal relation approach, it frequently derives a complete query differently from what a user would do, and generates redundant subqueries. It is shown that using the structural model removes the problem of redundancy by making the semantic observation of the database schema possible, and provides a complete query that many users would prefer to that of the original implicit join method.>

The view-object model provides a formal basis for representing and manipulating object-based views on relational databases.

Database updates are small and incremental compared to database contents. It is therefore desirable that recomputations of active relational expressions-such as views, derived data, integrity constraints, active queries, and monitors-can also be performed incrementally. An efficient algorithm for the incremental recomputation of active relational expressions based on finite differencing techniques is presented. Database updates are modeled as incremental changes to database relations, and the algorithm derives, by update propagation, the minimal incremental relational expressions that need recomputation. The algorithm has applications in the maintenance of materialized views and derived data, the checking of integrity constraints, and the evaluation of active queries and monitors.>

Querying databases to obtain information requires the user's knowledge of query language and underlying data. However, because the knowledge in human long-term memory is imprecise, incomplete, and often incorrect, user queries are subject to various types of failure. These may include spelling mistakes, the violation of the syntax and semantics of a query language, and the misconception of the entities and relationships in a database.

The growing complexity of VLSI designs has led to a partitioning of design responsibilities among different engineers, with the result that engineers work in parallel on different aspects of the design. With this division of responsibilities comes the need for automatic means of coordinating changes made by different engineers, and automatic means of administrating design policies laid down by management. In this paper we show how an information-rich design environment, incorporating (1) detailed knowledge of the design, (2) explicit representation of management's policies, and (3) special software units called change coordinators, can be used to automate the functions of change coordination and policy administration.

We study the properties of the magic semi-join, a new algebraic operator. In essence, a magic semi-join is the composition of a semi-join and a transitive closure. We present a theory for magic semi-joins that mirrors the theory for semi-joins; in particular, we define equivalence transformations of algebraic formulas using magic semi-joins, and we introduce the notion of full reducer program in this framework. The application of magic semi-joins is in the efficient evaluation of recursive DATALOG queries in centralized and in distributed databases.

In designing the interface between a relational database and a Prolog interpreter, efficiency is a major issue. The authors present a method for loading into the memory-resident database of Prolog facts permanently stored in secondary storage. The rationale of the method is to save access to the database by never repeating the same query and by storing in main memory, in a compact and efficient way, information about the past interaction with the database. The authors discuss how to reduce subsumption rests required by the method to pattern matching in many relevant cases. They also describe a simulator of the method, which validates their approach, and they discuss the results of the simulation.>

A new relationship type is proposed which permits describing the issues raised when information is distributed over autonomous workstations. Such federated environments are becoming the dominant form of distributed systems. Fully synchronous update of replicated data is not feasible in such systems. The proposed identity connection identifies data which should eventually match, but which can be in differing states for some time intervals. The concept permits modeling of the systems which are now becoming common in data processing.

This paper surveys methodological approaches for distributed database design. The design of distribution can be performed top-down or bottom-up; the first approach is typical of a distributed database developed from scratch, while the second approach is typical of the development of a multi-database as the aggregation of existing databases. We review the design problems and methodologies along both directions, and we describe DATAID-D, a top-down methodology for distribution design. We indicate how the methodology is part of a global approach to database design; how to collect the requirements about the distribution of data and applications; and how to progressively build the distribution of a schema. Our approach is exemplified through one case study.

Purpose. This paper defines a layered functional architecture that is useful for describing interfaces (data or parameter exchanges) between Ada and Data Management Systems (DMS). It uses this architecture in discussing potential approaches to implementating standard interfaces between Ada and both relational and CODASYL DMSs.

The work described here addresses two problems: information overload of database users, and knowledge acquisition for use in Al systems. We have implemented programs that use artificial intelligence techniques to prepare high-level, intelligent summaries of databases, and that use empirical databases in turn, in combination with statistical and Al methods, to generate new domain knowledge base. Both programs are examples of the aquisition of knowledge from data: the Summarization Module fuses large amounts of data succinctly, the Discovery Module extracts new knowledge present implicitly in data. We describe the implementation of our programs and outline planned extensions which combine both approaches. This work is distinguished from current knowledge engineering approaches in that we prime the system with expert knowledge, and then use factual data to learn more about the domain.

In a distributed database system the partitioning and allocation of the database over the processor nodes of the network can be a critical aspect of the database design effort. In this paper we develop and evaluate algorithms that perform this task in a computationally feasible manner. The network we consider is characterized by a relatively high communication bandwidth, considering the processing and input output capacities in its processors. Such a balance is typical if the processors are connected via busses or local networks. The common constraint that transactions have a specific root node no longer exists, so that there are more distribution choices. However, a poor distribution leads to less efficient computation, higher costs, and higher loads in the nodes or in the communication network so that the system may not be able to handle the required set of transactions. Our approach is to first split the database into fragments which constitute appropriate units for allocation. The fragments to be allocated are selected based on maximal benefit criteria using a greedy heuristic. The assignment to processor nodes uses a first-fit algorithm. The complete algorithm, called GFF, is stated in a procedural form. The complexity of the problem and of its candidate solutions are analyzed and several interesting relationships are proven. Alternate benefit metrics are considered, since the execution cost of the allocation procedure varies by orders of magnitude with the alternatives of benefit evaluation. A mixed benefit evaluation strategy is eventually proposed. A model for evaluation is presented. Two of the strategies are experimentally evaluated, and the reported results support the discussion. The approach should be suitable for other cases where resources have to be allocated subject to resource constraints.

Since cooperation is an essential aspect of human conversation, it is a necessary feature in a natural language interface. Previous work has shown that it is possible to incorporate principles of cooperative behaviour into a system allowing natural language access to a database. It is shown here that some of these principles can also be applied fruitfully in a formal language environment. Specifically, when a query retrieves an empty result set, it is possible, by analyzing the question and running related queries against the database, to give a useful explanation of the zero result. A precise specification of the information that should be presented to the user is described for queries consisting of boolean combinations of predicates of a single variable. Such cooperative responses to boolean queries have been implemented on the large bibliographic database of the Research Libraries Group. The size of the database has motivated a careful optimization of the algorithm, which is discussed.

A theoretical approach to the optimal design of a large multifile physical database is presented. The design algorithm is based on the theory that, given a set of join methods that satisfy a certain property called separability, the problem of optimal assignment of access structures to the whole database can be reduced to the subproblem of optimizing individual relations independently of one another. Coupling factors are defined to represent all the interactions among the relations. This approach not only reduces the complexity of the problem significantly, but also provides a better understanding of underlying mechanisms.

This paper addresses the vertical partitioning of a set of logical records or a relation into fragments. The rationale behind vertical partitioning is to produce fragments, groups of attribute columns, that “closely match” the requirements of transactions. Vertical partitioning is applied in three contexts: a database stored on devices of a single type, a database stored in different memory levels, and a distributed database. In a two-level memory hierarchy, most transactions should be processed using the fragments in primary memory. In distributed databases, fragment allocation should maximize the amount of local transaction processing. Fragments may be nonoverlapping or overlapping. A two-phase approach for the determination of fragments is proposed; in the first phase, the design is driven by empirical objective functions which do not require specific cost information. The second phase performs cost optimization by incorporating the knowledge of a specific application environment. The algorithms presented in this paper have been implemented, and examples of their actual use are shown.

The optimal distribution of a database schema over a number of sites in a distributed network is considered. The database is modeled in terms of objects (relations or record sets) and links (predefined joins or CODASYL sets). The design is driven by user-supplied information about data distribution. The inputs required by the optimization model are: 1) cardinality and size information about objects and links, 2) a set of candidate horizontal partitions of relations into fragments and the allocations of the fragments, and 3) the specification of all important transactions, their frequencies, and their sites of origin.

This paper describes recent and planned work at Stanford University in applying database technology to the problems of VLSI design. In particular, it addresses the issue of communication within a design's different representations and hierarchical levels in a multiple designer environment. We demonstrate the heretofore questioned utility of using commercial database systems, at least while developing a versatile, flexible, and generally efficient model and its associated communication paths. Completed work and results from initial work using DEC DBMS-20 is presented, including macroexpansion within the database, and signaling of changes to higher structural levels. Considerable discussion regarding overall philosophy for continued work is also included.

A read-only transaction or query is a transaction which does not modify any data. Read-only transactions could be processed with general transaction processing algorithms, but in many cases it is more efficient to process read-only transactions with special algorithms which take advantage of the knowledge that the transaction only reads. This paper defines the various consistency and currency requirements that read-only transactions may have. The processing of the different classes of read-only transactions in a distributed database is discussed. The concept of R insularity is introduced to characterize both the read-only and update algorithms. Several simple update and read-only transaction processing algorithms are presented to illustrate how the query requirements and the update algorithms affect the read-only transaction processing algorithms.

A new resiliency scheme for a distributed database system with replicated data is presented. One salient feature of the scheme is that it does not employ a log subsystem; hence, it can be used for a highly reliable system that must tolerate a total crash of a site. In addition, the scheme supports system partitioning without any consistency problem. The new scheme is based on a precise treatment of logical data; in particular, a precise definition of resilient system operation is given in terms of logical data.

A file access system, flash, for use in building database systems is described. It supports access from several languages, including pascal, fortran, and interlisp. Flash provides record level access to a file with multiple indexes using symbolic keys. It is portable and written in Pascal with support routines in dec System 20 macro. The file access system is designed to run on computers of various sizes and capabilities, including micros. Concurrent and simultaneous access by several users is supported given that the operating systems provides multiprogramming. Flash is designed to be highly reliable. It assumes the existence of underlying operating system file services that read or write named files directly. Transfer to files occurs in units which are efficient, typically a block.

Graphics and imaging are important in scientific, academic and industrial environments. In the past graphics systems have been used with large computers and were only available to a minority of users. The relatively small and specialized use of graphics has inhibited sharing of software and prevented standardization necessary for widespread use. Dense semiconductor memory has recently become easily available in large quantities and makes high resolution graphics and imaging systems feasible. The concepts leading to the design of the present system come from the need to provide a large number of graphic and imaging functions, in a compact form, to a commonly used microprocessor bus. Three fundamental functions are implemented: a video frame digitizer, an image memory, and an output video generator. Video images can be digitized in one frame time with a precision of 1, 2 or 4 bits per pixel. The video generator can display the images in gray levels or in color. The software selectable system parameters include a variety of image formats, video output controls, digitization commands, addressing modes, vertical image offset, and lightpen controls. A novel contouring digitization mode is useful to reduce images obtained in gray scale to outline form. Such real-time preprocessing reduces memory and bandwidth requirements. Photographic illustrations demonstrate various operating modes.

One approach to the design of a logical model for an integrated database requires each potential user or application to specify its view as a data model. An integration phase follows, where these user data models are integrated into a global database model. We address the problem of view integration when user data models are expressed using the structural model [Wi77, WE79].The structural model is built from relations in Boyce-Codd normal form [Co74]. A basic set of integrity assertions is implicit in the model. The integrity assertions are defined by classification of relations into types, and are represented by connections between relations. We will show how to integrate different representations of two related real-world entity classes.

The design considerations leading to the decision to equip a large time-sharing system at Carnegie–Mellon University with a very large addressable—but slow—core memory, instead of using the standard disk or drum swapping devices, are illustrated.