This paper presents the goal, accomplishments and research issues of an NSF project. The project aims to develop a distributed event-triggered knowledge sharing network (ETKnet) for government organizations to share, not only data and application operations, but also knowledge embedded in organizational and inter-organizational policies, regulations, data and security constraints as well as collaborative processes and operating procedures. A unified knowledge and process specification language has been developed to formally specify multi-faceted human and organizational knowledge in terms of three types of knowledge rules and rule structures. A user-friendly interface is provided for collaborating organizations to define events of interest as well as application operations, knowledge rules, rule structures and triggers. Events are published in a global registry for browsing, querying, event subscription and notification. Rules and rule structures are automatically translated into Web services for distributed processing in ETKnet. Event data are dots that can be connected dynamically across organizational boundaries through the interoperation of knowledge rules, processes and application operations.

Much effort is being made by the IT industry towards the establishment of a Web services infrastructure and the refinement of its component technologies to enable the sharing of heterogeneous application resources. Traditional roles of the service provider, service requestor and service broker and their interactions are now being improved upon to enable more effective services. The implementation of the Web service broker is currently limited to being an interface to the service repository for service registration, browsing and/or programmatic access. In this work, we have extended the functionality of the Web services broker to include constraint specification and processing, which enables the broker to find a good match between a service provider's capabilities and a service requestor's requirements. This paper presents the extension made to the Web Services Description Language to include constraint specifications in service descriptions and requests, the architecture of a constraint-based broker, the constraint matching technique, some implementation details, and preliminary evaluation results.

Grid computing provides the basic software infrastructure for integrating geographically distributed resources and services through standardized grid services. One of the key challenges to enable the broader use of grid services beyond the domain of scientific computing is the ability to perform complex tasks that require the modeling and coordination of the enactment of a number of distributed grid services. Workflow technology is a good candidate for supporting grid service flow. However, traditional workflow is static, thus unable to exploit the dynamic information available in the grid and respond to the dynamic nature of the grid. In this paper, we present an adaptive framework that provides adaptive management of grid service flows. The framework is based on an adaptive grid service flow model and is supported by an event-trigger-rule (ETR) technology that will be used to trigger rules in a distributed fashion to adapt a grid service flow to the dynamic grid environment and the changing requirements of a grid application.

