SQL is the standard database language, yet SQL statements can be complex and expensive to debug by hand. Automatic program repair techniques have the potential to reduce cost significantly. A previous attempt to repair SQL faults automatically used a decision tree (DT) algorithm that succeeded in some cases, but also generated many patches that passed the automated tests but that were not acceptable to the engineers. This paper proposes a novel fault localization and repair technique to repair faulty SQL statements. It targets faults in two common SQL constructs, JOIN and WHERE. It identifies the fault location and type precisely, and then creates a patch to fix the fault. We implemented this technique in a tool, and evaluated it on five medium to large-scale databases using 825 faulty queries with various complexity and faulty types. Experimental results showed that this technique can identify and repair JOIN faults when the DT approach is infeasible, and repair WHERE faults at about the same rate as the DT approach. Moreover, patches generated by our approach are more acceptable to engineers, and the tool is much faster.

Fault localization techniques have been applied to database and data-centric applications that use SQL or SQL-based languages. However, existing techniques can only identify the SQL statements that have faults, but not determine the precise location of the faults within SQL statements. Since SQL statements can be rather complex, programmers are still left with a difficult repair chore. We propose a novel fault localization method to localize multiple types of faults in SQL predicates, that is based on row-based dynamic slicing and delta debugging. Our method was implemented in a tool called ALTAR, and experiments were performed on two publicly available databases. Our method can be compared with existing fault localization techniques when these are applied to "drill-down" in SQL statements. The results showed that ALTAR can discover more types of faults. Moreover, for the type of faults discovered by current methods, ALTAR is more precise.

A collaborative manufacturing network is an alliance of business entities (mostly manufacturers and suppliers) who collaborate on the production of complex products. An essential element of this type of collaboration is that the participating entities are allowed to retain some measure of autonomy

We define a formal model for information services that incorporates the concept of service similarity. The model places services in metric spaces, and allows for services that have arbitrarily complex inputs and output domains. We then address the challenge of service substitution: finding the services most similar to a given service among a group, possibly large, of candidate services. To solve this nearest neighbor problem efficiently we embed the space of services into a vector space and search for the nearest neighbors in the target space. We report on an extensive experiment that validates both our formalization of similarity and the methods used for finding service substitutions.

We describe a method of inferring join plans for a set of relation instances, in the absence of any metadata, such as attribute domains, attribute names, or constraints (e.g., keys or foreign keys). Our method enumerates the possible join plans in order of likelihood, based on the compatibility of a pair of columns and their suitability as join attributes (i.e. their appropriateness as keys). We outline two variants of the approach. The first variant is accurate but potentially time-consuming, especially for large relations that do not fit in memory. The second variant is an approximation of the former and hence less accurate, but is considerably more efficient, allowing the method to be used online, even for large relations. We provide experimental results showing how both forms scale in terms of performance as the number of candidate join attributes and the size of the relations increase. We also characterize the accuracy of the approximate variant with respect to the exact variant.

A sequence of queries submitted by a database user within a short period of time may have a single, illuminating explanation. In this paper we consider sequences of single-record queries, and attempt to guess what information their authors may be trying to accumulate. Query sequences may reflect clandestine intentions, where users attempt to avoid direct queries which may disclose their true interests, preferring instead to obtain the same information by means of sequences of smaller, less conspicuous, queries. Sequences of queries may also reflect attempts to circumvent retrieval restrictions , where users attempt to approximate information which is inaccessible, with sequences of legitimate requests (in the latter case, our explanations may lead database owners to either tighten access, or, conversely, to reorganize their interfaces to facilitate access). Because the true objective of a sequence may be clouded by the retrieval of spurious records, our approach considers all the possible aggregates that a user may accumulate with a sequence, and to rank them, search-engine style, according to their plausibility as retrieval objectives. Our method is probabilistic in nature and postulates that the likelihood that a set of records is the true objective of the user is inverse proportional to the likelihood that this set results from random selection. Our method is shown to have good performance even in the presence of noise (spurious records) as high as 40–50%.

Considerable progress has been achieved in the area of virtual database systems, but substantial problems still persist. In this paper we discuss two current research directions: The resolution of extensional inconsistencies among databases participating in a virtual database, and the automatic incorporation of new information sources based on a process of discovery. Our approach to both problems involves to some degree what is often referred to as soft computing techniques.

In recent years, there has been considerable interest in techniques that enhance the cooperative behavior of database systems and many different techniques have been developed. These techniques approach the goal of cooperation in diverse ways; the differences may be in the specific task in which they offer cooperation, in the details of the solution, and even in the very interpretation of cooperative behavior. In this article we classify many different techniques into categories of cooperation, and we survey the techniques in some of these categories. Finally, we consider the challenges that remain and offer directions for new research. © 1996 John Wiley & Sons, Inc.

