Attribute-based access control (ABAC) is a general access control model that subsumes numerous earlier access control models. Its increasing popularity stems from the intuitive generic structure of granting permissions based on application and domain attributes of users, subjects, objects, and other entities in the system. Multiple formal and informal languages have been developed to express policies in terms of such attributes. The utility of ABAC policy languages is potentially undermined without a properly formalized underlying model. The high-level structure in a majority of ABAC models consists of sets of tokens and sets of sets, expressions that demand that the reader unpack multiple levels of sets and tokens to determine what things mean. The resulting reduced readability potentially endangers correct expression, reduces maintainability, and impedes validation. These problems could be magnified in models that employ nonuniform representations of actions and their governing policies. We propose to avoid these magnified problems by recasting the high-level structure of ABAC models in a logical formalism that treats all actions (by users and others) uniformly and that keeps existing policy languages in place by interpreting their attributes in terms of the restructured model. In comparison to existing ABAC models, use of a logical language for model formalization, including hierarchies of types of entities and attributes, promises improved expressiveness in specifying the relationships between and requirements on application and domain attributes. A logical modeling language also potentially improves flexibility in representing relationships as attributes to support some widely used policy languages. Consistency and intelligibility are improved by using uniform means for representing different types of controlled actions---such as regular access control actions, administrative actions, and user logins---and their governing policies. Logical languages also provide a well-defined denotational semantics supported by numerous formal inference and verification tools.

Many applications, including provenance and some analyses of social networks, require path-based queries over graphstructured data. When these graphs contain sensitive information, paths may be broken, resulting in uninformative query results. This paper presents innovative techniques that give users more informative graph query results; the techniques leverage a common industry practice of providing what we call surrogates: alternate, less sensitive versions of nodes and edges releasable to a broader community. We describe techniques for interposing surrogate nodes and edges to protect sensitive graph components, while maximizing graph connectivity and giving users as much information as possible. In this work, we formalize the problem of creating a protected account G' of a graph G. We provide a utility measure to compare the informativeness of alternate protected accounts and an opacity measure for protected accounts, which indicates the likelihood that an attacker can recreate the topology of the original graph from the protected account. We provide an algorithm to create a maximally useful protected account of a sensitive graph, and show through evaluation with the PLUS prototype that using surrogates and protected accounts adds value for the user, with no significant impact on the time required to generate results for graph queries.

This demonstration presents Galaxy, a schema manager that facilitates easy and correct data sharing among autonomous but related, evolving data sources. Galaxy reduces heterogeneity by helping database developers identify, reuse, customize, and advertise related schema components. The central idea is that as schemata are customized, Galaxy maintains a derivation graph, and exploits it for data exchange, discovery, and multi-database query over the "galaxy" of related data sources. Using a set of schemata from the biomedical domain, we demonstrate how Galaxy facilitates schema and data sharing.

Data integration systems often provide a uniform query interface, called amediated schema, to a multitude of data sources. To answer user queries, such systems employ a set ofsemantic matchesbetween the mediated schema and the data-source schemas. Finding such matches is well known to be difficult. Hence much work has focused on developing semi-automatic techniques to efficiently find the matches. In this paper we consider the complementary problem ofimproving the mediated schema, to make finding such matches easier. Specifically, a mediated schemaSwill typically be matched with many source schemas. Thus,can the developer of S analyze and revise S in a way that preserves S's semantics, and yet makes it easier to match with in the future? In this paper we provide an affirmative answer to the above question, and outline a promising solution direction, calledmSeer. Given a mediated schemaSand a matching toolM,mSeerfirst computes a matchability score that quantifies how wellScan be matched against usingM. Next,mSeeruses this score to generate a matchability report that identifies the problems in matchingS.Finally,mSeeraddresses these problems by automatically suggesting changes toS(e.g., renaming an attribute, reformatting data values, etc.) that it believes will preserve the semantics ofSand yet make it more amenable to matching. We present extensive experiments over several real-world domains that demonstrate the promise of the proposed approach.

The goal of EII systems is to provide uniform access to multiple data sources without having to first load them into a data warehouse. Since the late 1990's, several EII products have appeared in the marketplace and significant experience has been accumulated from fielding such systems. This collection of articles, by individuals who were involved in this industry in various ways, describes some of these experiences and points to the challenges ahead.

The target audience for this tutorial is the entire SIGMOD research community. The goals of the tutorial are to enlighten the SIGMOD research community about the state of the art in data security, especially for enterprise or larger systems, and to engage the community's interest in improving the state of the art.

No abstract available.

Data security (protection of information rather than systems) goes far beyond the traditional questions of RDBMS grant/revole, or security markings on documents. We will discuss what the new research agenda should be to impact the masses of systems.

The database and document worlds have traditionally had different approaches to security. Databases provide access controls on structured data, while document security interrogates the outgoing information, based on document markings and actual contents. For the emerging world in which many documents are generated from structured data (and vice versa), the separation can cause failure, implementation-dependence, inconsistency, and wasted effort. After comparing approaches and mechanisms in the two areas, we identify issues in security administration and implementation in military and medical applications. We then present elements of a unifying model.

