We present EventSummarizer - a tool for extracting comprehensive summaries from large event sequences. EventSummarizer takes as input a sequence with events of different types that occur during an observation period, and creates a partitioning of this time period into contiguous non-overlapping intervals such that each interval can be described by a simple model. Within each interval local associations between events of different types are reported. EventSummarizer runs on top of any Relational DataBase Management System (RDBMS), on tables with a timestamp attribute. Our system is parameter free and has a visual interface that provides the user with a global view of the input sequence via the segmentation of the timeline. The easy-to-use interface provides the user with the option to further examine the activity and associations of event types within each segment.

Event sequences capture system and user activity over time. Prior research on sequence mining has mostly focused on discovering local patterns appearing in a sequence. While interesting, these patterns do not give a comprehensive summary of the entire event sequence. Moreover, the number of patterns discovered can be large. In this article, we take an alternative approach and build short summaries that describe an entire sequence, and discover local dependencies between event types. We formally define the summarization problem as an optimization problem that balances shortness of the summary with accuracy of the data description. We show that this problem can be solved optimally in polynomial time by using a combination of two dynamic-programming algorithms. We also explore more efficient greedy alternatives and demonstrate that they work well on large datasets. Experiments on both synthetic and real datasets illustrate that our algorithms are efficient and produce high-quality results, and reveal interesting local structures in the data.

Event sequences capture system and user activity over time. Prior research on sequence mining has mostly focused on discovering local patterns. Though interesting, these patterns reveal local associations and fail to give a comprehensive summary of the entire event sequence. Moreover, the number of patterns discovered can be large. In this paper, we take an alternative approach and build short summaries that describe the entire sequence, while revealing local associations among events.

Numerous widely publicized cases of theft and misuse of private information underscore the need for audit technology to identify the sources of unauthorized disclosure. We present an auditing methodology that ranks potential disclosure sources according to their proximity to the leaked records. Given a sensitive table that contains the disclosed data, our methodology prioritizes by relevance the past queries to the database that could have potentially been used to produce the sensitive table. We provide three conceptually different measures of proximity between the sensitive table and a query result. One measure is inspired by information retrieval in text processing, another is based on statistical record linkage, and the third computes the derivation probability of the sensitive table in a tree-based generative model. We also analyze the characteristics of the three measures and the corresponding ranking algorithms.

The Sarbanes-Oxley Act instituted a series of corporate reforms to improve the accuracy and reliability of financial reporting. Sections 302 and 404 of the Act require SEC-reporting companies to implement internal controls over financial reporting, periodically assess the effectiveness of these internal controls, and certify the accuracy of their financial statements. We suggest that database technology can play an important role in assisting compliance with the internal control provisions of the Act. The core components of our solution include: (i) modeling of required workflows, (ii) active enforcement of control activities, (iii) auditing of actual workflows to verify compliance with internal controls, and (iv) discovery-driven OLAP to identify irregularities in financial data. We illustrate how the features of our solution fulfill Sarbanes-Oxley requirements using several real-life scenarios. In the process, we identify opportunities for new database research.

Databases are at the core of successful businesses. Due to the voluminous stores of personal data being held by companies today, preserving privacy has become a crucial requirement for operating a business. This paper proposes how current relational database management systems can be transformed into their privacy-preserving equivalents. Specifically, we present language constructs and implementation design for fine-grained access control to achieve this goal.

Encryption is a well established technology for protecting sensitive data. However, once encrypted, data can no longer be easily queried aside from exact matches. We present an order-preserving encryption scheme for numeric data that allows any comparison operation to be directly applied on encrypted data. Query results produced are sound (no false hits) and complete (no false drops). Our scheme handles updates gracefully and new values can be added without requiring changes in the encryption of other values. It allows standard databse indexes to be built over encrypted tables and can easily be integrated with existing database systems. The proposed scheme has been designed to be deployed in application environments in which the intruder can get access to the encrypted database, but does not have prior domain information such as the distribution of values and annot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.

Platform for privacy preferences (P3P) is the most significant effort currently underway to enable Web users to gain control over their private information. P3P provides mechanisms for Web site owners to express their privacy policies in a standard format that a user can programmatically check against her privacy preferences to decide whether to release her data to the Web site. We discuss architectural alternatives for implementing P3P and present a server-centric implementation that reuses database querying technology, as opposed to the prevailing client-centric implementations based on specialized engines. Not only does the proposed implementation have qualitative advantages, our experiments indicate that it performs significantly better than the sole public-domain client-centric implementation and that the latency introduced by preference matching is small enough for real-world deployments of P3P.

No abstract available.

