We present a novel linear-time acyclic join algorithm, TreeTracker Join ( TTJ ). The algorithm can be understood as the pipelined binary hash join with a simple twist: upon a hash lookup failure, TTJ resets execution to the binding of the tuple causing the failure, and removes the offending tuple from its relation. Compared to the best known linear-time acyclic join algorithm, Yannakakis’s algorithm, TTJ shares the same asymptotic complexity while imposing lower overhead. Further, we prove that when measuring query performance by counting the number of hash probes, TTJ will match or outperform binary hash join on the same plan. This property holds independently of the plan and independently of acyclicity. We are able to extend our theoretical results to cyclic queries by introducing a new hypergraph decomposition method called tree convolution. Tree convolution iteratively identifies and contracts acyclic subgraphs of the query hypergraph. The method avoids redundant calculations associated with tree decomposition and may be of independent interest. Empirical results on TPC-H, the Join Order Benchmark, and the Star Schema Benchmark demonstrate favorable results.

This paper introduces an indexing method for searching diverse data types that is easily parallelizable for use with large data sets. This method, the Adaptive Projection Forest (APF) is a partition-based metric-space indexing method, which provides generic retrieval solutions for data sets for which similarity is defined by a metric-distance function. The APF is uniquely suited to alleviate problems typically encountered in metric-space indexing because it adaptively incorporates exclusion, a method that removes data near a partition boundary and creates multiple trees for use in parallel computing. The use of exclusion allows the index to be more effective when data falls near partition boundaries, where traditional pruning is not always possible. The APF's use of exclusion also allows it to have greater success in parallel environments, meaning that the APF algorithm can be more effectively used on large data sets with diverse data types. In the APF index, the proportion of excluded data is adjusted dynamically at each index node by locally determining the dimension, k, of the projection of the metric space onto the real numbers. The algorithm, which provides asymptotic algorithmic guarantees for nearest neighbor search, is presented along with a parallel implementation of the APF. Across a suite of real-world and synthetic benchmarks the APF demonstrates favorable empirical results, measured in number of calculations, when compared with the emVP, MVP, and SA indexes. Experiments also reveal that number of calculations can be minimized when a critical parameter, the width of the exclusion region, is set much smaller than the value suggested by asymptotic algorithmic analysis.

Automatic schema matching algorithms are typically only concerned with finding attribute correspondences. However, real world data integration problems often require matchings whose arguments span all three types of elements in relational databases: relation, attribute and data value. This paper introduces the definitions and semantics of three additional correspondence types concerning both schema and data values. These correspondences cover the higher-order mappings identified in a seminal paper by Krishnamurthy, Litwin, and Kent. It is shown that these correspondences can be automatically translated to tuple generating dependencies (tgds), and thus this research is compatible with data integration applications that leverage tgds.

BACKGROUND: Drug discovery, disease detection, and personalized medicine are fast-growing areas of genomic research. With the advancement of next-generation sequencing techniques, researchers can obtain an abundance of data for many different biological assays in a short period of time. When this data is error-free, the result is a high-quality base-pair resolution picture of the genome. However, when the data is lossy the heuristic algorithms currently used when aligning next-generation sequences causes the corresponding accuracy to drop. RESULTS: This paper describes a program, ADaM (APF DNA Mapper) which significantly increases final alignment accuracy. ADaM works by first using an existing program to align "easy" sequences, and then using an algorithm with accuracy guarantees (the APF) to align the remaining sequences. The final result is a technique that increases the mapping accuracy from only 60% to over 90% for harder-to-align sequences.

Selection finding, and its most common form median finding, are used as a measure of central tendency for problems in biology, databases, and graphics. These problems often require selection finding as a subcomponent where it can be called many times, and as such speed is important. The Map/Reduce framework has been shown to be an important tool for creating scalable applications. There are a number of valid implementations of the selection algorithms inside of a Map/Reduce framework, certain of which are compared in this paper. However, as the volume of data increases, subtle theoretical algorithmic implementation differences can lead to significant differences in practical application. Therefore, an efficient and scalable selection finding method has the potential to provide general benefit to a number of applications. This paper compares algorithms that have been redesigned or created for the Map/Reduce framework for the purpose of selection finding, or, finding the k-th ranked element in an unordered set. This paper takes the concepts used from two existing selection algorithms and translates them into a novel method using the Map/Reduce framework with two variations. Each approach uses a different methodology to reduce the total amount of workload needed for a selection. All the algorithms are compared together for scalability and efficiency in a computing cluster environment with up to 256 processing cores. The results show that the methods proposed in this paper outperform several common alternatives in identifying medians with Hadoop, including using sorting, Pig, and BinMedian methods. Our implementations are also available upon request.

