Science and Technology Studies Commons^™

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.

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 …

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 …

Algorithms For Structural Schema Integration, James Geller, Ashish Mehra, Yehoshua Perl, Erich Neuhold, Amit P. Sheth

Kno.e.sis Publications

Current view and schema integration methodologies are driven by semantic considerations, and allow integration of objects only if that is valid from semantic and structural viewpoints. We had introduced a new integration technique called structural integration. It permits integration of objects that have structural similarities, even if they differ semantically. This technique uses the object-oriented Dual Model which separates the representation of structure and semantics.

In this paper we introduce algorithms for structural integration. We apply these algorithms to integrate two views of a large university database schema which had significant structural similarities but differed semantically.

Executing Multidatabase Transactions, Mansoor Ansari, Marek Rusinkiewicz, Linda Ness, Amit P. Sheth

Kno.e.sis Publications

In a multidatabase environment, the traditional transaction model has been found to be too restrictive. Therefore, several extended transaction models have been proposed in which some of the requirements of transaction, such as isolation or atomicity, are optional. The authors describe one of such extensions, the flexible transaction model and discuss the scheduling of transactions involving multiple autonomous database systems managed by heterogeneous DBMS.

The scheduling algorithm for flexible transactions is implemented using L.0, a logically parallel language which provides a framework for concisely specifying the multidatabase transactions and for scheduling them. The key aspects of a flexible transaction specification, …

Specifying Interdatabase Dependencies In A Multidatabase Environment, Marek Rusinkiewicz, Amit P. Sheth, George Karabatis

Kno.e.sis Publications

The problem of interdatabase dependencies and the effect they have on applications updating interdependent data are addressed. A model that allows specifications of constraints among multiple databases in a declarative fashion is proposed. The separation of the constraints from the application programs facilitates the maintenance of data constraints and allows flexibility in their implementation. It allows investigation of various mechanisms for enforcing the constraints, independently of the application programs. By grouping the constraints together, it is possible to check their completeness and discover possible contradictions among them. The concepts of polytransactions, which use interdatabase dependencies to generate a series of …

On The Relationship Between Parsimonious Covering And Boolean Minimization, Venu Dasigi, Krishnaprasad Thirunarayan

Kno.e.sis Publications

Minimization of Boolean switching functions is a basic problem in the design of logic circuits. The designer first comes up with a switching function expressed in terms of several binary input variables that satisfies the desired functionality, and then attempts to minimize the function as a sum of products or product of sums. It turns out that a sum of products form of a switching function that has no redundancy is a union of prime implicants of the function.

In this paper we would like to explicate some of the relationships of the boolean minimization problem to a formalization of …

On Serializability Of Multidatabase Transactions Through Forced Local Conflict, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth

Kno.e.sis Publications

The main difficulty in enforcing global serializability in a multidatabase environment lies in resolving indirect transitive conflicts between multidatabase transactions. Indirect conflicts introduced by local transactions are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these problems, 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 their existence. Based …

The Architecture Of Braid: A System For Bridging Al/Db Systems, Amit P. Sheth, Anthony B. O'Hare

Kno.e.sis Publications

We describe the design of BrAID (a Bridge between Artificial Intelligence and Database Management Systems), an experimental system for the efficient integration of logic based Artificial Intelligence (Al) and database (DB) technologies. Features provided by BrAID include (a) access to conventional DBMSs, (b) support for multiple inferencing strategies, (c) a powerful caching subsystem that manages views and employs subsumption to facilitate the reuse of previously cached data, (d) lazy or eager evaluation of queries submitted by the AI system, and (e) the generation of advice by the AI system to aid in cache management and query execution planning. To discuss …

Management Of Interdependent Data: Specifying Dependency And Consistency Requirements, Amit P. Sheth, Marek Rusinkiewicz

Kno.e.sis Publications

Multiple databases that serve the needs of various application systems are considered. One of the significant problems in managing these databases is to maintain the related data items consistent to the required degree. This problem is frequently referred to as `redundant data management'. Since the term `redundancy' tends to imply that the data is unwanted or superfluous, the authors use the more general term `management of interdependent data'. Some preliminary ideas in this area are discussed. The problem of managing interdependent data is characterized, and some important types of interdatabase dependency are identified.

Attribute Relationships: An Impediment In Automating Schema Integration, Amit P. Sheth, Sunit K. Gala

Kno.e.sis Publications

Success in schema integration depends on understanding the semantics of schema components (e.g., entity sets, relationship sets, attributes), and the ability to capture and reason about these semantics. An important objective of our work on schema integration is to automate the reasoning as much as possible, and when not possible, depend on the human input and guidance. A key results of comparing the semantics associated with schema objects is that of determining attribute relationship. Once attribute relationships are determined, the task of object class(e.g., entity sets and relationship sets) integration becomes simpler and can e automated to a great extent. …

Fault Tolerance In A Very Large Database System: A Strawman Analysis, Amit P. Sheth

Kno.e.sis Publications

A simple model is used to study the effect of fault-tolerance techniques and system design on system availability. A generic multiprocessor architecture is used that can be configured in different ways to study the effect of system architectures. Important parameters studied are different system architectures and hardware fault-tolerance techniques, mean time to failure of basic components, database size and distribution, interconnect capacity, etc. Quantitative analysis compares the relative effect of different parameter values. Results show that the effect of different parameter values on system availability can be very significant. System architecture, use of hardware fault tolerance (particularly mirroring), and data …

A Tool For Integrating Conceptual Schemas And User Views, Amit P. Sheth, James A. Larson, Aloysius Cornelio, Shamkant B. Navathe

Kno.e.sis Publications

An interactive tool has been developed to assist database designers and administrators (DDA) in integrating schemas. It collects the information required for integration from a DDA, performs essential bookkeeping, and integrates schemas according to the semantics provided. The authors present the capabilities of this tool by discussing the integration methodology and the user interface of the tool.