The Platform for Privacy Preferences (P3P) is the most significant effort currently underway to enable web users to gain control over their private information. The designers of P3P simultaneously designed a preference language called APPEL to allow users to express their privacy preferences, thus enabling automatic matching of privacy preferences against P3P policies. Unfortunately subtle interactions between P3P and APPEL result in serious problems when using APPEL: Users can only directly specify what is unacceptable in a policy, not what is acceptable; simple preferences are hard to express; and writing APPEL preferences is error prone. We show that these problems follow from a fundamental design choice made by APPEL, and cannot be solved without completely redesigning the language. Therefore we explore alternatives to APPEL that can overcome these problems. In particular, we show that XPath serves quite nicely as a preference language and solves all the above problems. We identify the minimal subset of XPath that is needed, thus allowing matching programs to potentially use a smaller memory footprint. We also give an APPEL to XPath translator that shows that XPath is as expressive as APPEL.

This paper presents a query processing algorithm called DECAF for use in middleware object query systems that are based on the use of an object cache. The DECAF algorithm is designed to work correctly even in the presence of updates to the underlying databases that don't go through the object cache (i.e., even for autonomous data sources that can be updated through legacy applications that do not perform their updates through the middleware object layer). DECAF's query results are consistent with updates performed by such transactions; its results are also consistent with any deferred updates that are present in the object cache but not yet committed at the database server. The DECAF algorithm attempts to push down query predicates to the underlying DBMSs to take advantage of the query processing capabilities of these systems and to reduce the amount of data transferred from these systems to the object cache.

This paper describes the design and implementation of a query engine that provides extended SQL-based access to the data managed by an object-oriented database system. This query engine allows extended SQL queries to be embedded in C++ programs or issued interactively as from a command line interface. The language supported by the engine is the complete SQL-92 select statement plus object extensions for navigating along paths and embedded structures, querying nested sets, and invoking member functions. In addition, an object-oriented SQL view facility is provided. Using this view facility, one can define object-oriented views; one can also define views that flatten complex OODB schemas, allowing direct access by existing tools designed to provide remote access to relational databases. The view facility also supports the definition of views that include reference and set-valued columns based on other views, thus allowing entire "view schemas" to be created. This paper describes the SQL-92 query and view extensions and discusses a number of issues that arose on the way to the implementation that is currently running on top of the ObjectStore OODB system.

An access structure that accelerates the processing of generalized transitive closure queries is presented. For an acyclic graph, the access structure consists of source-destination pairs arranged in a topologically sorted order. For a cyclic graph, entries in the structure are approximately topologically sorted. The authors present a breadth-first algorithm for creating such a structure, show how it can be used to process queries, and describe incremental techniques for maintaining it.>

The design and the implementation of a rule database language (RDL) compiler is presented. In this design, the RDL/C language supports both declarative programming based on a production rule language and C-based procedural programming. The data model is relational. This implies that all rule programs can be solved without having to download data from the database management system (DBMS) into some working memory. The language supports domain variables which can appear in rules. These variables are monitored by the inference engine and included in the semantics of rule firing. A partial ordering among rules is available to the user. The RDL/C compiler translates RDL/C source code into C code with embedded structured query language (SQL) statements. Its implementation is compared to fully integrated deductive databases and to loosely coupled systems. It is shown how the rule-based paradigm for a database can be used as a framework for a general-purpose database application generator.>

Deductive databases provide a formal framework to study rule-based query languages that are extensions of first-order logic. However, deductive database languages and their current implementations do not seem appropriate for improving the development of real applications or even sample of them. Our goal is to make deductive database technology practical. The design and implementation of the RDL1 system, presented in this paper, constitute a step toward this goal. Our approach is based on the integration of a production rule language within a relational database system, the development of a rule-based programming environment and the support of system extensibility using Abstract Data Types. We discuss important practical experience gained during the implementation of the system. Also, comparisons with related work such as LDL, STARBURST and POSTGRES are given.

The authors present a clustering method for complex domains. The method is original in that tuples can be clustered using functions applied to complex domain values. Thus, tuples are organized according to a function result. Those functions most often applied to complex values and used in the restriction part of queries can be used as clustering predicates. Hence, they optimize the retrieval of tuples that would otherwise require processing the whole relation. In SABRINA, complex domain processing is made possible by a Lisp language processor designed as an integrated database management system processor. Clustering is determined by a set of predicates defining a recursive partitioning of the relation. These predicates are the Lisp functions, taken from the set of functions applicable to a given domain. The authors demonstrate that by using the same approach for a data manipulation language and a clustering strategy, few modifications of the DBMS program are required and the assertional power of the DBMS is upgraded while respecting performance considerations.>