Search

SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries. Categories and Subject Descriptors: H.2.3 [Database Management]: Languages--Query languages General Terms: Algorithms, Languages, Performance, Theory Additional Key Words and Phrases: Complexity, query language, RDF, semantic Web, SPARQL

Problem statement: Students completing introductory computing courses did not know how to program at the expected level. Seeking the underlying problem, we came to believe that students were focusing only on results and not connecting with the inner workings of their code. This left them poorly prepared to master increasingly complex problems. Approach: We hoped that by promoting memory tracing as a core competence as early as possible in introductory programming courses we would hone the understanding and skills of our students and improve their chances for succeeding in computer science. We emphasized a basic and manual approach to memory tracing--in the classroom, in conjunction with homework assignments and on exams--to help our students gain the ability to write good programs, test them and, should it become necessary, debug them. Results: Having received gratifying results from our approach in our own classes, we had moved to get the word out as quickly as possible to motivate other educators to implement it. We described how we derived benefit from memory tracing in the various contexts and we presented the details of our method for teaching students how to best use this technique. Conclusion/Recommendations: Training students early on to actively carry out a manual memory trace of programs (as opposed to relying on debuggers or print statements) will help them develop their coding skill and comfort, quite apart from any facility for finding and fixing errors. Although experienced programmers trace intuitively, beginning students do not; they need to be trained. Therefore we felt that tracing should be an explicit, emphasized component of the introductory courses. Key words: Memory tracing, tracing, introductory programming, novice programming, computer science education, INTRODUCTION Memory tracing is the process of recording the value changes of program variables. It has also been called desk checking or playing computer. This is distinct from hand-checking, doing [...]

This article describes an approach to program optimization based on transformations, where temporal logic is used to specify side conditions, and strategies are created which expand the repertoire of transformations and provide a suitable level of abstraction. We demonstrate the power of this approach by developing a set of optimizations using our transformation language and showing how the transformations can be converted into a form which makes it easier to apply them, while maintaining trust in the resulting optimizing steps. The approach is illustrated through a transformational case study where we apply several optimizations to a small program. Categories and Subject Descriptors: D.3.0 [Programming Languages]: General; D.1.4 [Programming Techniques]: Sequential Programming; D.3.4 [Programming Languages]: Processors--Optimization General Terms: Design, Languages, Verification Additional Key Words and Phrases: Optimizing compilers, program transformation, rewriting, temporal logic

We propose a sequent calculus derived from the [bar.[lambda]][mu][??]-calculus of Curien and Herbelin that is expressive enough to directly represent the fine details of program evaluation using typical abstract machines. Not only does the calculus easily encode the usual components of abstract machines such as environments and stacks, but it can also simulate the transition steps of the abstract machine with just a constant overhead. Technically this is achieved by ensuring that reduction in the calculus always happens at a bounded depth from the root of the term. We illustrate these properties by providing shallow encodings of the Krivine (call-by-name) and the CEK (call-by-value) abstract machines in the calculus. Categories and Subject Descriptors: F.3.3 [Logics and Meanings of Programs]: Studies of Program Constructs--Control primitives; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages--Operational semantics; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic--Lambda calculus and related systems; D.1.1 [Programming Techniques]: Applicative (Functional) Programming General Terms: Languages, Theory Additional Key Words and Phrases: Curry-Howard isomorphism, duality, explicit substitutions, Krivine machine, natural deduction

We investigate proof rules for information hiding, using the formalism of separation logic. In essence, we use the separating conjunction to partition the internal resources of a module from those accessed by the module's clients. The use of a logical connective gives rise to a form of dynamic partitioning, where we track the transfer of ownership of portions of heap storage between program components. It also enables us to enforce separation in the presence of mutable data structures with embedded addresses that may be aliased. Categories and Subject Descriptors: D.2.4 [Software Engineering]: Software Program Verification--Class invariants; D.3.3 [Programming Languages]: Language Constructs and Features-Modules, packages General Terms: Languages, Theory, Verification Additional Key Words and Phrases: Separation logic, modularity, resource protection DOI = 10.1145/1498926.1498929 http://doi.acm.org/10.1145/1498926.1498929

