An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method.

Presents a technique for semantic query optimization (SQO) for object databases. We use the ODMG-93 (Object Data Management Group) standard ODL (Object Database Language) and OQL (Object Query Language) languages. The ODL object schema and the OQL object query are translated into a DATALOG representation. Semantic knowledge about the object model and the particular application is expressed as integrity constraints. This is an extension of the ODMG-93 standard. SQO is performed in the DATALOG representation, and an equivalent logic query and (subsequently) an equivalent OQL object query are obtained. SQO is based on the residue technique of Chakravarthy et al. (1990). We show that our technique generalizes previous research on SQO for object databases. It can be applied to queries with structure constructors and method application. It utilizes integrity constraints about keys, methods and knowledge of access support relations, to produce equivalent queries, which may have more efficient evaluation plans.

We study the semantics of disjunctive logic programs that simultaneously contain multiple kinds of default negations. We introduce operators notG , notW , and notSTB in the language of logic programs to represent the Generalized Closed World Assumpti

Two or more companies, each with its own knowledge base, may merge. In that case one option is to merge the knowledge bases into one knowledge base. It can happen that some of the information contained in one or more knowledge bases may be in conflict with information in the other knowledge bases. There may be several such points of conflict and any information may be involved in several different such points of conflict. In that case, the integrator of the knowledge bases may prefer a certain claim to another in one conflict-point without necessarily preferring that claim in another conflict-point. Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give three types of semantics for priorities, two of which are shown to be equivalent to one another. The third type of semantics for priorities is shown to be more cautious than the other two. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.

Ordered model trees were introduced as a normal form for disjunctive deductive databases. They were also used to facilitate the computation of minimal models for disjunctive theories by exploiting the order imposed on the Herbrand base of the theory. In this work we show how the order on the Herbrand base can be used to compute perfect models of a disjunctive stratified finite theory. We are able to compute the stable models of a general finite theory by combining the order on the elements of the Herbrand base with previous results that had shown that the stable models of a theory T can be computed as the perfect models of a corresponding disjunctive theory ɛT resulting from applying the so called evidential transformation to T. While other methods consider many models that are rejected at the end, the use of atom ordering allows us to guarantee that every model generated belongs to the class of models being computed. As for negation‐free databases, the ordered tree serves as the canonical representation of the database.

The use of explicit negation enhances the expressive power of logic programs by providing a natural and unambiguous way to assert negated information about the domain being represented. We study the semantics of disjunctive programs that contain both

During the past decade, it has become increasingly clear that the future generation of large-scale knowledge bases will consist, not of one single isolated knowledge base, but a multiplicity of specialized knowledge bases that contain knowledge about different domains of expertise. These knowledge bases will work cooperatively, pooling together their varied bodies of knowledge, so as to be able to solve complex problems that no single knowledge base, by itself, would have been able to address successfully. In any such situation, inconsistencies are bound to arise. In this paper, we address the question: "Suppose we have a set of knowledge bases, KB1, …, KBn, each of which uses default logic as the formalism for knowledge representation, and a set of integrity constraints IC. What knowledge base constitutes an acceptable combination of KB1, …, KBn?"

Query evaluation in disjunctive deductive databases is in general computationally hard. The class of databases for which the process is tractable is severely limited. The complexity of the process depends on the structure of the database as well as on the type of query being evaluated. In this paper we study the issue of simplified query processing in disjunctive deductive databases. We address the possibility of evaluating general queries by independently processing their atomic components and describe the class of databases for which this approach is possible. We also discuss the issue of dividing a disjunctive deductive database into a set of disjoint components then answering queries and computing database completions by combining the results obtained against the individual components. Some practical special cases are considered. The methods developed in this paper can be utilized to introduce parallelism into the query evaluation process.

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process ofcombiningthe knowledge of these different experts is an important and nontrivial problem. We study this problem here when the expert systems are considered to be first‐order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.

Combining knowledge present in multiple knowledge base systems into a single knowledge base is discussed. A knowledge based system can be considered an extension of a deductive database in that it permits function symbols as part of the theory. Alternative knowledge bases that deal with the same subject matter are considered. The authors define the concept of combining knowledge present in a set of knowledge bases and present algorithms to maximally combine them so that the combination is consistent with respect to the integrity constraints associated with the knowledge bases. For this, the authors define the concept of maximality and prove that the algorithms presented combine the knowledge bases to generate a maximal theory. The authors also discuss the relationships between combining multiple knowledge bases and the view update problem.>