MOTIVATION: In the post-genomic era, biologists interested in systems biology often need to import data from public databases and construct their own system-specific or subject-oriented databases to support their complex analysis and knowledge discovery. To facilitate the analysis and data processing, customized and centralized databases are often created by extracting and integrating heterogeneous data retrieved from public databases. A generalized methodology for accessing, extracting, transforming and integrating the heterogeneous data is needed. RESULTS: This paper presents a new data integration approach named JXP4BIGI (Java XML Page for Biological Information Gathering and Integration). The approach provides a system-independent framework, which generalizes and streamlines the steps of accessing, extracting, transforming and integrating the data retrieved from heterogeneous data sources to build a customized data warehouse. It allows the data integrator of a biological database to define the desired bio-entities in XML templates (or Java XML pages), and use embedded extended SQL statements to extract structured, semi-structured and unstructured data from public databases. By running the templates in the JXP4BIGI framework and using a number of generalized wrappers, the required data from public databases can be efficiently extracted and integrated to construct the bio-entities in the XML format without having to hard-code the extraction logics for different data sources. The constructed XML bio-entities can then be imported into either a relational database system or a native XML database system to build a biological data warehouse. AVAILABILITY: JXP4BIGI has been integrated and tested in conjunction with the IKBAR system (http://www.ikbar.org/) in two integration efforts to collect and integrate data for about 200 human genes related to cell death from HUGO, Ensembl, and SWISS-PROT (Bairoch and Apweiler, 2000), and about 700 Drosophila genes from FlyBase (FlyBase Consortium, 2002). The integrated data has been used in comparative genomic analysis of x-ray induced cell death. Also, as explained later, JXP4BIGI is a middleware and framework to be integrated with biological database applications, and cannot run as a stand-alone software for end users. For demonstration purposes, a demonstration version is accessible at (http://www.ikbar.org/jxp4bigi/demo.html).

The paper presents an information infrastructure for supporting Internet-based scalable e-business enterprises (ISEE). The information infrastructure is formed by a network of ISEE hubs, each of which has a number of replicable e-business servers providing various e-services to individuals and businesses. The servers are the implementations of a number of core technologies developed to facilitate collaborative e-business, including business event and rule management, active distributed objects, constraint satisfaction processing, and cost benefit analysis and selection. Using the e-services provided by these servers, other e-services such as constraint-based brokering, supplier selection, active business process management, and automated negotiation can be developed. Supply chain management is used as an example of collaborative e-business in the descriptions of these technologies and their implementations.

The Internet and distributed object technologies have made it possible for different business enterprises to draw upon the best of their resources for conducting joint business as a virtual e-enterprise (VEE). To enable virtual e-enterprises, the integration of legacy applications and the modeling and enactment of concurrent business processes are necessary. The authors combine the features of the messaging approach and the distributed object approach to system integration. Business Object Documents (BOD) are used for transmitting business operations and data among application systems. Message transmission is supported by two underlying communication infrastructures: CORBA and Java RMI. The separation of messaging from communication infrastructure allows the underlying infrastructure to be changed without impacting application systems. Also, business processes are modeled as sequences or network structures of BOD transmissions. The process models are replicated at all sites and used by an extended information infrastructure to enable distributed, concurrent enactment of processes.

With the emergence of e-business as the next killer application for the Web, automating bargaining-type negotiations between clients (i.e., buyers and sellers) has become increasingly important. With IDEAL (Internet based Dealmaker for e-business), we have developed an architecture and framework, including a negotiation protocol, for automated negotiations among multiple IDEAL servers. The main components of IDEAL are a constraint satisfaction processor (CSP) to evaluate a proposal, an Event-Trigger-Rule (ETR) server for managing and triggering the execution of rules which make up the negotiation strategy (rules can be updated at run-time to deal with the dynamic nature of negotiations), and a cost-benefit analysis to help in the selection of alternative strategies. We have implemented a fully functional prototype system of IDEAL to demonstrate automated negotiations among buyers and suppliers participating in a supply chain.

Two types of parallel processing and optimization algorithms for processing object-oriented databases are the hybrid-hash pointer-based (HHP) algorithms and multi-wavefront (MWF) algorithms. We analyze these two algorithms and develop analytical formulas to capture their main performance features. We study their performance in three application environments, characterized by large databases having many object classes, each of which, respectively, (1) contains a large number of instances; (2) contains a relatively small number of instances; and (3) is of varying size. A horizontal data partitioning strategy is used in (1). A class-per-node assignment strategy is used in (2). In (3), object classes are partitioned horizontally and assigned to a varying number of processors depending on their different sizes. The MWF algorithm has three distinguishing features which contribute to its better performance: (a) a two-phase processing strategy, (b) vertical partitioning of horizontal segments, and (c) dynamic determination of the collision point in MWF propagations, which results in an optimized query execution plan. If these features are adopted by an HHP algorithm, its performance is comparable with that of the MWF algorithm because the difference in CPU time between them is negligible. The computing environment is a network of workstations having a shared-nothing architecture. The schema and some queries selected from the OO7 benchmark are used in the performance analyses and comparisons. The queries are modified slightly in different data environments in order to reflect the features of diverse database applications.

This paper describes an object-oriented temporal association algebra (called TA-algebra) which is intended to serve as a formal foundation for supporting a pattern-based query specification and processing paradigm. Different from the traditional table-and-attribute-based paradigm, the pattern-based paradigm views the intension of an object-oriented temporal database as a network of object classes interconnected by different association types and its extension as a network of associated temporal object instances. Consistent with this view, queries can be specified in terms of patterns of temporal object associations or nonassociations (i.e., linear, tree and network structures of object classes/objects with logical AND and OR branches). TA-algebra provides a set of algebraic operators for processing these patterns and allows the direct and/or indirect associations and/or nonassociations among temporal object instances to be more explicitly represented and maintained during processing than the traditional tabular representation of temporary or final query results. TA-algebra operators are based on time-interval and valid-time semantics and they preserve the closure property. The algebra is capable of operating on heterogeneous as well as homogeneous patterns of object associations. Both homogeneous and heterogeneous patterns are decomposed into a set of primitive temporal pattern instances for uniform treatment. This paper formally defines the TA-algebra operators and their mathematical properties. The applications of these operators in query decomposition and processing are illustrated by examples.

An active object-oriented knowledge base server can provide many desirable features for supporting a wide spectrum of advanced and complex database applications. Knowledge rules, which are used to define a variety of database tasks to be performed automatically on the occurrence of some events, often need much more sophisticated rule-specification and control mechanisms than the traditional priority-based mechanism to specify the control structural relationships and parallel execution properties among rules. The underlying object-oriented (OO) knowledge representation model must provide a means to model the structural relationships among data entities and the control structures among rules in a uniform fashion. The transaction execution model must provide a means to incorporate the execution of structured rules in a transaction framework. Also, a parallel implementation of an active knowledge base server is essential to achieve the needed efficiency in processing nested transactions and rules. In this paper, we present the architecture, implementation, and performance of a parallel active OO knowledge base server, which has the following features. First, the server is developed based on an extended OO knowledge representation model that models rules as objects and their control structural relationships as association types. This is analogous to the modeling of entities as objects and their structural relationships as association types. Thus, entities and rules, and their structures, can be uniformly modeled. Second, the server uses a graph-based transaction model that can naturally incorporate the control semantics of structured rules and guarantee the serializable execution of rules as subtransactions. Thus, the rule-execution model is uniformly integrated with that of transactions. Third, it uses an asynchronous parallel execution model to process the graph-based transactions and structured rules. This server, named OSAM*.KBMS/P, has been implemented on a shared-nothing multiprocessor system (nCUBE2) to verify and evaluate the proposed knowledge-representation model, graph-based transaction model, and asynchronous parallel-execution model.

Article Incorporating association pattern and operation specification in ODMG's OQL Share on Authors: Vanja Josifovski Department of Computer and Information Science, Linköping University, S-581 83 Linköping, Sweden and Database Research and Development Center, University of Florida Department of Computer and Information Science, Linköping University, S-581 83 Linköping, Sweden and Database Research and Development Center, University of FloridaView Profile , Stanley Y. W. Su Database Research and Development Center, University of Florida Database Research and Development Center, University of FloridaView Profile Authors Info & Claims CIKM '97: Proceedings of the sixth international conference on Information and knowledge managementJanuary 1997 Pages 332–340https://doi.org/10.1145/266714.266921Published:01 January 1997 0citation260DownloadsMetricsTotal Citations0Total Downloads260Last 12 Months0Last 6 weeks0 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 SiteGet Access

The main objective of a virtual enterprise (VE) is to allow a number of organizations to rapidly develop a working environment to manage a collection of resources contributed by the organizations toward the attainment of some common goals. One of the key requirements of a virtual enterprise is to develop an information infrastructure to support the interoperability of distributed and heterogeneous systems for controlling and conducting the business of the virtual enterprise. In order to achieve the objective and to meet this requirement, it is necessary to model all things of interest to a virtual enterprise such as data, human and hardware resources, organizational structures, business constraints, production processes, and activities in work management. Additionally, a system is needed to manage the meta-information and the shared data and to provide both build-time and run-time services to the heterogeneous systems to achieve their interoperability. In this paper, we describe the mo...

Management of large quantities of complex data is essential in many advanced application areas. Object-oriented (OO) database management system have been developed to effectively model and process the complex domain knowledge. They have been shown to outperform some existing relational systems. The existing implementations of OO database management systems attempt to improve the efficiency of OO queries by explicitly capturing the relationships among objects. However, the execution of complex queries involving the retrieval of objects from many classes and relationships among them causes the existing system to operate inefficiently. In this paper, we present parallel algorithms for the processing of queries against a large OO database. The algorithms are based on a closed model of query processing pattern-based access instead of the conventional value-based access. During processing, the algorithms avoid the execution of time-consuming join operations by making use of the explicitly stored object associations. Generation of large quantities of temporary data is avoided by marking objects using their identifiers and by employing a two-phase query processing strategy. A query is processed by concurrent multiple waves, thereby improving parallelism avoiding the complexities introduced in their sequential implementation. The correctness and the performance of the parallel algorithms have been tested and analyzed by running parallel programs on a 32-node transputer based parallel machine designed and developed at the IBM Research Center at Yorktown Heights, New York. Benchmark queries of different semantic complexities are generated, and their performance is analyzed for various data and query parameters.>

Expert systems and deductive database systems are knowledge-based systems which have the capability of storing andproeessing datartndknowledge rules, and performing logical deductions.The knowledge bases of these systems are usually assumed to be eonsisten~that is, no contradictions are deduced by the system.This assumption is not realistic since, in real-world applications, a knowledge base can contain a large number of rules which pose problems in terms of their ecmsistency.Thus, an automatic knowledge validation procedure is necessary for building a reliable knowledge-based system.In this paper, we present a knowledge validation technique based on the resolution principle to detect inconsistencies of a knowledge base.In this work, we formally define the eoneept of rule base inconsistency and show its relationship with the concept of unsatisfiability in formal logic.We also define completeness of a rule validation algorithm and show that our rule validation method is complete in the sense that it can not only identify all the input facts casing the system to deduee contradictions but also determine the specific subset of rules involved in the deductions of the contradictions.Based on this information, knowledge base designers can then make proper corrections to their knowledge base designs.A rule validation system using the proposed technique has been implemented in Prolog.

The application of the object-oriented (O-O) paradigm in the database management field has gained much attention in recent years. Several experimental and commercial O-O database management systems have become available. However, the existing O-O DBMSs still lack a solid mathematical foundation for the manipulation of O-O databases, the optimization of queries, and the design and selection of storage structures for supporting O-O database manipulations. This paper presents an association algebra (A-algebra) to serve as a mathematical foundation for processing O-O databases, which is analogous to the relational algebra used for processing relational databases. In this algebra, objects and their associations in an O-O database are uniformly represented by association patterns which are manipulated by a number of operators to produce other association patterns. Different from the relational algebra, in which set operations operate on relations with union-compatible structures, the A-algebra operators can operate on association patterns of homogeneous and heterogeneous structures. Different from the traditional record-based relational processing, the A-algebra allows very complex patterns of object associations to be directly manipulated. The pattern-based query formulation and the A-algebra operators are described. Some mathematical properties of the algebraic operators are presented together with their application in query decomposition and optimization. The completeness of the A-algebra is also defined and proven. The A-algebra has been used as the basis for the design and implementation of an object-oriented query language, OQL, which is the query language used in a prototype Knowledge Base Management System OSAM*.KBMS.>

The authors present a dynamically partitionable circular bus network (PCBN) and efficient algorithms for maximizing its utilization. In their approach, a distributed network is transformed into a graph, in which a vertex represents a communication request and an edge denotes the conflict between a pair of communication requests. A graph traversal algorithm is applied to the graph to identify some maximal independent sets of vertices. The communication requests corresponding to the vertices of a maximum independent set call proceed in parallel. By computing the expected size of the maximal independent sets of a graph, the improvement ratio of the network can be obtained. The network control and synchronization techniques of PCBN are described in detail. The idling problem in the execution of nonconflicting requests is also discussed.>

An association algebra (A-algebra) is presented for manipulating object-oriented (O-O) databases which is analogous to the relational algebra for relational databases. In this algebra, objects and their associations in an O-O database are uniformly represented by association patterns and are manipulated by a number of operators. These operators are defined to operate on association patterns of both heterogeneous and homogeneous structures. Very complex structures (e.g. network structures of object associations across several classes) can be directly manipulated by these operators. Therefore, the association algebra has greater expressive powers than the relational algebra which manipulates on relations of compatible structures. Some mathematical properties of these operators are described together with their application in query decomposition and optimization. The algebra has been used as the basis for the design and implementation of an O-O query language called OQL and a knowledge rule specification language.>

article Free Access Share on K: a high-level knowledge base programming language for advanced database applications Authors: Yuh-Ming Shyy Database Systems Research and Development Center, Department of Computer and Information Science, CSE 470, University of Florida, Gainesville, FL Database Systems Research and Development Center, Department of Computer and Information Science, CSE 470, University of Florida, Gainesville, FLView Profile , Stanley Y. W. Su Database Systems Research and Development Center, Department of Computer and Information Science, CSE 470, University of Florida, Gainesville, FL Database Systems Research and Development Center, Department of Computer and Information Science, CSE 470, University of Florida, Gainesville, FLView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991pp 338–347https://doi.org/10.1145/119995.115851Published:01 April 1991Publication History 15citation352DownloadsMetricsTotal Citations15Total Downloads352Last 12 Months13Last 6 weeks0 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

The design and analysis of a special function unit for database operations (SFU-DB) that uses a novel hardware sorting module, the automatic retrieval memory (ARM), are described. The SFU-DB is a functionally independent unit that efficiently performs certain nonnumeric operations. It can function as a coprocessor for a host CPU or as a special processing unit in a highly parallel processing system. The ARM implements in hardware a true distribution-based sort algorithm that requires no comparison operations. Without performing any comparison, the SFU-DB avoids the lower bound constraint on comparison-based sorting algorithms and achieves, for the worst case, a complexity of O(n) for both execution time and main memory size. Using the fundamental sort algorithm with slight modifications. the SFU-DB also uses the ARM as an engine for other primitive database operations such as relational join, elimination of duplicates, set union, set intersection, and set difference, also with complexity of O(n). The SFU-DB/ARM architecture is rather simple and requires only a modest amount of specialized hardware. The specialized hardware has been designed and simulated for fabrication using CMOS gate arrays, and the remainder of the SFU-DB has been simulated in software using Turbo Pascal running on an IBM-PC.>

An efficient dynamic graph traversal algorithm is used to identify nonconflicting requests and to allocate network resources in a dynamically partitionable bus network (DPBN). In centralized network control a special processor receives from the control computer of a partitionable bus network an adjacency matrix which indicates conflicts among requests. It applies the dynamic graph traversal algorithm and returns the identified nonconflicting requests to the control computer. The control computer then physically partitions the network into a number of subnetworks for processing the nonconflicting requests in parallel. In distributed control, each station determines conflicts and sets the switches. The results of performance evaluation show a 40% decrease of network delay as compared with a fully utilized, but unpartitioned local area network.>

A graphical user interface for an object-oriented query language, GOQL, is presented, GOQL is a part of a prototype knowledge base management system which is based on an object-oriented semantic association model, OSAM. GOQL consists of a graphical browser and a graphical querying module. The browser allows a user to browse through a complex knowledge-base schema graphically and prune it into a desired level of abstraction and details before the querying process. In the querying module, there are two modes, OQL and graphical OQL. The OQL mode is provided for knowledgeable users to directly type in the OQL command. In the graphical OQL mode, the user is guided through the formation of the query. It is noted that the object-oriented nature and the increased semantics of the underlying model and query language pose new challenges in user interface design due to their added complexity. On the other hand, these features also provide more information to the system in order to make the user interface more intelligent.>

The authors present two heuristic algorithms for determining traversal paths in a semantic network which models an object-oriented database. The first algorithm is an extension of Dijkstra's shortest path algorithm, and it identifies the most likely interpretation of an incomplete specified query. The second algorithm finds all possible interpretations of the query and ranks them in order of likely interpretations. Cost assignment for different paths is based on a set of heuristic rules which allows costs to be dynamically determined during a path traversal. The algorithms have been implemented and are in use in a graphics interface developed for an object-oriented knowledge base management system.>

A deductive rule-based language for object-oriented databases is presented. A deductive rule in this language derives new patterns of associations among objects of some selected classes if these objects fall in certain 'base' on other derived patterns. The patterns of object associations derived by a rule are held in a subdatabase whose intention consists of some selected classes and their associations. In other words, the structure of a derived subdatabase is represented using the structural constructs provided by the object-oriented data model and hence can be uniformly operated on by other rules to further derive new subdatabases. Therefore, the world of subdatabases is closed under this rule-based language.>

The object orientation of a semantic association model (OSAM) is presented. It integrates the concepts and techniques of semantic modeling and those introduced by the object-oriented paradigm. Unlike conventional data models such as the relational model, the object orientation of OSAM allows the user to model an application in terms of complex objects, classes and their associations, instead of tuples (or records) and relations (or record types). The primitives (objects, class, instance and link) and the perspectives (class and object) of an OSAM database are described. Key differences between OSAM and a conventional object-oriented model are discussed. The features of object orientation and explicit definition of semantic associations among objects allow the database of an application domain to be modeled, accessed and manipulated at a higher conceptual level and thus simplify the tasks of the users in the development of their applications.>

It is argued that present object-oriented (O-O) database management systems (DBMSs) have not gone far enough. Two important aspects of semantics are not captured in the Smalltalk-type O-O paradigm and the DBMSs that have been developed on the basis of this paradigm. The first aspect is the specification of knowledge rules which model constraints, expert knowledge, deductive rules, and trigger conditions that are applicable to objects. The second aspect is the specification of various types of associations that an object type can have with other object types. It is suggested that the O-O paradigm for future database or knowledge-base management systems should extend the concept of a class from that of object type to object class. Rule declaration, rule inheritance, and association types are discussed.>

An interactive design tool for designing CODASYL databases is described. The system is composed of three main modules: a user interface, a transaction analyzer, and a core module. The user interface allows a designer to enter interactively information concerning a database design which is to be evaluated. The transaction analyzer allows the designer to specify the processing requirements in terms of typical logical transactions to be executed against the database and translates these logical transaction into physical transaction which access and manipulate the physical databases. The core module is the implementation of a set of analytical models and cost formulas developed for the manipulation of indexed sequential and hash-based files and CODASYL sets. These models and formulas account for the situation in which occurrences of multiple record types are stored in the same area. Also presented are the results of a series of experiments in which key design parameters are varied. The system is implemented in UCSD Pascal running on IBM PCs.>

A description is given of a Petri-net-based methodology for modeling and evaluation of pipelined processing of concurrent database queries in an integrated data network (IDN). An extended Petri-net model is presented and used to model two key approaches to concurrent database query processing in the IDN, namely, pipelined and data-flow-based execution of queries and intermediate data sharing among concurrent queries. Database operations are categorized, and the models for the data flow and control flow in them are presented. A general-purpose Petri-net simulator has been developed using event-driven programming techniques and used to simulate the execution of the Petri-net models of some test queries. The results validate the results of a previous analytical evaluation in which the advantages of pipeline and intermediate data sharing were established. Since all the essential details of query processing in the IDN have been simulated, the results of this simulation study are believed to present closely the workings of the actual system.>

A query processing strategy which is based on pipelining and data-flow techniques is presented. Timing equations are developed for calculating the performance of four join algorithms: nested block, hash, sort-merge, and pipelined sort-merge. They are used to execute the join operation in a query in distributed fashion and in pipelined fashion. Based on these equations and similar sets of equations developed for other relational algebraic operations, the performance of query execution was evaluated using the different join algorithms. The effects of varying the values of processing time, I/O time, communication time, buffer size, and join selectively on the performance of the pipelined join algorithms are investigated. The results are compared to the results obtained by employing the same algorithms for executing queries using the distributed processing approach which does not exploit the vertical concurrency of the pipelining approach. These results establish the benefits of pipelining.>

This paper presents an analysis and evaluation of the performance of a multicomputer system (SM3) in supporting two basic matrix operations, namely multiplication and inversion. The system supports the efficient execution of the above mentioned operations by 1) achieving a high-bandwidth data transfer among computers by switching main memory modules, 2) supporting network partitioning, 3) employing a hardware communication and synchronization scheme, 4) using a distributed control technique, and 5) providing means to dynamically transfer control. Timing equations are derived and evaluated in an attempt to analyze the performance. Different cases which arise due to the relative sizes of memory modules and matrices during matrix multiplication are analyzed. The cases of partial and maximal pivoting during inversion are also analyzed. The SM3 system is compared quantitatively and qualitatively to a hypercube architecture.