This survey gives an overview of formal results on the XML query language XPath. We identify several important fragments of XPath, focusing on subsets of XPath 1.0. We then give results on the expressiveness of XPath and its fragments compared to other formalisms for querying trees, algorithms, and complexity bounds for evaluation of XPath queries, as well as static analysis of XPath queries. Categories and Subject Descriptors: H.2.3 [Languages]: Query languages General Terms: Languages Additional Key Words and Phrases: XML, XPath

Previous work on statistical language modeling has shown that it is possible to train a feedforward neural network to approximate probabilities over sequences of words, resulting in significant error reduction when compared to standard baseline models based on n-grams. However, training the neural network model with the maximum-likelihood criterion requires computations proportional to the number of words in the vocabulary. In this paper, we introduce adaptive importance sampling as a way to accelerate training of the model. The idea is to use an adaptive n-gram model to track the conditional distributions produced by the neural network. We show that a very significant speedup can be obtained on standard problems. Index Terms--Energy-based models, fast training, importance sampling, language modeling, Monte Carlo methods, probabilistic neural networks.

ABSTRACT The UML is an industry standard for object-oriented software engineering. However, there is little empirical evidence on how UML is used. This article reports results of a survey of […]

This paper investigates ways to create algorithms to invert Laplace transforms numerically within a unified framework proposed by Abate and Whitt (2006). That framework approximates the desired function value by […]

The percentage of microprocessors used for embedded systems is increasing. The details of the design and implementation of the resilient system for embedded systems development, where the programs are written in the Smalltalk language and executed on the resilient embedded platform are analyzed.

The R language, a freely available environment for statistical computing and graphics is widely used in many fields. This 'expert-friendly' system has a powerful command language and programming environment, combined with an active user community. We discuss how R is ideal as a platform to support experimentation in mathematical statistics, both at the undergraduate and graduate levels. Using a series of case studies and activities, we describe how R can be used in a mathematical statistics course as a toolbox for experimentation. Examples include the calculation of a running average, maximization of a nonlinear function, resampling of a statistic, simple Bayesian modeling, sampling from multivariate normal, and estimation of power. These activities, often requiring only a few dozen lines of code, offer students the opportunity to explore statistical concepts and experiment. In addition, they provide an introduction to the framework and idioms available in this rich environment. KEY WORDS: Mathematical statistics education; Statistical computing., 1. INTRODUCTION The R language (Ihaka and Gentleman 1996; Hornik 2004) is a freely available environment for statistical computing and graphics. It allows the handling and storage of data, supports [...]

This article presents a new technique, adaptive replication, for automatically eliminating synchronization bottlenecks in multithreaded programs that perform atomic operations on objects. Synchronization bottlenecks occur when multiple threads attempt to concurrently update the same object. It is often possible to eliminate synchronization bottlenecks by replicating objects. Each thread can then update its own local replica without synchronization and without interacting with other threads. When the computation needs to access the original object, it combines the replicas to produce the correct values in the original object. One potential problem is that eagerly replicating all objects may lead to performance degradation and excessive memory consumption. Adaptive replication eliminates unnecessary replication by dynamically detecting contention at each object to find and replicate only those objects that would otherwise cause synchronization bottlenecks. We have implemented adaptive replication in the context of a parallelizing compiler for a subset of C++. Given an unannotated sequential program written in C++, the compiler automatically extracts the concurrency, determines when it is legal to apply adaptive replication, and generates parallel code that uses adaptive replication to efficiently eliminate synchronization bottlenecks. In addition to automatic parallelization and adaptive replication, our compiler also implements a lock coarsening transformation that increases the granularity at which the computation locks objects. The advantage is a reduction in the frequency with which the computation acquires and releases locks; the potential disadvantage is the introduction of new synchronization bottlenecks caused by increases in the sizes of the critical sections. Because the adaptive replication transformation takes place at lock acquisition sites, there is a synergistic interaction between lock coarsening and adaptive replication. Lock coarsening drives down the overhead of using adaptive replication, and adaptive replication eliminates synchronization bottlenecks associated with the overaggressive use of lock coarsening. Our experimental results show that, for our set of benchmark programs, the combination of lock coarsening and adaptive replication can eliminate synchronization bottlenecks and significantly

