Bioinformatics Commons^™

Characterizing A Portable Subset Of Behavioral Vhdl-93, Krishnaprasad Thirunarayan, Robert Ewing

Kno.e.sis Publications

Goossens defined a structural operational semantics for a subset of VHDL-87 and proved that the parallelism present in VHDL is benign. We extend this work to include VHDL-93 features such as shared variables and postponed processes that change the underlying semantic model. In the presence of shared variables, nondeterministic execution of VHDL-93 processes destroys the unique meaning property. We identify and characterize a class of portable VHDL-93 descriptions for which unique meaning property can be salvaged. Our specification can serve as a correctness criteria for a VHDL-93 simulator.

The Carnot Heterogeneous Database Project: Implemented Applications, Munindar Singh, Phil Cannata, Michael N. Huhns, Nigel Jacobs, Tomasz Ksiezyk, Kayliang Ong, Amit P. Sheth, Christine Tomlinson, Darrell Woelk

Kno.e.sis Publications

The Carnot project was an ambitious research project in heterogeneous databases. It integrated a variety of techniques to address a wide range of problems in achieving interoperation in heterogeneous environments. Here we describe some of the major implemented applications of this project. These applications concern(a) accessing a legacy scientific database, (b) automating a workflow involving legacy systems, (c) cleaning data, and (d) retrieving semantically appropriate information from structured databases in response to text queries. These applications support scientific decision support, business process management, data integrity enhancement, and analytical decision support, respectively. They demonstrate Carnot‘s capabilities for (a) heterogeneous query processing, …

Some Relationships Between Foies And Sigma 1 1 Arity Hierarchies, Guozhu Dong, Limsoon Wong

Kno.e.sis Publications

No abstract provided.

Structural Issues In Active Rule Systems, James Bailey, Guozhu Dong, Kotagiri Ramamohanarao

Kno.e.sis Publications

Active database systems enhance the functionality of traditional databases through the use of active rules or ‘triggers’. There is little consensus, though, on what components should be included in a rule system. In this paper, the expressive power of some simple active database rule systems is examined and the effect of choosing different features studied. Four important parameters of variation are presented, namely the rule language, the external query language, the meta rule language and the pending rule structure. We show that each of these is highly influential in determining the expressiveness of the rule system as a whole, and …

An Error Handling Framework For The Orbwork Workflow Enactment Service Of Meteor, Davasish Worah, Amit P. Sheth, Krzysztof J. Kochut, John A. Miller

Kno.e.sis Publications

Workflow Management Systems (WFMSs) can be used to re-engineer, streamline, automate, and track organizational processes involving humans and automated information systems. However, the state-of-the-art in workflow technology suffers from a number of limitations that prevent it from being widely used in large-scale mission critical applications. Error handling is one such issue. What makes the task of error handling challenging is the need to deal with errors that appear in various components of a complex distributed application execution environment, including various WFMS components, workflow application tasks of different types, and the heterogeneous computing infrastructure.

In this paper, we discuss a top-down …

Algorithms For Adapting Materialised Views In Data Warehouses, Mukesh Mohania, Guozhu Dong

Kno.e.sis Publications

In this paper we consider the problem of materialised view adaptation in data warehouses. Materialised views are important in data warehousing where they are used to speed up query processing on large amounts of data. User requirements change over time, which may change the definitions of views dynamically. For such situations, the question arises whether the materialised views should be recomputed from scratch for every change in the definition or they should be obtained by adapting old materialised views. Changes to a view definition may be expensive, if the view is recomputed from scratch. Therefore, it is worthwhile to examine …

On The Portability Of Behavioral Vhdl-93, Krishnaprasad Thirunarayan, Robert Ewing

Kno.e.sis Publications

Goossens defined a structural operational semantics for a subset of VHDL-87 and proved that the parallelism present in VHDL is benign. We extend this work to include shared variables in VHDL-93 that changes the underlying semantic model. In the presence of shared variables, non-deterministic execution of VHDL-93 processes destroys the unique meaning property. We identify and characterize a class of portable VHDL-93 descriptions for which unique meaning property can be salvaged.

Managing Multiple Information Sources Through Ontologies: Relationship Between Vocabulary Heterogeneity And Loss Of Information, Eduardo Mena, Vipul Kashyap, Arantza Illarramendi, Amit P. Sheth