This paper describes a general cost-benefit decision model that is applicable to the evaluation, comparison, and selection of alternative products with a multiplicity of features, such as complex computer systems. The application of this model is explained and illustrated using the selection of data management systems as an example. The model has the following features: (1) it is mathematically based on an extended continuous logic and a theory of complex criteria; (2) the decision-making procedure is very general yet systematic, well-structured, and quantitative; (3) the technique is based on a comprehensive cost analysis and an elaborate analysis of benefits expressed in terms of the decision maker's preferences. The decision methodology, when applied to the problem of selecting a data management system, takes into consideration the life cycle of a DMS and the objectives and goals for the new systems under evaluation. It allows the cost and preference analyses to be carried out separately using two different models. The model for preference analysis makes use of comprehensive performance (or preference) parameters and allows what we call a “logic scoring of preferences” using continuous values between zero and one, to express the degree with which candidate systems satisfy stated requirements. It aggregates preference parameters based on their relative weights and logical relationships to compute a global performance (preference) score for each system. The cost model incorporates an aggregation of costs which may be estimated over different time horizons and discounted at appropriate discount rates. A procedure to establish an overall ranking of alternative systems based on their global preference scores and global costs is also discussed.

The future data systems are likely to be integrated data networks (IDNs) consisting of a mix of general-purpose computer systems and special-purpose functional processors that are produced by different vendors and have quite different computational power and database management capabilities. Data stored in these networks need to be integrated and shared by the network users. It is important to have a query processing strategy in this type of network that can take advantage of the diverse functional capabilities of the component systems and the parallel processing potential of the network. In this paper, we present a query processing strategy which combines three known techniques: 1) query decomposition, 2) pipelined and data-flow processing of queries, and 3) intermediate result sharing among concurrent queries. The strategies for controlling and managing query and data pipelines are presented. Algorithms for the pipelined execution of the relational join operation are also described. Selected results of the evaluation of the query processing strategy, pipeline control strategies, and parallel algorithms are presented.