A pair wise comparison of data objects is a requisite step in many data mining applications, but has quadratic complexity. In applications such as record linkage, blocking methods may be applied to reduce the cost. That is, the data is first partitioned into a set of blocks, and pair wise comparisons computed for pairs within each block. To date, blocking methods have required the blocking scheme be given, or the provision of training data enabling supervised learning algorithms to determine a blocking scheme. In either case, a domain expert is required. This paper develops an unsupervised method for learning a blocking scheme for tabular data sets. The method is divided into two phases. First, a weakly labeled training set is generated automatically in time linear in the number of records of the entire dataset. The second phase casts blocking key discovery as a Fisher feature selection problem. The approach is compared to a state-of-the-art supervised blocking key discovery algorithm on three real-world databases and achieves favorable results.

The rapid determination of nucleic acid sequences is increasing the number of sequences that are available. Inherent in a template or seed alignment is the culmination of structural and functional constraints that are selecting those mutations that are viable during the evolution of the RNA. While we might not understand these structural and functional, template-based alignment programs utilize the patterns of sequence conservation to encapsulate the characteristics of viable RNA sequences that are aligned properly. We have developed a program that utilizes the different dimensions of information in rCAD, a large RNA informatics resource, to establish a profile for each position in an alignment. The most significant include sequence identity and column composition in different phylogenetic taxa. We have compared our methods with a maximum of eight alternative alignment methods on different sets of 16S and 23S rRNA sequences with sequence percent identities ranging from 50% to 100%. The results showed that CRWAlign outperformed the other alignment methods in both speed and accuracy. A web-based alignment server is available at http://www.rna.ccbb.utexas.edu/SAE/2F/CRWAlign.

Mapping relational databases to RDF is a fundamental problem for the development of the Semantic Web. We present a solution, inspired by draft methods defined by the W3C where relational databases are directly mapped to RDF and OWL. Given a relational database schema and its integrity constraints, this direct mapping produces an OWL ontology, which, provides the basis for generating RDF instances. The semantics of this mapping is defined using Datalog. Two fundamental properties are information preservation and query preservation. We prove that our mapping satisfies both conditions, even for relational databases that contain null values. We also consider two desirable properties: monotonicity and semantics preservation. We prove that our mapping is monotone and also prove that no monotone mapping, including ours, is semantic preserving. We realize that monotonicity is an obstacle for semantic preservation and thus present a non-monotone direct mapping that is semantics preserving.

We present a fast pairwise RNA sequence alignment method using structural information, named R-PASS (RNA Pairwise Alignment of Structure and Sequence), which shows good accuracy on sequences with low sequence identity and significantly faster than alternative methods. The method begins by representing RNA secondary structure as a set of structure motifs. The motifs from two RNAs are then used as input into a bipartite graph-matching algorithm, which determines the structure matches. The matches are then used as constraints in a constrained dynamic programming sequence alignment procedure. The R-PASS method has an O(nm) complexity. We compare our method with two other structure-based alignment methods, LARA and ExpaLoc, and with a sequence-based alignment method, MAFFT, across three benchmarks and obtain favorable results in accuracy and orders of magnitude faster in speed.

MOTIVATION: High-throughput protein identification experiments based on tandem mass spectrometry (MS/MS) often suffer from low sensitivity and low-confidence protein identifications. In a typical shotgun proteomics experiment, it is assumed that all proteins are equally likely to be present. However, there is often other evidence to suggest that a protein is present and confidence in individual protein identification can be updated accordingly. RESULTS: We develop a method that analyzes MS/MS experiments in the larger context of the biological processes active in a cell. Our method, MSNet, improves protein identification in shotgun proteomics experiments by considering information on functional associations from a gene functional network. MSNet substantially increases the number of proteins identified in the sample at a given error rate. We identify 8-29% more proteins than the original MS experiment when applied to yeast grown in different experimental conditions analyzed on different MS/MS instruments, and 37% more proteins in a human sample. We validate up to 94% of our identifications in yeast by presence in ground-truth reference sets. AVAILABILITY AND IMPLEMENTATION: Software and datasets are available at http://aug.csres.utexas.edu/msnet