Data security issues today go far beyond the traditional questions of grant/revoke in an RDBMS. We will discuss what the new research agenda should be.

Enterprise databases are comprised of multiple local databases that exchange information. The component databases will rarely have the same native form, so one must map between the supplier’s native interface and the consumer’s. Using a SQL view to define this map is convenient and powerful, because it provides not just an evaluation mechanism, but also query, and (to some degree) update and trigger capabilities. However, SQL views do not map the critical metadata (e.g., security, source attribution, and quality information) between supplier and consumer. We present motivation, theory, and some pragmatics for creating an administrator’s assistant. We propose a framework into which one would put definitions and translators for individual metadata types. The underlying theory supports consistent (but not complete) inference services, to add value and to get maximal value from the currently available knowledge. We also discuss why support for collaboration and negotiation are essential such administrative environments, and sketch an initial approach.

Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the “a-priori” trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called “query flocks,” is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.

Conventional database optimizers take full advantage of associativity and commutativity properties of join to implement efficient and powerful optimizations on select/project/join queries.However, only limited optimization is performed on other binary operators.In this article, we present the theory and algorithms needed to generate alternative evaluation orders for the optimization of queries containing outerjoins.Our results include both a complete set of transformation rules, suitable for new-generation, transformation-based optimizers, and a bottom-up join enumeration algorithm compatible with those used by traditional optimizers.

We describe the tools and theory of a comprehensive system for database design, and show how they work together to support multiple conceptual and logical design processes. The Database Design and Evaluation Workbench (DDEW) system uses a rigorous, information-content-preserving approach to schema transformation, but combines it with heuristics, guess work, and user interactions. The main contribution lies in illustrating how theory was adapted to a practical system, and how the consistency and power of a design system can be increased by use of theory. First, we explain why a design system needs multiple data models, and how implementation over a unified underlying model reduces redundancy and inconsistency. Second, we present a core set of small but fundamental algorithms that reaarange a schema without changing its information content. From these reusable components, we easily built larger tools and transformations that were still formally justified. Third, we describe heuristic tools that attempt to improve a schema, often by adding missing information. In these tools, unreliable techniques such as normalization and relationship inference are bolstered by system-guided user interactions to remove errors. We present a rigorous criterion for identifying unnecessary relationships, and discuss an interactive view integrator. Last, we examine the relevance of database theory to building these practically motivated tools and contrast the paradigms of system builders with those of theoreticians.

Large organizations need to exchange information among many separately developed systems. In order for this exchange to be useful, the individual systems must agree on the meaning of their exchanged data. That is, the organization must ensure semantic interoperability . This paper provides a theory of semantic values as a unit of exchange that facilitates semantic interoperability betweeen heterogeneous information systems. We show how semantic values can either be stored explicitly or be defined by environments . A system architecture is presented that allows autonomous components to share semantic values. The key component in this architecture is called the context mediator , whose job is to identify and construct the semantic values being sent, to determine when the exchange is meaningful, and to convert the semantic values to the form required by the receiver. Our theory is then applied to the relational model. We provide an interpretation of standard SQL queries in which context conversions and manipulations are transparent to the user. We also introduce an extension of SQL, called Context-SQL (C-SQL), in which the context of a semantic value can be explicitly accessed and updated. Finally, we describe the implementation of a prototype context mediator for a relational C-SQL system.

The authors provide a nearly complete theory for reordering join/outerjoin queries. The theory is used to describe modular extensions that strengthen a conventional optimizer to handle nearly all select/project/join/outerjoin queries. Unlike previous work, these results are not limited to queries possessing a nice structure, or queries that are nicely represented in relational calculus. The theoretical results concern query simplification and reassociation using a generalized outerjoin.>

No abstract available.

The logic of many query optimizers corresponds to searching a graph that contains all alternative intermediate results considered by the optimizer. We consider the problem, “Given a query Q, determine the cost of a best strategy that uses intermediate result v to compute Q, assuming that v is available at no cost.” Our main result is an algorithm that mass-produces such cost information for all intermediates v considered by the query optimizer, in time linear in the size of the graph. To illustrate potential applications for the algorithm, we describe rules for identifying and eliminating suboptimal alternatives in multiple query optimization and demonstrate how the algorithm rapidly computes the necessary cost bounds. We also describe applications of the algorithm to speeding physical database design. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We determine when a join/outerjoin query can be expressed unambiguously as a query graph, without an explicit specification of the order of evaluation. To do so, we first characterize the set of expression trees that implement a given join/outerjoin query graph, and investigate the existence of transformations among the various trees. Our main theorem is that a join/outerjoin query is freely reorderable if the query graph derived from it falls within a particular class, every tree that “implements” such a graph evaluates to the same result.

A general framework is presented for rapidly analyzing tree networks to compute a measure of the centrality or eccentricity of all vertices in the tree. Several problems, which have been previously described in the literature, fit this framework. Some of these problems have no published solution better than performing a separate traversal for each vertex whose eccentricity is calculated. The method presented in this paper performs just two traversals and yields the eccentricities of all vertices in the tree. Natural sufficient conditions for the algorithm to work in linear time on any given problem are stated.