The architecture of a multicomputer system with switchable main memory modules (SM3) is presented. This architecture supports the efficient execution of parallel algorithms for nonnumeric processing by 1) allowing the sharing of switchable main memory modules between computers, 2) supporting dynamic partitioning of the system, and 3) employing global control lines to efficiently support interprocessor communication. Data transfer time is reduced to memory switching time by allowing some main memory modules to be switched between processors. Dynamic partitioning gives a common bus system the capability of an MIMD machine while performing global operations. The global control lines establish a quick and efficient high-level protocol in the system. The network is supervised by a control computer which oversees network partitioning and other global functions. The hardware involved is quite simple and the network is easily extensible. A simulation study using discrete event simulation techniques has been carried out and the results of the study are presented. The architecture of this system is compared to those of conventional local area networks and shared-memory systems in order to establish the distinct nature and characteristics of a multicomputer system based on the SM3 concept.

Achieving efficiency in database management functions is a fundamental problem underlying many computer applications. Efficiency is difficult to achieve using the traditional general-purpose von Neumann processors. Recent advances in microelectronic technologies have prompted many new research activities in the design, implementation, and application of database machines which are tailored for processing database management functions. To build an efficient system, the software algorithms designed for this type of system need to be tailored to take advantage of the hardware characteristics of these machines. Furthermore, special hardware units should be used, if they are cost- effective, to execute or to assist the execution of these software algorithms.