This article describes an approach for verifying programs in the presence of data abstraction and information hiding, which are key features of modern programming languages with objects and modules. This article draws on our experience building and using an automatic program checker, and focuses on the property of modular soundness: that is, the property that the separate verifications of the individual modules of a program suffice to ensure the correctness of the composite program. We found this desirable property surprisingly difficult to achieve. A key feature of our methodology for modular soundness is a new specification construct: the abstraction dependency, which reveals which concrete variables appear in the representation of a given abstract variable, without revealing the abstraction function itself. This article discusses in detail two varieties of abstraction dependencies: static and dynamic. The article also presents a new technical definition of modular soundness as a monotonicity property of verifiability with respect to scope and uses this technical definition to formally prove the modular soundness of a programming discipline for static dependencies. Categories and Subject Descriptors: D.1.5 [Programming Techniques]: Object-Oriented Programming; D.2.1 [Software Engineering]: Requirements/Specifications; D.2.4 [Software Engineering]: Software/Program Verification; D.3.3 [Programming Languages]: Language Constructs and Features--modules, packages; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs General Terms: Languages, Verification Additional Key Words and Phrases: Abstract variables, abstraction dependencies, extended static checking, modifies clauses, modular verification, object-oriented programming, specifications

This paper presents secure program partitioning, a language-based technique for protecting confidential data during computation in distributed systems containing mutually untrusted hosts. Confidentiality and integrity policies can be expressed by annotating programs with security types that constrain information flow; these programs can then be partitioned automatically to run securely on heterogeneously trusted hosts. The resulting communicating subprograms collectively implement the original program, yet the system as a whole satisfies the security requirements of participating principals without requiring a universally trusted host machine. The experience in applying this methodology and the performance of the resulting distributed code suggest that this is a promising way to obtain secure distributed computation. Categories and Subject Descriptors: D.4.6 [Operating Systems]: Security and Protection--Information flow controls; D.4.7 [Operating Systems]: Organization and Design--Distributed systems; D.3.4 [Programming Languages]: Processors--Compilers, Run-time environments; D.3.3 [Programming Languages]: Language Constructs and Features General Terms: Security, Languages Additional Key Words and Phrases: Confidentiality, declassification, distributed systems, downgrading, integrity, mutual distrust, secrecy, security policies, type systems

Java offers interesting opportunities for parallel computing. In particular, Java Remote Method Invocation (RMI) provides a flexible kind of remote procedure call (RPC) that supports polymorphism. Sun's RMI implementation achieves this kind of flexibility at the cost of a major runtime overhead. The goal of this article is to show that RMI can be implemented efficiently, while still supporting polymorphism and allowing interoperability with Java Virtual Machines (JVMs). We study a new approach for implementing RMI, using a compiler-based Java system called Manta. Manta uses a native (static) compiler instead of a just-in-time compiler. To implement RMI efficiently, Manta exploits compile-time type information for generating specialized serializers. Also, it uses an efficient RMI protocol and fast low-level communication protocols. A difficult problem with this approach is how to support polymorphism and interoperability. One of the consequences of polymorphism is that an RMI implementation must be able to download remote classes into an application during runtime. Manta solves this problem by using a dynamic bytecode compiler, which is capable of compiling and linking bytecode into a running application. To allow interoperability with JVMs, Manta also implements the Sun RMI protocol (i.e., the standard RMI protocol), in addition to its own protocol. We evaluate the performance of Manta using benchmarks and applications that run on a 32-node Myrinet cluster. The time for a null-RMI (without parameters or a return value) of Manta is 35 times lower than for the Sun JDK 1.2, and only slightly higher than for a C-based RPC protocol. This high performance is accomplished by pushing almost all of the runtime overhead of RMI to compile time. We study the performance differences between the Manta and the Sun RMI protocols in detail. The poor performance of the Sun RMI protocol is in part due to an inefficient implementation of the protocol. To allow a fair comparison, we compiled the applications and the Sun RMI protocol with the native Manta compiler. The results show that Manta's null-RMI latency is still eight times lower than for the compiled Sun RMI protocol and that Manta's efficient RMI protocol results in 1.8 to 3.4 times higher speedups for four out of six applications. Categories and Subject Descriptors: D. 1.3 [Programming Techniques]: Concurrent Programming--distributed programming, parallel programming; D.3.2. [Programming Languages]: Language Classifications--concurrent, distributed, and parallel languages; object-oriented languages; D.3.4 [Programming Languages]: Processors--compilers; run-time environments General Terms: Languages, Performance Additional Key Words and Phrases: Communication, performance, remote method invocation