Kno.e.sis Publications

The ability to deal with a huge number of independent and heterogeneous repositories is the most critical problem in Global Information Systems. One approach to enable efficient query processing is by utilizing semantic descriptions (organized as ontologies) of such repositories whenever available.

In this context semantic relationships among ontologies can be used Query Processors. Three kind of relationships are considered: synonyms and hypernyms. Using synonyms the semantic of the query is preserved; however, when synonyms are not available and hypernyms or hyponyms are used there exists some loss of information that must be measured.

1: "To Know Ourselves", The U.S. Department Of Energy, The Human Genome Project

Genomics: Past & Future

AT THE END OF THE ROAD in Little Cottonwood Canyon, near Salt Lake City, Alta is a place of near-mythic renown among skiers. In time it may well assume similar status among molecular geneticists. In December 1984, a conference there, co-sponsored by the U.S. Department of Energy, pondered a single question: Does modern DNA research offer a way of detecting tiny genetic mutations—and, in particular, of observing any increase in the mutation rate among the survivors of the Hiroshima and Nagasaki bombings and their descendants? In short the answer was, Not yet. But in an atmosphere of rare intellectual fertility, …

Observer: An Approach For Query Processing In Global Information Systems Based On Interoperation Across Pre-Existing Ontologies, Eduardo Mena, Vipul Kashyap, Amit P. Sheth, Arantza Illarramendi

Kno.e.sis Publications

The huge number of autonomous and heterogeneous data repositories accessible on the “global information infrastructure” makes it impossible for users to be aware of the locations structure/organization, query languages and semantics of the data in various repositories. There is a critical need to complement current browsing, navigational and information retrieval techniques with a strategy that focuses on information content and semantics. In any strategy that focuses on information content, the most critical problem is that of different vocabularies used to describe similar information across domains. We discuss a scalable approach for vocabulary sharing. The objects in the repositories are represented …

Proof Strategies For Hardware Verification, Robert Eastham, Krishnaprasad Thirunarayan

Kno.e.sis Publications

Ascertaining correctness of digital hardware designs through simulation does not scale-up for large designs because of the sheer combinatorics of the problem. Formal verification of hardware designs holds promise because its computational complexity is of the order of number of different types of components (and not number of components in the design). This approach requires the specification of the behavior and the design in a formal language, and reason with them using a theorem prover. In this paper we attempt to develop a methodology for writing and using these specifications for some important classes of hardware circuits. We examine digital …

Ultrasound Three- Dimensional Velocity Measurements By Feature Tracking, Gregory R. Bashford, Olaf T. Von Ramm

Biomedical Imaging and Biosignal Analysis Laboratory

This article describes a new angle-independent method suitable for three-dimensional (3-D) blood flow velocity measurement that tracks features of the ultrasonic speckle produced by a pulse echo system. In this method, a feature is identified and followed over time to detect motion. Other blood flow velocity measurement methods typically estimate velocity using one- (1-D) or two-dimensional (2-D) spatial and time information. Speckle decorrelation due to motion in the elevation dimension may hinder this estimate of the true 3-D blood flow velocity vector. Feature tracking is a 3-D method with the ability to measure the true blood velocity vector rather than …

Chaos And Detection, Andrew M. Fraser

Systems Science Faculty Publications and Presentations

I report on numerical experiments in which a detector reliably found chaotic signals at signal to noise ratios as low as -15 dB. The detector was based on a variant of the hidden Markov models used in speech research. The task was particularly difficult because the Fourier power spectrum of the noise was constructed to match the spectrum of the signal. I review likelihood ratio detectors, limitations on the performance of linear models implied by the broad Fourier power spectra of chaotic signals, and the upper limit that the Kolmogorov-Sinai (KS) entropy of a chaotic system places on the expected …

Spieltheorie, Alexander Chocholaty, Pascal Hitzler

Computer Science and Engineering Faculty Publications

No abstract provided.

Semantic And Schematic Similarities Between Database Objects: A Context-Based Approach, Vipul Kashyap, Amit P. Sheth

Kno.e.sis Publications