The architecture of a multicomputer system with switchable main memory modules (SM3) is presented. This architecture supports the efficient execution of parallel algorithms for non-numeric processing by 1) allowing the sharing of switchable main memory modules between computers, 2) supporting network partitioning, and 3) employing global control lines to efficiently support inter-processor communication. By allowing some main memory modules to be switched between processors, the data transfer time is reduced to memory switching time. Network partitioning gives a common bus network system the capability of a MIMD machine while performing global operations. The global control lines establish a quick and efficient high-level protocol in the system. The network is supervised by a Control Computer which oversees network partitioning and other global functions. The hardware involved is quite simple and the network is easily extensible. An analytical study using parallel algorithms for common database operations has been carried out to compare the SM3 System with several other architectures. The results of the study are presented.

To perform a statistical aggregation operation over a large file often requires that the records of the file be divided into categories based on the values of the attribute(s) over which some statistical computation is to be performed. It is rather inefficient to perform the necessary data transfer, categorization and statistical computation using a single processor Parallel algorithms designed for multiprocessor systems have been proposed and their performance improvement over the conventional systems has been demonstrated. It is shown in this paper that three to four times performance improvement can be further gained by using a dynamically partitionable multicomputer system with switchable main memory modules (SM3).

Protection of data in a database against unauthorized disclosure, alteration, or destruction is an important aspect of a multiuser database system. In a system which uses a celiular-logic device as a means for data management applications, protection can be achieved in part by associating security windows with queries. This paper describes a mechanism for dynamically creating these windows for cellular-logic devices. The mechanism mainly benefits from the associative techniques such as content and context searches, tagging and marking data, etc. These techniques allow the windows to be created physically by simultaneously activating related access control decision procedures, which implement access control decisions employed by the system, to mask out those data to which the user does not have the right of access. Furthermore, they enable the content-dependent security decisions to be efficiently implemented, eliminating the drawbacks found in conventional systems. Thus, a query accessing to a protected database system is identical to a query accessing to its companion window. An implementation of this mechanism on the cellular-logic device CASSM is also presented.