In addition to data, database systems store various kinds of information about their data. Examples are: class hierarchies, to define the various data classes and their relationships; integrity constraints, to state required relationships among the data; and inference rules, to define new classes in terms of known classes. This information is often referred to as intensional information (the data are referred to as extensional information). There have been several independent research works that suggested ways by which intensional information may be used to improve the conventional (extensional) database answers. Although each of these efforts developed its own specific methods, they all share a common belief: database answers would be improved if accompanied by intensional statements that describe them more abstractly. We study and compare the various approaches to intensional answers by using various classifications; we examine their relative merits with regard to key aspects; we discuss remaining issues; and we offer new research directions.>

Lately, there has been increased pressure on universities to place more emphasis on teaching, relative to research. Hence, this is a good time to discuss the state of database instruction in universities. The annual SIGMOD Conference brings together both the “producers” and the “consumers” of database education (i.e., university professors, and professionals representing research and development organizations). Hence, this is a good place to hold such a discussion.

The issues of database security and integrity are tightly related. Security mechanisms and integrity mechanisms are both concerned with protection of information, and both involve management of meta-information and procedures for screening transactions. Yet in database systems these tasks are entir ely separate. In this paper we describe a unified model that accommodates both security and integrity, with all protective restrictions stated in terms of database views. These protective restrictions are treated as knowledge, from which transaction screening procedures infer the restrictions that apply to individual transactions. A transaction may be allowed or denied in its entirety, or specific non-violating subtransactions may be identified. This process is an application of the view inference problem, to which we offer two alternative solutions. We then show how users can exploit information made available by the integrity mechanism to bypass the security mechanism, and discuss how such security breaches can be avoided. Finally, we show how the model can accommodate a broader concept of integrity that was introduced recently.

The role of database knowledge is usually limited to the evaluation of data queries. In this paper we argue that when this knowledge is of substantial volume and complexity, there is genuine need to query this repository of information. Moreover, since users of the database may not be able to distinguish between information that is data and information that is knowledge, access to knowledge and data should be provided with a single, coherent instrument. We provide an informal review of various kinds of knowledge queries, with possible syntax and semantics. We then formalize a framework of knowledge-rich databases, and a simple query language consisting of a pair of retrieve and describe statements. The retrieve statement is for querying the data (it corresponds to the basic retrieval statement of various knowledge-rich database systems). The describe statement is for querying the knowledge. Essentially, it inquires about the meaning of a concept under specified circumstances. We provide algorithms for evaluating sound and finite knowledge answers to describe queries, and we demonstrate them with examples.

FLEX a user interface to relational databases, can be used satisfactorily by users with different levels of expertise. FLEX is based on a formal query language, but is tolerant of incorrect input. It never rejects queries; instead, it adapts flexibility and transparently to their level of correctness and well-formedness, providing interpretations of corresponding accuracy and specificity. The most prominent design feature of FLEX is the smooth concatenation of several independent mechanisms, each capable of handling input of decreasing level of correctness and well-formedness. Each input is cascaded through this series of mechanisms until an interpretation is found. FLEX is also cooperative. It never delivers empty answers without explanation or assistance. By following up each failed query with a set of more general queries, FLEX determines whether an empty answer is genuine, in which case it suggests related queries that have nonempty answers, or whether it reflects erroneous presuppositions on the part of the user, in which case it then explains them.>

A model of access authorization is described for relational databases. In this model access permissions are a form of database knowledge, from which access permissions that apply to specific requests are inferred. Database access is specified in terms of views: a set of views is defined, and each user is granted permission to access one or more views. Users direct queries at the actual database, not at any particular view. When a request to access a view is presented to the database system, the system derives views of the request that are views of the views to which the user has access permission and presents the user only with these views. The model represents the definitions of views in special metarelations and extends standard algebraic operators to these relations.>

Database integrity has two complementary components: validity , which guarantees that all false information is excluded from the database, and completeness , which guarantees that all true information is included in the database. This article describes a uniform model of integrity for relational databases, that considers both validity and completeness. To a large degree, this model subsumes the prevailing model of integrity (i.e., integrity constraints). One of the features of the new model is the determination of the integrity of answers issued by the database system in response to user queries. To users, answers that are accompanied with such detailed certifications of their integrity are more meaningful. First, the model is defined and discussed. Then, a specific mechanism is described that implements this model. With this mechanism, the determination of the integrity of an answer is a process analogous to the determination of the answer itself.

A specific query establishes a rigid qualification and is concerned only with data that match it precisely. A vague query establishes a target qualification and is concerned also with data that are close to this target. Most conventional database systems cannot handle vague queries directly, forcing their users to retry specific queries repeatedly with minor modifications until they match data that are satisfactory. This article describes a system called VAGUE that can handle vague queries directly. The principal concept behind VAGUE is its extension to the relational data model with data metrics, which are definitions of distances between values of the same domain. A problem with implementing data distances is that different users may have different interpretations for the notion of distance. VAGUE incorporates several features that enable it to adapt itself to the individual views and priorities of its users.