In a multidatabase system, schematic conflicts between two objects are usually of interest only when the objects have some semantic similarity. We use the concept of semantic proximity, which is essentially an abstraction/mapping between the domains of the two objects associated with the context of comparison. An explicit though partial context representation is proposed and the specificity relationship between contexts is defined. The contexts are organized as a meet semi-lattice and associated operations like the greatest lower bound are defined. The context of comparison and the type of abstractions used to relate the two objects form the basis of a …

Simulation Modeling Within Workflow Technology, John A. Miller, Amit P. Sheth, Krzysztof J. Kochut, Xuzhong Wang, Arun Murugan

Kno.e.sis Publications

This paper presents an approach for integrating simulation modeling and analysis capabilities within the workflow management system (WFMS) being developed in the Large Scale Distributed Information Systems (LSDIS) Lab at the University of Georgia. Simulation modeling can be used for studying the efficiency of workflow designs as well as studying the general performance and reliability of WFMSs. We also discuss the importance of using sophisticated monitoring and animation capabilities, and the use of workflow management technology to advance simulation technology itself. Finally, we demonstrate a sample simulation where tasks and task managers are simulated.

On The Equivalence Of Upward And Downward Inheritance Reasoners, Krishnaprasad Thirunarayan

Kno.e.sis Publications

In this paper, we analyze systematically the downward (property flow) and the upward (individual flow) views of inheritance for different categories of inheritance networks. We observe that both these views assign the same meaning to tree-structured hierarchies, and explain the divergence in the interpretation of more general networks in terms of their expressive power. This simple analysis sheds light on the inherent nature of nonmonotonic inheritance and can form the basis for the design of efficient algorithms for certain classes of queries. In addition, we describe the notion of preferential inheritance to specify additional conflict resolution information that can be …

Power Systems Marginal Cost Curve And Its Applications, Shaojun Wang, S. M. Shahidehpour, Nian-De Xiang

Kno.e.sis Publications

This paper presents a forward recursive procedure to calculate the expected system marginal cost curve (EMC). The EMC formulation allows for multi-state and multi-block dispatch of generating units and is used to determine the optimal energy of pumped-storage units. A new approach is developed to compute the first and second derivatives of the expected generation energy of a thermal unit with respect to the capacity of all thermal units in the system. The salient feature of the proposed approach is that it applies to hydro-thermal systems with multiple limited-energy hydro units.

Predicting Conserved Water-Mediated Interactions In Protein Active Sites, Michael L. Raymer, Sridhar Venkataraman, William F. Punch, Erik D. Goodman, Brenda Kuhn

Kno.e.sis Publications

No abstract provided.

A Meta-Interpreter For Circuit-Extraction, Krishnaprasad Thirunarayan

Kno.e.sis Publications

The design of a VLSI circuit consists of a description of the circuit in terms of its components and subcomponents, at various levels of detail. To verify that the layout of a VLSI circuit conforms to its design, one needs to work backwards from the lowest-level description of the circuit and recognize the higher-level components it constitutes. This paper is concerned with the application of logic programming techniques in the formal verification of the structural correctness of the VLSI circuit layouts. In particular, we review Michael Dukes' Generalized Extraction System (1990) that compiles design descriptions into a set of extraction …

Nonrecursive Incremental Evaluation Of Datalog Queries, Guozhu Dong, Jianwen Su, Rodney Topor

Kno.e.sis Publications

We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process “incremental query evaluation using conjunctive queries”. After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, …

The "Infoharness" Information Integration Platform, Leon Shklar, Satish Thatte, Howard Marcus, Amit P. Sheth

Kno.e.sis Publications

The "InfoHarness" information integration platform, tools, and services being developed at Bellcore are aimed at providing integrated and rapid access to huge amounts of heterogeneous information independent of the type, representation, and location of information. InfoHarness provides advanced search and browsing capabilities without imposing the burden of restructuring, reformatting or relocating information on information suppliers or creators. This is achieved through object-oriented encapsulation of information and the associated meta-information (e.g., type, location, access rights, owner, creation date, etc.). The meta-information extraction methods ensure rapid and largely automatic creation of information repositories. A gateway that supports access to InfoHarness repositories from …

Using Tickets To Enforce The Serializability Of Multidatabase Transactions, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth

Kno.e.sis Publications

To enforce global serializability in a multidatabase environment the multidatabase transaction manager must take into account the indirect (transitive) conflicts between multidatabase transactions caused by local transactions. Such conflicts are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these difficulties, we propose to incorporate additional data manipulation operations in the subtransactions of each multidatabase transaction. We show that if these operations create direct conflicts between subtransactions at each participating local database system, indirect conflicts can be resolved even if the multidatabase system is not aware of …