This paper presents the integrity control mechanism of the associative processing system, CASSM. The mechanism takes advantage of the associative techniques, such as content and context addressing, tagging and marking data, parallel processing, automatic triggering of integrity control procedures, etc., for integrity control and as a result offers three significant advantages: (1) The problem of staging data in a main memory for integrity checking can be eliminated because database storage operations are verified at the place where the data are stored. (2) The backout or merging procedures are relatively easy and inexpensive in the associative system because modified copies can be substituted for the originals or may be discarded by merely changing their associated tags. (3) The database management system software is simplified because database integrity functions are handled by the associative processing system to which a mainframe computer is a front-end computer.

This paper addresses the problem of application program conversion to account for changes in database semantics that result in changes in the schema and database contents. With the observation that the existing data models can be viewed as alternative ways of modeling the same database semantics, a methodology of application program analysis and conversion based on an existing-DBMS-model-and schema-independent representation of both the database and programs is presented. In this methodology, the source and target databases are described in terms of the association types of a semantic association model. The structural properties, the integrity constraints, and the operational characteristics (storage operation behaviors) of the association types are more explicitly defined to reveal the semantics that is generally hidden in application programs. The explicit descriptions of the source and target databases are used as the basis for program analysis and conversion. Application programs are described in terms of a small number of “access patterns” which define the data traversals and operations of the programs. In addition to the methodology, this paper (1) describes a model of a generalized application program conversion system that serves as a framework for research, (2) presents an analysis of access patterns that serve as the primitives for program description, (3) delineates some meaningful semantic changes to databases and their corresponding transformation rules for program conversion, (4) illustrates the application of these rules to two different approaches to program conversion problems, and (5) reports on the development effort undertaken at the University of Florida.