An important advantage of a database system is that it provides each application with a custom view of the data. The issue addressed in this paper is how to provide such custom views to applications that access multiple databases. The paper describes a formal method that generates such superviews, in an interactive process of schema editing operations. A mapping of the superview into the individual databases is derived from the editing process, and is stored together with the superview as a virtual database. When this database is interrogated, the mapping is used to decompose each query into a set of queries against the individual databases, and recompose the answers to form an answer to the original query. As this process is transparent to the user, virtual databases may be regarded as a more general type of databases. A prototype database system, that allows users to construct virtual databases and interrogate them, has been developed.

In this paper we introduce the Time Warp mechanism as a new method for concurrency control in distributed database systems. Its major distinguishing features are first, a unification of transactions and data as two forms of the more general notion of object, and second, the use of object rollback as the fundamental tool for synchronization instead of blocking or abortion.

In an unstructured database the data is a collection of facts that does not adhere to any schema. Such a database does not require any initial design and can therefore evolve freely to accommodate new applications. It is particularly suitable for information which is diverse and idiosyncratic, such as when we want to store everything known on a particular topic. Unfortunately, this freedom also means that similar information may be entered in different forms. This may cause severe problems when retrieval is attempted, as some of the data may appear to have been "lost" in the database. In this paper we propose a method to solve this problem. Each database fact must be supported by a context in the database, in the form of several other facts. When an attempt is made to add a fact to the database, the existence of a suitable context is verified, or is extracted from the user in a simple dialogue. Thus, the database still retains the flexibility of unstructured databases, but problems of multiple representations are usually prevented.

A database token is a value of either the data or the metadata. Usually, such tokens are combined with formal language constructs to form queries. In this paper we show how a given set of tokens may be completed to a proper query. This process provides a useful means of communication between naive users and databases, allowing them to express simple requests by listing several tokens. As the inferred query is always shown to the user, this process has a side effect of instructing the user in the proper use of the query language. The method is described and demonstrated with relational databases, but its principles may be implemented with other databases as well.

The standard, most efficient method to retrieve information from databases can be described as systematic retrieval: The needs of the user are described in a formal query, and the database management system retrieves the data promptly. There are several situations, however, in which systematic retrieval is difficult or even impossible. In such situations exploratory search (browsing) is a helpful alternative. This paper describes a new user interface, called BAROQUE, that implements exploratory searches in relational databases. BAROQUE requires few formal skills from its users. It does not assume knowledge of the principles of the relational data model or familiarity with the organization of the particular database being accessed. It is especially helpful when retrieval targets are vague or cannot be specified satisfactorily. BAROQUE establishes a view of the relational database that resembles a semantic network, and provides several intuitive functions for scanning it. The network integrates both schema and data, and supports access by value. BAROQUE can be implemented on top of any basic relational database management system but can be modified to take advantage of additional capabilities and enhancements often present in relational systems.

Every information system incorporates a database component, and a frequent activity of users of information systems is to present it with queries. These queries reflect the presuppositions of their authors about the system and the information it contains. With most query processors, queries that are based on erroneous presuppositions often result in null answers. These fake nulls are misleading, since they do not point out the user's erroneous presuppositions (and can even be interpreted as their affirmation). This article describes the SEAVE mechanism for extracting presuppositions from queries and verifying their correctness. The verification is done against three repositories of information: the actual data, their integrity constraints, and their completeness assertions. Consequently, queries that reflect erroneous presuppositions are answered with informative messages instead of null answers, and user-system communication is thus improved (an aspect that is particularly important in systems that often are accessed by naive users). First, the principles of SEAVE are described abstractly. Then, specific algorithms for implementing it with relational databases are presented, including a new method for storing knowledge and an efficient algorithm for processing queries against the knowledge.

Current database architectures emphasize structure and are inappropriate for applications which model environments that are subject to constant evolution, or environments which do not lend themselves to massive classifications In this paper we describe an architecture which promotes databases that are only loosely structured heaps of facts instead of highly structured data This architecture avoids the traditional dichotomy between "schema" and "data", and it incorporates a single mechanism for defining both inference rules and integrity constraints As lack of organization will usually have adverse effect on retrieval, the principal retrieval method for loosely structured databases is browsing exploratory searching which does not assume any knowledge of the organization (or even the very existence of organization) Two styles of browsing, called navigation and probing, are defined Both are derived from a standard query language based on predicate logic

A method is described for integrating two or more databases into a conceptual "superview", through a set of schema transformations. Such integration may be useful when it is required to produce a unified view of two databases while preserving their physical independence. Each transformation defines a mapping of queries against the superview into the appropriate set of queries against the underlying databases and imposes a constraint that is checked when the query is evaluated. A program that interactively aids the user in constructing the superview and that performs this query transformation is being developed.