The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described and proved the correctness of a method for semantic query optimization in deductive databases couched in first-order logic. This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries. Additionally, we show how this method subsumes and generalizes earlier work on semantic query optimization. We also indicate how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.

I will discuss my experiences, some of the work that I have done and related work that influenced me, concerning deductive databases over the last 30 years. It will be convenient to divide this time period into roughly three equal parts, 1957 - 1968, 1969 - 1978, 1979 - present. For the first portion I will describe how my interest started in deductive databases in 1957, at a time when not even the field of databases existed I will describe work in the beginning years, leading to the start of deductive databases in about 1968 with the work of Cordell Green and Bertram Raphael.

article Free Access Share on A Note on Fuzzy Deduction Authors: Jack Minker Department of Computer Science, University of Maryland, College Park, Maryland Department of Computer Science, University of Maryland, College Park, MarylandView Profile , Alan R. Aronson Department of Computer Science, University of Maryland, College Park, Maryland Department of Computer Science, University of Maryland, College Park, MarylandView Profile , Barry E. Jacobs Department of Computer Science, University of Maryland, College Park, Maryland Department of Computer Science, University of Maryland, College Park, MarylandView Profile Authors Info & Claims Journal of the ACMVolume 27Issue 4Oct. 1980 pp 599–603https://doi.org/10.1145/322217.322218Published:01 October 1980Publication History 9citation453DownloadsMetricsTotal Citations9Total Downloads453Last 12 Months4Last 6 weeks1 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract It is argued that scientists and scientific organizations have an obligation to speak out in defense of human rights of scientists. The sentencing of Anatoly Shcharansky by the Soviet Union to thirteen years imprisonment is cited as a case in point. Because it is questionable that the Soviet Union upholds international scientific standards it is urged that either scientific conferences not be held in the Soviet Union, or that the organizing committee and attendees be vigilant in assuring free and open conferences. Finally, it is questioned as to whether or not it is advisable to cooperate in official scientific exchanges with the Soviet Union in view of their repressive acts against scientists.

An inferential relational system is one in which data in the system consists of both explicit facts and general axioms (or “views”). The general axioms are used together with the explicit facts to derive the facts that are implicit (virtual relations) within the system. A top-down algorithm, as used in artificial intelligence work, is described to develop inferences within the system. The top-down approach starts with the query, a conjunction of relations, to be answered. Either a relational fact solves a given relation in a conjunct, or the relation is replaced by a conjunct of relations which must be solved to solve the given relation. The approach requires that one and only one relation in a conjunction be replaced (or expanded) by the given facts and general axioms. The decision to expand only a single relation is termed a selection function. It is shown for relational systems that such a restriction still guarantees that a solution to the problem will be found if one exists. The algorithm provides for heuristic direction in the search process. Experimental results are presented which illustrate the techniques. A bookkeeping mechanism is described which permits one to know when subproblems are solved. It further facilitates the outputting of reasons for the deductively found answer in a coherent fashion.

This paper describes a comparative study of six binary inference systems and two search strategies employed in resolution-based problem solving systems. A total of 152 problems, most of which were taken from the recent literature, were employed. Each of these problems was attempted under a standard set of conditions using each inference system and each search strategy, for a total of twelve attempts for each problem. Using a variety of performance measures, a large number of hypotheses were examined in an effort to provide insight into the behavior of each inference system/search strategy combination. Whenever possible, the authors employed distribution-free statistical tests to minimize the subjectivity of the comparisons and hypothesis testing. Conclusions are presented concerning the effectiveness of the binary inference systems and search strategies, some effects of employing different problem representations, and certain characteristics of problems found to be significant in the overall system performance. Suggestions are made as to additional techniques that might enable theorem provers to solve practical problems.

In a relational data base, if a relation is listed explicitly in the data base, then questions asking whether the relation exists can be retrieved readily. There are questions that may be posed to such a system in which, although the answer is not listed in an explicit form, nonetheless, the answer is implicit within the system. In this paper, an algorithm is presented which will permit questions to be answered where the answer is implicit within the data base. One must infer the answer from the given relations. The problem of performing inferences is related to developments in the field of artificial intelligence: state-space, problem-reduction, and theorem-proving techniques all apply. It is shown how the answer to the question may be extracted, and the reasons for the deduction may be given. Developments required to construct an operational relational system for large data base problems with an inferential capability are discussed.