MOTIVATION: Tandem mass spectrometry (MS/MS) offers fast and reliable characterization of complex protein mixtures, but suffers from low sensitivity in protein identification. In a typical shotgun proteomics experiment, it is assumed that all proteins are equally likely to be present. However, there is often other information available, e.g. the probability of a protein's presence is likely to correlate with its mRNA concentration. RESULTS: We develop a Bayesian score that estimates the posterior probability of a protein's presence in the sample given its identification in an MS/MS experiment and its mRNA concentration measured under similar experimental conditions. Our method, MSpresso, substantially increases the number of proteins identified in an MS/MS experiment at the same error rate, e.g. in yeast, MSpresso increases the number of proteins identified by approximately 40%. We apply MSpresso to data from different MS/MS instruments, experimental conditions and organisms (Escherichia coli, human), and predict 19-63% more proteins across the different datasets. MSpresso demonstrates that incorporating prior knowledge of protein presence into shotgun proteomics experiments can substantially improve protein identification scores. AVAILABILITY AND IMPLEMENTATION: Software is available upon request from the authors. Mass spectrometry datasets and supplementary information are available from (http://www.marcottelab.org/MSpresso/).

MOTIVATIONS: Biclustering is a clustering method that simultaneously clusters both the domain and range of a relation. A challenge in multiple sequence alignment (MSA) is that the alignment of sequences is often intended to reveal groups of conserved functional subsequences. Simultaneously, the grouping of the sequences can impact the alignment; precisely the kind of dual situation biclustering is intended to address. RESULTS: We define a representation of the MSA problem enabling the application of biclustering algorithms. We develop a computer program for local MSA, BlockMSA, that combines biclustering with divide-and-conquer. BlockMSA simultaneously finds groups of similar sequences and locally aligns subsequences within them. Further alignment is accomplished by dividing both the set of sequences and their contents. The net result is both a multiple sequence alignment and a hierarchical clustering of the sequences. BlockMSA was tested on the subsets of the BRAliBase 2.1 benchmark suite that display high variability and on an extension to that suite to larger problem sizes. Also, alignments were evaluated of two large datasets of current biological interest, T box sequences and Group IC1 Introns. The results were compared with alignments computed by ClustalW, MAFFT, MUCLE and PROBCONS alignment programs using Sum of Pairs (SPS) and Consensus Count. Results for the benchmark suite are sensitive to problem size. On problems of 15 or greater sequences, BlockMSA is consistently the best. On none of the problems in the test suite are there appreciable differences in scores among BlockMSA, MAFFT and PROBCONS. On the T box sequences, BlockMSA does the most faithful job of reproducing known annotations. MAFFT and PROBCONS do not. On the Intron sequences, BlockMSA, MAFFT and MUSCLE are comparable at identifying conserved regions. AVAILABILITY: BlockMSA is implemented in Java. Source code and supplementary datasets are available at http://aug.csres.utexas.edu/msa/

BACKGROUND: Cis-acting transcriptional regulatory elements in mammalian genomes typically contain specific combinations of binding sites for various transcription factors. Although some cis-regulatory elements have been well studied, the combinations of transcription factors that regulate normal expression levels for the vast majority of the 20,000 genes in the human genome are unknown. We hypothesized that it should be possible to discover transcription factor combinations that regulate gene expression in concert by identifying over-represented combinations of sequence motifs that occur together in the genome. In order to detect combinations of transcription factor binding motifs, we developed a data mining approach based on the use of association rules, which are typically used in market basket analysis. We scored each segment of the genome for the presence or absence of each of 83 transcription factor binding motifs, then used association rule mining algorithms to mine this dataset, thus identifying frequently occurring pairs of distinct motifs within a segment. RESULTS: Support for most pairs of transcription factor binding motifs was highly correlated across different chromosomes although pair significance varied. Known true positive motif pairs showed higher association rule support, confidence, and significance than background. Our subsets of high-confidence, high-significance mined pairs of transcription factors showed enrichment for co-citation in PubMed abstracts relative to all pairs, and the predicted associations were often readily verifiable in the literature. CONCLUSION: Functional elements in the genome where transcription factors bind to regulate expression in a combinatorial manner are more likely to be predicted by identifying statistically and biologically significant combinations of transcription factor binding motifs than by simply scanning the genome for the occurrence of binding sites for a single transcription factor.

Managing data with distance-based indexing methods has the potential to provide scalability and integration with relational database management systems and the SQL programming model. We previously demonstrated the advantages of such an approach for nucleotide sequences using Hamming distance (mismatch). However, the larger alphabet size of peptide sequences increases the dimensionality of the problem, making algorithmic results more challenging. The development of a metric-PAM substitution matrix enables metric-distance based indexing for peptide sequences. The performance of distance-based indexing for homologous protein retrieval entails trade-off among accuracy, scalability and computational cost. We investigate the application of the multi-vantage point (MVP) tree algorithm to index peptide k-mers based on global mPAM alignment. We show that k-mer retrieval can still maintain accuracy when k is at least as large as 6 that creates a domain of over 60 million key values and enables scalability sufficient for effective performance on large disk-resident sequence databases

MOTIVATION: We reformulate the problem of comparing mass-spectra by mapping spectra to a vector space model. Our search method leverages a metric space indexing algorithm to produce an initial candidate set, which can be followed by any fine ranking scheme. RESULTS: We consider three distance measures integrated into a multi-vantage point index structure. Of these, a semi-metric fuzzy-cosine distance using peptide precursor mass constraints performs the best. The index acts as a coarse, lossless filter with respect to the SEQUEST and ProFound scoring schemes, reducing the number of distance computations and returned candidates for fine filtering to about 0.5% and 0.02% of the database respectively. The fuzzy cosine distance term improves specificity over a peptide precursor mass filter, reducing the number of returned candidates by an order of magnitude. Run time measurements suggest proportional speedups in overall search times. Using an implementation of ProFound's Bayesian score as an example of a fine filter on a test set of Escherichia coli protein fragmentation spectra, the top results of our sample system are consistent with that of SEQUEST.

MOTIVATION: We address the question of whether there exists an effective evolutionary model of amino-acid substitution that forms a metric-distance function. There is always a trade-off between speed and sensitivity among competing computational methods of determining sequence homology. A metric model of evolution is a prerequisite for the development of an entire class of fast sequence analysis algorithms that are both scalable, O(log n) and sensitive. RESULTS: We have reworked the mathematics of the point accepted mutation model (PAM) by calculating the expected time between accepted mutations in lieu of calculating log-odds probabilities. The resulting substitution matrix (mPAM) forms a metric. We validate the application of the mPAM evolutionary model for sequence homology by executing sequence queries from a controlled yeast protein homology search benchmark. We compare the accuracy of the results of mPAM and PAM similarity matrices as well as three prior metric models. The experiment shows that mPAM significantly outperforms the other three metrics and sufficiently approaches the sensitivity of PAM250 to make it applicable to the management of protein sequence databases.

Weijia Xu, Daniel P. Miranke; A metric model of amino acid substitution, Bioinformatics, Volume 20, Issue 18, 12 December 2004, Pages 3716, https://doi.org

Hierarchical metric-space clustering methods have been commonly used to organize proteomes into taxonomies. Consequently, it is often anticipated that hierarchical clustering can be leveraged as a basis for scalable database index structures capable of managing the hyper-exponential growth of sequence data. M-tree is one such data structure specialized for the management of large data sets on disk. We explore the application of M-trees to the storage and retrieval of peptide sequence data. Exploiting a technique first suggested by Myers (1994), we organize the database as records of fixed length substrings. Empirical results are promising. However, metric-space indexes are subject to "the curse of dimensionality" and the ultimate performance of an index is sensitive to the quality of the initial construction of the index. We introduce new hierarchical bulk-load algorithm that alternates between top-down and bottom-up clustering to initialize the index. Using the Yeast Proteomes, the bi-directional bulk load produces a more effective index than the existing M-tree initialization algorithms.

We examine the organizational impact on phylogenetic databases of the increasing sophistication in the need and use of phylogenetic data. A primary issue is the use of the unnormalized representation of phylogenies in Newick format as a primitive data type in existing phylogenetic databases. In particular we identify and enumerate a list of potential applications of such databases and queries (use-cases) that biologists may wish to see integrated into a phylogenetic database management system. We show there are many queries that would best be supported by a normalized data model where phylogenies are stored as lists of edges. Since many of the queries require transitive traversals of the phylogenies we demonstrate, constructively, that complex phylogenetic queries can be conveniently constructed as Datalog programs. We address concerns with respect to the cost and performance of the normalized representation by developing and empirically evaluating a feasibility prototype.

MoBIoS is a specialized database management system whose storage manager is based on metricspace indexing, and whose query language entails biological data types. When relational database management systems are used to support biological data, important data types are relegated to blob and unstructured text fields. Thus, even simple, but critical queries are executed by sequentially dumping the data to utilities outside the database. MoBIoS provides O(log n) physical access to diverse biological data types as well as uniform logical and syntactic access. Consequently, MoBIoS provides a framework where complex bioinformatic algorithms may be effectively expressed and executed as concise declarative SQL-like (Structured Query Language) queries.

Federated systems integrating data from multiple sources must cope with semantic heterogeneity by reasoning over both the data and meta-data of their sources. SchemaSQL is one of a number of related higher-order languages, which have been proposed for succinctly expressing integrated views over heterogeneous sources. We define a method for compiling SchemaSQL into standard SQL. We show that the output of the compilation algorithm is of size O(m+p) where m is the size of the catalogs and p the size of input queries. The resulting code may be executed by existing conventional SQL query engines without modification. We extend our basic compilation method by including type driven optimizations which, empirical evaluation shows, yield an effective execution by native query engines. Prior efforts do not provide feasible guarantees on the size of the compiled programs or require the development of new query engines encompassing higher-order query operators.

We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload, we can construct an indexing scheme, which is a collection of fixed-sized subsets of the data. We identify two measures of efficiency for an indexing scheme on a workload: storage redundancy, r (how many times each item in the data set is stored), and access overhead, A (how many times more blocks than necessary does a query retrieve).For many interesting families of workloads, there exists a trade-off between storage redundancy and access overhead. Given a desired access overhead A , there is a minimum redundancy that any indexing scheme must exhibit. We prove a lower-bound theorem for deriving the minimum redundancy. By applying this theorem, we show interesting upper and lower bounds and trade-offs between A and r in the case of multidimensional range queries and set queries.

We present the architecture and a performance assessment of an extensible query optimizer written in Venus. Venus is a general-purpose active-database rule language embedded in C++. Following the developments in extensible database query optimizers, first in rule-based form, followed by optimizers written as object-oriented programs, the Venus-based optimizer avails to the advantages of both. Venus' modular structure allows us to go a step further and provide extensibility in search by defining parameterized search components in a declarative form that has the additional effect of integrating heuristic and cost-based optimization. We compare optimizers developed with Volcano, OPT++ and Venus. Venus' optimizing compiler yields code whose performance is comparable with Volcano and OPT++ on smaller queries. The ability to introduce additional pruning heuristics yields better scalability on larger queries. Evaluation of the system using quantitative software metrics supports a claim that the Venus-based optimizer is more easily maintained and extended than are its predecessors.

Indexing schemes were proposed by Hellerstein, Koutsoupias and Papadimitriou [7] to model data indexing on external memory. Using indexing schemes, the complexity of indexing is quantified by two parameters: storage redundancy and access overhead. There is a tradeoff between these two parameters, in the sense that for some problems it is not possible for both of these to be low. In this paper we derive a lower-bounds theorem for arbitrary indexing schemes. We apply our theorem to the particular problem of d-dimensional range queries. We first resolve the open problem of [7] for a tight lower bound for 2-dimensional range queries and extend our lower bound to d-dimensional range queries. We then show, how, the construction in our lower-bounds proof may be exploited to derive indexing schemes for d-dimensional range queries, whose asymptotic complexity matches our lower bounds. 1

This paper presents an algorithm for implementing rule filtering in active and trigger enabled databases. The algorithm generates one or more decision trees that determine what rules or triggers might be enabled by an individual database element, reducing the number of rules or triggers that must be evaluated. The algorithm operates by symbolically representing the space of database elements and subdividing the space based on rule predicates. Regions of the state space represent particular combinations of enabled rules. Decision trees are then generated based on the subdivided state space. The trees have the important property that no individual test is repeated. The ordered binary decision diagram (BDD) data structure is used to represent and manipulate the state space. 1. Introduction Modern database systems increasingly support active behavior through rules. This support ranges from simple database triggers to complete active database functionality. Rules typically follow the even...

Special support for quickly finding the first-few answers of a query is atready appearing in commercial database systems.This support is useful in active databases,when dealing with potentially unmanageable query results, and as a declarative akernativeto navigational techniques.In this paper, wediscuss query processing techniques for first-answer queries.We provide a method for predicting the cost of a first-answer query plan under an execution model that attempts to reduce wasted effort in join pipelining.We define new statistics necessary for accurate cost prediction, and discuss techniques for obtaining the statistics through traditional statistical measures (e.g.selectivity) and semantic data properties commonly specified through modem 00DB and relatiorud schemas.The proposed techniques also apply to all-answer query processing when optimizing for fast delivery of the initiat query results.

Article A case study of Venus and a declarative basis for rule modules Share on Authors: Lane B. Warshaw Department of Computer Sciences and Applied Research Laboratories, The University of Texas at Austin Department of Computer Sciences and Applied Research Laboratories, The University of Texas at AustinView Profile , Daniel P. Miranker Department of Computer Sciences and Applied Research Laboratories, The University of Texas at Austin Department of Computer Sciences and Applied Research Laboratories, The University of Texas at AustinView Profile Authors Info & Claims CIKM '96: Proceedings of the fifth international conference on Information and knowledge managementNovember 1996 Pages 317–325https://doi.org/10.1145/238355.238569Published:12 November 1996 4citation284DownloadsMetricsTotal Citations4Total Downloads284Last 12 Months0Last 6 weeks0 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 SiteGet Access

Decomposition abstraction is the process of organizing and specifying decomposition strategies for the exploitation of parallelism available in an application. In this paper we develop and evaluate declarative primitives for rule-based programs that expand opportunities for parallel execution. These primitives make explicit, implicit relations among the data and similarly among the rules. The semantics of the primitives are presented in a general object-based framework such that they may be applied to most rule-based programming languages. We show how the additional information provided by the decomposition primitives can be incorporated into a semantic-based dependency analysis technique. The resulting analysis reveals parallelism at compile time that is very difficult, if not impossible, to discover by traditional syntactic analysis techniques. Simulation results demonstrate scalable and broadly available parallelism.

Article On isolation, concurrency, and the Venus rule language Share on Authors: Stephen Correl Department of Computer Sciences and the Applied Research Laboratories, University of Texas at Austin, Austin, Texas Department of Computer Sciences and the Applied Research Laboratories, University of Texas at Austin, Austin, TexasView Profile , Daniel P. Miranker Department of Computer Sciences and the Applied Research Laboratories, University of Texas at Austin, Austin, Texas Department of Computer Sciences and the Applied Research Laboratories, University of Texas at Austin, Austin, TexasView Profile Authors Info & Claims CIKM '95: Proceedings of the fourth international conference on Information and knowledge managementDecember 1995 Pages 281–289https://doi.org/10.1145/221270.221591Published:02 December 1995 5citation213DownloadsMetricsTotal Citations5Total Downloads213Last 12 Months2Last 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 AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Presents performance results for a production system environment, CLIPS++, that demonstrate the advantage of selectively building and applying simple index structures. We contrast this to the extensive body of work on matching, which, over the years, has evolved increasingly complex compositions of index structures which are then uniformly applied to all the data types and rules in a production system program. Over a set of benchmark programs, the fastest executions are always attained by carefully selecting a good mixture of indexes rather than universal use of a single index.

We propose a new approach for the parallel execution of production system programs. This approach embodies methods of decomposition abstraction using declarative mechanisms. Application semantics can then be exploited to achieve a much higher degree of concurrency. We present the underlying object-based framework of production systems and discuss the ensuing semantic-based dependency analysis technique. In particular, we define a new notion of functional dependency to characterize associative relationships among data objects, which can be used to determine concurrently executable rules.

We describe a purely declarative method for introducing modularity into forward-chaining, rule-based languages and its embodiment in the Venus rule language. The method is enforced by the syntax of the language and includes the ability to parameterize the rule groups. Drawing from two of three Venus applications developed to date, we illustrate how this form of modularity contributes directly to the resolution of certain software engineering problems associated with rule languages.>

Integrated rule and database systems are quickly moving from the research laboratory into commercial systems. However, the current generation of prototypes are designed to work with small rule sets involving limited inferencing. The problem of supporting large complex rule programs within database management systems still presents significant challenges. The basis for many of these challenges is providing support for rule activation. Rule activation is defined as the process of determining which rules are satisfied and what data satisfies them. In this paper we present performance results for the DATEX database rule system and its novel indexing technique for supporting rule activation. Our approach assumes that both the rule program and the database must be optimized synergistically. However, as an experimental result we have determined that DATEX requires very few changes to a standard DBMS environment, and we argue that these changes are reasonable for the problems being solved. Based on the performance of DATEX we believe we have demonstrated a satisfactory solution to the rule activation problem for complex rule programs operating within a database system.

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

A panel session in which issues relating to the effects of advances in faster and more parallel hardware, production system match (PSM) algorithms, and application domains for match on PSM as a research area is presented. It is argued that there is no such thing as the optimal matching algorithm, even for the well-defined task of production-system match and that broadening the scope of the matching task beyond forward-chaining production system presents a new set of problems to the artificial intelligence community. Also, even with all the speedups, large production system runs take hours to complete, and a major portion of this time is attributable to PSM. Match technology remains a large and centralized component of system performance. To that extent, providing sufficient speedups in the match in these systems may still be useful. Performance issues of production system execution are discussed, and a common set of benchmarks and test cases is called for. It is argued that parallel algorithms for match, resolve, and fire are all interesting and difficult problems to solve, and should be the focus of research by the PSM community.>

Most rule execution environments, having been derived from LISP, inference on internally defined data types and come packaged with stand-alone development environments. Data derived from outside these systems must be reformatted before they can be evaluated. This mismatch leads to a duplicate representation of data, which, in turn, introduces both performance and semantic problems. A description is given of a C++ embeddable rule system (CERS) which avoid this mismatch. CERS is a compiled, forward-chaining rule system that inferences directly on arbitrary C++ objects. CERS can be viewed as an extension of C++, where object methods can be defined either procedurally or declaratively.>

An ensemble of techniques that compile OPS5 production system programs to executable machine code is described and an increase in the execution speed of production system programs by two orders of magnitude over the commonly used list processing (LISP)-based OPS5 system is demonstrated. The computer is based on the TREAT incremental match algorithm. A version of the TREAT algorithm, formulated in relational algebra, is presented. The compiler employs optimization techniques derived from relational database system. The combination of the TREAT algorithm and the compiling techniques reduces the proportion of time spent in the match phase below the 'greater than 90%' figure often cited by developers of other production system environments.>

Executing a large number of transactions on a large database within a short amount of time is computationally stressful. Main-memory resident production systems have been made computationally feasible by the development of incremental match algorithms that exploit the temporal redundancy of the database by saving results computed in prior cycles. Unfortunately, the worst-case space complexity of these match algorithms is exponential, and space management becomes a dominant issue. A lazy incremental match algorithm with linear worst-case space complexity is presented. Initial empirical results show that Lazy Match can prune 60% of the search for rule instantiations. It is felt that these results provide the first reasonable algorithmic basis upon which one can develop an active database system.>

DADO is a parallel, tree-structured machine designed to provide significant performance improvements in the execution of large expert systems implemented in production system form. A full-scale version of the DADO machine would comprise a large set of processing elements (PEs) (on the order of thousands), each containing its own processor, a small amount (20K bytes, in the current prototype design) of local random access memory, and a specialized I/O switch. The PEs are interconnected to form a complete binary tree. This paper describes the application domain of the DADO machine and the rationale for its design. Parallel algorithms for production system execution are briefly described. We then focus on the machine architecture and detail the hardware design of a moderately large prototype comprising 1023 microprocessors currently operational at Columbia University. We conclude with very encouraging performance statistics recently calculated from an analysis of simulations of the system.