One-way, dataflow constraints are commonly used in graphical interface toolkits, programming environments, and circuit applications. Previous papers on dataflow constraints have focused on the design and implementation of individual algorithms. In contrast, this article focuses on the lessons we have learned from a decade of implementing competing algorithms in the Garnet and Amulet graphical interface toolkits. These lessons reveal the design and implementation tradeoffs for different one-way, constraint satisfaction algorithms. The most important lessons we have learned are that (1) mark-sweep algorithms are more efficient than topological ordering algorithms; (2) lazy and eager evaluators deliver roughly comparable performance for most applications; and (3) constraint satisfaction algorithms have more than adequate speed, except that the storage required by these algorithms can be problematic. Categories and Subject Descriptors: D.2.2 [Software Engineering]: Design Tools and Techniques--user interfaces; D.2.6 [Software Engineering]: Programming Environments--graphical environments; interactive environments; D.3.2 [Programming Languages]: Language Classifications--dataflow languages; D.3.3 [Programming Languages]: Language Constructs and Features--constraints; I.1.2 [Computing Methodologies]: Algorithms--nonalgebraic algorithms; I.1.2 [Computing Methodologies]: Languages and Systems--evaluation strategies General Terms: Algorithms, Design, Experimentation, Human Factors, Performance Additional Key Words and Phrases: Constraint experience, constraint satisfaction, constraint usage, eager evaluation, lazy evaluation, one-way dataflow constraints

We establish a correspondence between temporal logic and a subset of ATSQL, a temporal extension of SQL-92. In addition, we provide an effective translation from temporal logic to ATSQL that enables a user to write high-level queries which are then evaluated against a space-efficient representation of the database. A reverse translation, also provided in this paper, characterizes the expressive power of a syntactically defined subset of ATSQL queries. Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic--temporal logic; H.2.3 [Database Management]: Languages--query languages; H.2.4 [Database Management]: Systems--query processing General Terms: Languages, Theory Additional Key Words and Phrases: ATSQL, first-order temporal logic, query translation, temporal databases

Orca is a portable, object-based distributed shared memory (DSM) system. This article studies and evaluates the design choices made in the Orca system and compares Orca with other DSMs. The […]

The usability of the (ML)2 language for formal modeling of knowledge-based systems was assessed. Specifically, case studies concerning the use of (ML)2 for adaptation and construction of an expert model and its reusability were carried out. The language formalized the CommonKADS expert model, and was evaluated according to expressiveness, error frequency, redundancy, locality of changes, reusability and support tools.

The artificial intelligence (AI) community should continue to use Lisp not only because it is the original programming language for AI applications but because it is ideal for 'creating and embedding other domain- or problem-specific languages' in future applications. Moreover, it is a high-level and highly dynamic language that employs higher order functionals to express patterns of computation with the ability to control its own syntax.

Empirical evidence is provided in which the reliability estimation has an effect on estimates of software-reliability while testing is in progress. It indicates that the reliability models should encompass additional data, created in testing, as found in some kind of code coverage. The need for further research, to identify the specific testing method which gives better reliability, is emphasized.