A memory organized around a major/minor loop magnetic bubble storage unit contains database information in relational form. An external marker memory, consisting of an M-bit shift register or an M X 1 RAM, provides, in conjunction with an assumed processing element, an associative search capability. Each bit accumulates search results of a query applied to its corresponding bubble page. The number of pages M equals the minor loop length and N, the page size, equals the number of minor loops in the bubble memory. A systematic series of performance-improving access strategies and architectural modifications are applied to an existing major/minor loop bubble device to determine the effects of each change. In all cases data access-time formulas reveal that positioning a marked page for access is a linear function of the minor loop length M, while outputting the marked pages via the bubbles serial output bus is a quadratic function of M. An evaluation and relative comparison of these architectures indicate that a segmented, nondestructive major/minor loop transfer function can enhance current magnetic bubble memory (MBM) performance in relational data processing by an order of magnitude.

The architectural characteristics and the implementation techniques of a context addressed segment sequential memory system called CASSM are described. The system provides hardware support for many database management functions. It offers associative and parallel processing capabilities for the efficient retrieval and manipulation of data in large databases. The hardware is designed mainly to support a hierarchical model for database applications but also contains facilities for supporting a wide range of data searches and operations useful for other nonnumeric data processing applications. The software development of the assembly language CASAL and its assembler, the high-level nonprocedural language CASDAL and its compiler, the interface to the CASSM-user interface computer, etc., have been carried out for the system. The hardware design and implementation techniques have been verified using a one-cell prototype system and a simulator designed for testing the system in the multicell environment. The emphasis of this paper is in the detailed description of the hardware features and techniques used in the multicell CASSM system.