Part Hierarchies are a fundamental datatype in CAD applications. But intelligent and efficient processing requires major extensions to DBMS data models, query languages, and processing algorithms. We explore formulations and execution algorithms for path-traversal queries. Hierarchy semantics are then exploited for spatial data and to intelligently choose an appropriate detail level for query output.

Many capabilities that are needed for recursive applications in engineering and project management are not well supported by the usual formulations of recursion. We identify a class of recursions called “traversal recursions” (which model traversals of a directed graph) that have two important properties they can supply the necessary capabilities and efficient processing algorithms have been defined for them. First we present a taxonomy of traversal recursions based on properties of the recursion on graph structure and on unusual types of metadata. This taxonomy is exploited to identify solvable recursions and to select an execution algorithm. We show how graph traversal can sometimes outperform the more general iteration algorithm. Finally we show how a conventional query optimizer architecture can be extended to handle recursive queries and views.

We describe an optimizer for relational queries to databases stored as flat files and Codasyl networks. We include sophisticated manipulations on a broad range of direct access structures (DAS's). To achieve this with minimum additional code, we allow operations like sort, scan, and join to apply to DAS's, and categorize indexes and other DAS's in terms of the operations which can be performed on them. Our storage model, based on indivisible units of access and a small set of associated physical operators, provides a uniform interface to both relational and Codasyl storage mechanisms. The optimizer derives a sequence of internal data structures at successively more detailed levels. For a given query, a graph representing an overview of alternative joins is constructed, and then used to derive a physical graph which considers the physical attributes (location and sort order) of the data objects involved. Using cost predictions and other heuristics, the optimizer prunes the physical graph to produce a final access strategy tree. This layered approach and reliance on primitive operators make explicit (and permit changes to) the universe of possible strategies for the query at hand, and ease extension of the optimizer to new storage structures.

We consider discrete optimization problems in which the only exploitable feature of the objective function is a limited form of decomposability. “Nonoverlapping comparison algorithms” are defined as a model of procedures which decompose the problem and apply Bellman’s principle of optimality. Nonserial dynamic programming (DP), a simple elimination procedure, is shown to be optimal among all nonoverlapping comparison algorithms, including nondeterministic algorithms. These results can give an exponential lower bound on the shortest admissible proof that a solution is optimal. Furthermore, if part of the search space is ruled out, a subset of the comparisons made by DP optimally searches the remainder. We suggest that the running time of DP is a useful measure of the “interaction complexity” of a problem, and that because of its simplicity DP is of practical as well as theoretical interest.

Abstract Formulas for series and parallel reductions are obtained for difficult measures of network reliability. Examples considered include “traffic to center,” “total traffic carried,” “minimum cut,” and “all demanding vertices communicate.” We find general properties of “distribution‐preserving” and “average‐preserving” replacements, and present several examples. For systems analyzed by Monte‐Carlo sampling, we find that the estimator variance is reduced by the replacement.

We show that nonserial dynamic programming is optimal among one class of algorithms for an important class of discrete optimization problems. We consider discrete, multivariate, optimization problems in which the objective function is given as a sum of terms. Each term is a function of only a subset of the variables. We first consider a class of optimization algorithms which eliminate suboptimal solutions by comparing the objective function on “comparable” partial solutions. A large, natural subclass of comparison algorithms in which the subproblems considered are either nested or nonadjacent (i.e., noninteracting) is then defined. It is shown that a variable-elimination procedure, nonserial dynamic programming, is optimal in an extremely strong sense among all algorithms in the subclass. The results' strong implications for choosing deterministic, adaptive, and nondeterministic algorithms for the optimization problem, for defining a complexity measure for a pattern of interactions, and for describing general classes of decomposition procedures are discussed. Several possible extensions and unsolved problems are mentioned.

Abstract All known methods for calculating the connection probability for two vertices of an unreliable network take time exponential in the size of the network. A method is presented for reducing network size by transforming three‐terminal subnetworks into Y‐shaped networks, thus reducing terminal degrees and possibly creating series combinations which can be reduced to a single edge. Previously defined transformations were approximate, restricted to triangles, and required perfect terminals. The transformations given here are exact, apply to any three‐terminal subnetwork with perfect terminals, and permit the inclusion of unreliable terminals which are incident to one external edge. In addition, transformations for reducing certain networks with directed edges, and transformations for eliminating positive failure correlations are discussed.

We provide an $O(| V | + | E |)$ algorithm which, given a graph G, finds a smallest set of edges which, when added to G, produces a graph with no cutpoints.

Abstract A bit manipulation method is given for finding shortest distances from an origin in an unweighted graph, or alternatively, for finding connected components. The basic approach is similar to some component algorithms already in the literature but an easy implementation is given that overcomes the problem which prevents the others from being efficient–namely, the problem of identifying the ones in a sparse bit string without checking all the bits. The algorithm would be most effective for moderate sized graphs (about 20–100 nodes). Computational results are given.