Semantics-Based Information Brokering: A Step Towards Realizing The Infocosm, Vipul Kashyap, Amit P. Sheth

Kno.e.sis Publications

The rapid advances in computer and communication technologies, and their merger, is leading to a global information market place. It will consist of federations of very large number of information systems that will cooperate to varying extents to support the users' information needs. We propose an architecture which may facilitate meeting these needs. It consists of three main components: information providers, information brokers and information consumers. We also propose an approach to information brokering. We discuss two of it's tasks: information resource discovery, which identities relevant information sources for a given query, and query processing, which involves the generation of …

Specifying And Enforcing Intertask Dependencies, Paul Attie, Munindar Singh, Amit P. Sheth, Marek Rusinkiewicz

Kno.e.sis Publications

Extensions of the traditional atomic transaction model are needed to support the development of multi-system applications or workflows that access heterogeneous databases and legacy application systems. Most extended transaction models use conditions involving events or dependencies between transactions. Intertask dependencies can serve as a uniform framework for defining extended transaction models. In this paper we introduce event attributes needed to determine whether a dependency is enforceable and to properly schedule events in extended transaction models. Using these attributes and a formalization of a dependency into the temporal logic CTL, we can automatically synthesize an automaton that captures the computations that …

A Framework For Controlling Cooperative Agents, Kuo-Chu Lee, William H. Mansfield, Amit P. Sheth

Kno.e.sis Publications

Presents an overview of the ITX (Interacting Transaction) system, which supports complex interactions among cooperating agents in the presence of user interventions that change application objectives and system failures. The system's components and its unique fixed-point criterion for feedback control of iterative interactions are described. An example of a simplified multimedia teleconferencing application is discussed to illustrate the features of the ITX system.

So Far (Schematically) Yet So Near (Semantically), Amit P. Sheth, Vipul Kashyap

Kno.e.sis Publications

In a multidatabase system, schematic conflicts between two objects are usually of interest only when the objects have some semantic affinity. In this paper we try to reconcile the two perspectives. We first define the concept of semantic proximity and provide a semantic taxonomy. We then enumerate and classify the schematic and data conflicts. We discuss possible semantic similarities between two objects that have various types of schematic and data conflicts. Issues of uncertain information and inconsistent information are also addressed.

On Transactional Workflows, Amit P. Sheth, Marek Rusinkiewicz

Kno.e.sis Publications

The basic transaction model has evolved over time to incorporate more complex transactions structures and to take the advantage of semantics of higher-level operations that cannot be seen at the level of page reads and writes. Well known examples of such extended transaction models include nested and multi-level transactions. A number of relaxed transaction models have been defined in the last several years that permit a controlled relaxation of the transaction isolation and atomicity to better match the requirements of various database applications. Correctness criteria other than global serializability have also been proposed. Several examples of extended/relaxed transaction models are …

Abduction In Annotated Logic Programming, Krishnaprasad Thirunarayan

Kno.e.sis Publications

The author investigates techniques to make the logic programming paradigm more expressive for knowledge representation, while simultaneously retaining the computational advantages of efficiency and simplicity. He extends the annotated language of K. Thirunarayan and K. Kifer (1989) in various directions to obtain an enriched representation language. In particular, rule bodies are permitted to be a conjunction of literals, and the rules to be recursive. A class of annotated logic programs called the stratified programs is identified which can be given a unique supported minimal Herbrand model as their meaning. Abductive reasoning is integrated into this annotated logic framework. The notion …

Using Flexible Transactions To Support Multisystem Telecommunication Applications, Mansoor Ansari, Linda Ness, Marek Rusinkiewicz, Amit P. Sheth

Kno.e.sis Publications

Service order provisioning is an important telecommunication application that automates the process of providing telephone services in response to the customer requests. It is an example of a multi-system application that requires access to multiple, independently developed application systems and their databases. In this paper, we describe the design and implementation of a prototype system1 that supports the execution of the Flexible Transactions and its use to develop the service order provisioning application. We argue that such approach may be used to support the development of multi-system, flow-through processing applications in a systematic and organized manner. Its advantages include fast …