A set of basic instruction sequences (DBTG's DML and COBOL statements) useful for the implementation of a generalized application program conversion system to account for various types of database changes is presented. It is used to form language templates which are DML's realization of a set of data-model and schema independent access patterns useful for describing the semantics of application programs.These basic instruction sequences are also useful for enforcing a standardized programming practice for developing application programs which would yield to automatic program conversion to account for database changes. In this paper, the methodology for program conversion is reviewed and the use of the basic instruction sequences for program analysis and synthesis is explained and illustrated.

There is much to be said on the limitations of the conventional Von Neumann processors and the available hardware organizations for database applications. Through research and development, several recent efforts have been in the investigation and development of new architectures and special prupose machines for supporting database applications. This panel aims to familiarize the attendants with 1) the motivations for works on data machines, 2) the objectives and characteristics of several categories of database machines, 3) the accomplishments made in this area of research and development, 4) the problems and current issues confronting the area, and 5) the impact of the current and future technologies on database management.

CASDAL is a high level data language designed and implemented for the database machine CASSM. The language is used for the manipulation and maintenance of a database using an unnormalized (hierarchically structured) relational data model. It also has facilities to define, modify, and maintain the data model definition. The uniqueness of CASDAL lies in its power to specify complex operations in terms of several new language constructs and its concepts of tagging or marking tuples and of matching values when walking from relation to relation. The language is a result of a top-down design and development effort for a database machine in which high level language constructs are directly supported by the hardware. This paper (1) gives justifications for the use of an unnormalized relational model on which the language is based, (2) presents the CASDAL language constructs with examples, and (3) describes CASSM's architecture and hardware primitives which match closely with the high level language constructs and facilitate the translation process. This paper also attempts to show how the efficiency of the language and the translation task can be achieved and simplified in a system in which the language is the result of a top-down system design and development.

This research studies the effects of 1) association changes in database semantics, 2) file composition and decomposition, and 3) the conversion of one DBMS to another to the application programs. A methodology of application program analysis and conversion based on database semantics is proposed. The semantics of both the source and target databases are described in terms of entity types and their associations. The semantics of application programs is represented by an "application structure" of language sequences which correspond to a number of access path graphs representing the general access patterns associated with entity types and their associations. Program conversion is achieved by meaning-preserving transformations of the access path graphs to account for the various types of database changes.

Since conventional computers are straining to handle the increased size and sophistication of non-numeric processing (data management, information retrieval, artificial intelligence), a new class of non-numeric architectures is evolving. The segment sequential architecture is one of these. Further development of this architecture requires new techniques for multiple cell operation and intercell communication to handle control and search operations. This paper describes such techniques for instruction fetching, operand recall, string, set and tree context searching, and pointer transfer. It is expected that combinations of these techniques will appear in future architectures that are needed for non-numeric processing.

A Self Managing Secondary Memory (SMSM) organization is proposed herein, in which hardware directly assists the storage, retrieval and management of arbitrary length records on such devices as fixed head discs or charge coupled devices (CCD's). This paper emphasizes some of the techniques used to implement an SMSM system.

This paper describes an on-going National Science Foundation sponsored project on the design and implementation of an associative memory system for handling large data base information storage and retrieval. The system uses a Clontext Addressed Segment Sequential Memory (CASSM) implemented on a head-per-track disc and an array of non-numeric microprocessors for processing data in parallel and in an associative manner. It provides hardware support to carry out Boolean searches, data base collection, and the execution of high-level data processing functions. It also contains facilities for processing data represented in several data models. The content and context addressing and parallel processing capabilities of CASSM offer potential solutions to several large data base problems. In this paper, the application view of CASSM is emphasized.

This paper presents the architecture of a context-addressed cellular system for non-numeric information processing, using an inexpensive, large-capacity circulating memory device. The system allows data to be represented in a structure very close to the form as the user perceives it (information structure) and allows the search operations of high level queries to be implemented directly. The information structures currently used in existing information systems are described. Then the architecture of the system as a whole is presented, as well as the implementation of these information structures as basic data types and hardware management of storage allocation and garbage collection.

This paper describes the design and implementation of a general associative net structure to be used in an interactive information system, and presents a scheme designed to manage large quantities of semantic data stored in a data base on disc. The associative-net-structured data base is functionally divided into two pools: the hierarchy pool and the linguistic pool. The network of items in the hierarchy pool represents the descriptive information about documents and the network of items in the linguistic pool represents the syntactic and semantic properties of the items in the hierarchy pool. Two search functions and a general search algorithm are presented in this paper. In the implementation, the data base is a regional data set on disc. Items and their associated labeled links are stored on disc tracks. The system establishes a directory to keep track of the items which have associated information stored on more than one track. The use of the directory eliminates unnecessary disc accesses and allows the system to move a proper track into core storage for data processing.