Abstract The objectives of this paper are to describe the effect of using weighted index terms in a document retrieval system, and to evaluate retrieval performance when queries are expanded by terms occurring in clusters with the query terms. Three data collections, each indexed by several methods, two of which were studied and reported on in previous work, are used to develop explicit results. The study both expands upon and extends previous work at the University of Maryland. The effect of weighting index terms in the document collection, the queries and the formation of clusters is analyzed. Eight cases are investigated in which index terms are weighted and unweighted. The best results are obtained when weighted index terms are used in forming clusters, in queries, and in documents. In this case, the results on the new collection demonstrate a significant improvement in retrieval performance relative to the performance with the unmodified data base, when clustered terms are added to queries. The improvement is in contrast to the results in the previous study, where a degradation in performance, or at best an insignificant improvement, was obtained. Comparisons are made to related work by Sparck‐Jones and her colleagues. This study tends to support the conclusion of Sparck‐Jones that weighted index terms provide better retrieval performance than unweighted terms. The cluster addition of index terms to queries yields unpredictable results. Some collections show an improvement in retrieval performance, others a degradation or no change in performance. Sparck‐Jones obtained an improvement in retrieval performance for her document collection. We conclude that the results are highly dependent upon the document collection, and the technique should be employed with caution.

An introduction and some prospectives are provided for the 1971 ACM Information Storage and Retrieval Symposium held at the University of Maryland on April 1 and 2, 1971. The symposium, sponsored by the University of Maryland, the National Aeronautics and Space Administration and the Special Interest Group on Information Retrieval (SIGIR) of the ACM, focuses on advances in techniques in the computer oriented technology of information retrieval. Early developments and the status of recent efforts in document retrieval, quesiton-answering and data management systems are reviewed briefly.

Several graph theoretic cluster techniques aimed at the automatic generation of thesauri for information retrieval systems are explored. Experimental cluster analysis is performed on a sample corpus of 2267 documents. A term-term similarity matrix is constructed for the 3950 unique terms used to index the documents. Various threshold values, T , are applied to the similarity matrix to provide a series of binary threshold matrices. The corresponding graph of each binary threshold matrix is used to obtain the term clusters. Three definitions of a cluster are analyzed: (1) the connected components of the threshold matrix; (2) the maximal complete subgraphs of the connected components of the threshold matrix; (3) clusters of the maximal complete subgraphs of the threshold matrix, as described by Gotlieb and Kumar. Algorithms are described and analyzed for obtaining each cluster type. The algorithms are designed to be useful for large document and index collections. Two algorithms have been tested that find maximal complete subgraphs. An algorithm developed by Bierstone offers a significant time improvement over one suggested by Bonner. For threshold levels T ≥ 0.6, basically the same clusters are developed regardless of the cluster definition used. In such situations one need only find the connected components of the graph to develop the clusters.

article Free AccessStorage Requirements for Information Handling Centers Authors: Herbert M. Gurk Radio Corporation of America, Astroelectronics Division, Princeton, New Jersey Radio Corporation of America, Astroelectronics Division, Princeton, New JerseyView Profile , Jack Minker University of Maryland, Computer Science Center, College Park, Maryland University of Maryland, Computer Science Center, College Park, MarylandView Profile Authors Info & Claims Journal of the ACMVolume 17Issue 1pp 65–77https://doi.org/10.1145/321556.321563Published:01 January 1970Publication History 5citation297DownloadsMetricsTotal Citations5Total Downloads297Last 12 Months16Last 6 weeks2 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

article Free Access Share on The Design and Simulation of an Information Processing System Authors: Herbert M. Gurk Radio Corporation of America, Princeton, NJ Radio Corporation of America, Princeton, NJView Profile , Jack Minker Radio Corporation of America, Princeton, NJ Radio Corporation of America, Princeton, NJView Profile Authors Info & Claims Journal of the ACMVolume 8Issue 2April 1961 pp 260–270https://doi.org/10.1145/321062.321073Published:01 April 1961Publication History 11citation467DownloadsMetricsTotal Citations11Total Downloads467Last 12 Months9Last 6 weeks1 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF