Towards optimal workload-aware XML to relational schema mapping

Storing XML documents in relational databases has drawn much attention in recent years because it can leverage existing investments in relational database technologies. Different algorithms have been proposed to map XML DTD/Schema to relational schema in order to store XML data in relational databases. However, most work defines mapping rules based on heuristics without considering application characteristics, hence fails to produce efficient relational schema for various applications. In this paper, we propose a workload-aware approach to generate relational schema from XML data and user specified workload. Our approach adopts the genetic algorithm to find optimal mappings. An elegant encoding method and related operations are proposed to manipulate mappings using bit strings. Various techniques for optimization can be applied to the XML to relational mapping problem based on this representation. We implemented the proposed algorithm and our experiment results showed that our algorithm was more robust and produced better mappings than existing work.     

From searching text to querying XML streams

XML data is queried with a limited form of regular expressions, in a language called XPath. New XML stream processing applications, such as content-based routing or selective dissemination of information, require thousands or millions of XPath expressions to be evaluated simultaneously on the incoming XML stream at a high, sustained rate. In its simplest approximation, the XPath evaluation problem is analogous to the text search problem, in which one or several regular expressions need to be matched to a given text. At a finer level, it is related to the tree pattern matching problem. However, unlike the traditional setting, the number of regular expressions here is much larger, while the “text” is much shorter, since it corresponds to the depth of the XML stream. In this paper we examine techniques that have been proposed for XML stream processing and describe a few open problems.     

基于模式约束的XML数据存储和索引技术

对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.现有的索引和存储策略,大部分以丢失结构信息为代价,不利于结构查询和更新.XMLSchema作为描述XML文档结构信息的标准,对文档和查询路径进行有效性验证提供保证,基于此提出了一种基于XMLmSchema模式约束的XML文档数据索引技术SBXI,用于文档数据存储和查询的导航,提高了存储和查询效率,具有较高的空间利用率和较低的索引维护代价,并支持含有多个谓词的复杂查询.     

OSiL: An instance language for optimization

Distributed computing technologies such as Web Services are growing rapidly in importance in today’s computing environment. In the area of mathematical optimization, it is common to separate modeling languages from optimization solvers. In a completely distributed environment, the modeling language software, solver software, and data used to generate a model instance might reside on different machines using different operating systems. Such a distributed environment makes it critical to have an open standard for exchanging model instances. In this paper we present OSiL (Optimization Services instance Language), an XML-based computer language for representing instances of large-scale optimization problems including linear programs, mixed-integer programs, quadratic programs, and very general nonlinear programs. OSiL has two key features that make it much superior to current standard forms for optimization problem instances. First, it uses the object-oriented features of XML schemas to efficiently represent nonlinear expressions. Second, its XML schema maps directly into a corresponding in-memory representation of a problem instance. The in-memory representation provides a robust application program interface for general nonlinear programming, facilitates reading and writing postfix, prefix, and infix formats to and from the nonlinear expression tree, and makes the expression tree readily available for function and derivative evaluations.     

An exploration of students’ errors in derivatives in a university of technology

This paper reports on an exploration of errors that were displayed by students who studied mathematics in chemical engineering in derivatives of various functions such as algebraic, exponential, logarithmic and trigonometric functions. The participants of this study were a group of twenty students who were at risk in an extended curriculum programme in a university of technology in Western Cape, South Africa. The researcher used a qualitative case study approach and collected data from students’ written work. This research uses action, process, object, and schema (APOS) theory to classify errors into categories and to analyse and interpret the data collected. The students displayed five different kinds of errors, namely, conceptual, interpretation, linear extrapolation, procedural and arbitrary. The use of APOS theory as a framework revealed that several students’ errors might be caused by over-generalisation of mathematical rules and properties such as the power rule of differentiation and distributive property in manipulation of algebraic expressions. This study suggests that teaching of the standard rules of differentiation should put emphasis on its restrictions to eliminate common errors that normally crop up due to over-generalisation of certain differentiation rules.     

Using dialog-controlled rule systems in a maintenance module for knowledge bases

Dialog-controlled rule systems were introduced as a tool to describe the way in which theWimdas system for knowledge-based analysis of marketing data manages its dialog with the user. In this paper we shall discuss how dialog-controlled rule systems can be used to specify a formal language aiding a knowledge engineer in maintaining a system's knowledge base. Although this language is finite, it must be defined generically, being too extensive to be enumerated. In contrast to the well-known traditional methods for defining formal languages — using finite automata, regular expressions or grammars — our method can be applied by a user who need not be an expert in theoretical computer science.Research for this paper was supported by the Deutsche Forschungsgemeinschaft.     

An exact method with variable fixing for solving the generalized assignment problem

We propose a simple exact algorithm for solving the generalized assignment problem. Our contribution is twofold: we reformulate the optimization problem into a sequence of decision problems, and we apply variable-fixing rules to solve these effectively. The decision problems are solved by a simple depth-first lagrangian branch-and-bound method, improved by our variable-fixing rules to prune the search tree. These rules rely on lagrangian reduced costs which we compute using an existing but little-known dynamic programming algorithm.     

The set of numerical semigroups of a given genus

In this paper we present a new approach to construct the set of numerical semigroups with a fixed genus. Our methodology is based on the construction of the set of numerical semigroups with fixed Frobenius number and genus. An equivalence relation is given over this set and a tree structure is defined for each equivalence class. We also provide a more efficient algorithm based on the translation of a numerical semigroup to its so-called Kunz-coordinates vector.     

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base 2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.     

Automatic detection of degenerate planetary gear trains with different degree of freedoms

Planetary gear trains (PGT) are widely used in transmissions of vehicles, pulley blocks, wrist watches, machine tool, robots, etc. The structural synthesis of PGTs is an effective way to create novel transmissions. In the synthesis process, one of the most important problems is to detect and eliminate degenerate PGTs. This paper proposes a fully automatic algorithm to resolve this key problem. Our previous graph representation of PGT is first introduced and the corresponding adjacency matrix is used as the numerical tool, based on which the fundamental circuits (f-circuit) of PGT can be easily determined. The present algorithm is executed by successively adding a single f-circuit to generate sub-graphs. The detection process has been automated by an interactive computer program. The algorithm is applicable for PGTs with any number of degree of freedoms (DOF). The algorithm has been applied to a large number of PGTs, including the counterexamples found in literature. Our results of all the tested PGTs are verified to be correct.     

An XML format for benchmarks in High School Timetabling

The High School Timetabling Problem is amongst the most widely used timetabling problems. This problem has varying structures in different high schools even within the same country or educational system. Due to lack of standard benchmarks and data formats this problem has been studied less than other timetabling problems in the literature. In this paper we describe the High School Timetabling Problem in several countries in order to find a common set of constraints and objectives. Our main goal is to provide exchangeable benchmarks for this problem. To achieve this we propose a standard data format suitable for different countries and educational systems, defined by an XML schema. The schema and datasets are available online.     

Uniform election in trees and polyominoids

Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves until the graph is reduced to a single vertex; the elected one. In Métivier et al. (2003) [7], the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that the expected election duration of this algorithm is O(ln(n)) where n denotes the size of the tree, and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs.In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

A Math Query Language with an Expanded Set of Wildcards

Math search is a new area of research with many enabling technologies but also many challenges. Some of the enabling technologies include XML, XPath, XQuery, and MathML. Some of the challenges involve enabling search systems to recognize mathematical symbols and structures. Several math search projects have made considerable progress in meeting those challenges. One of the remaining challenges is the creation and implementation of a math query language that enables the general users to express their information needs intuitively yet precisely. This paper will present such a language and detail its features. The new math query language offers an alternative way to describe mathematical expressions that is more consistent and less ambiguous than conventional mathematical notation. In addition, the language goes beyond the Boolean and proximity query syntax found in standard text search systems. It defines a powerful set of wildcards that are deemed important for math search. These wildcards provide for more precise structural search and multi-levels of abstractions. Three new sets of wildcards and their implementation details will also be discussed.      

Theoretical and Empirical Properties of the Genetic Algorithm as a Numerical Optimizer

Abstract

We investigate the basic form of the genetic algorithm as an optimization technique. Its failure to maximize a simple function of a string of 50 binary variables prompts a closer study of Holland's “schema theorem” and we find the implications of this result to be much weaker than are often claimed. Further theoretical results and exact calculations for simple problems provide an understanding of how the genetic algorithm works and why it failed in our original application. We show that the algorithm can be fine tuned to succeed in that problem but only by introducing features that could cause serious difficulties in harder problems.     

The validation of SGML content models

The Standard Generalized Markup Language (SGML) is an ISO standard that provides a syntactic meta-language for the definition of textual markup systems, which are used to indicate the structure of documents so that they can be electronically typeset, searched, and communicated. We address only one problem raised by the standard, namely: in SGML, the right-hand sides of context-free productions are regular expressions, called content models, that are restricted to be what the standard calls “unambiguous”, but what is more appropriately called deterministic. We solve the problem of how to define determinism precisely, how to recognize deterministic regular expressions efficiently, and how to recognize deterministic regular languages. Any SGML parser must check that a given document grammar conforms to the standard; that is, it must validate it. Hence, our results are an important step in the clarification of the standard and in the efficient implementation of an SGML parser for SGML document grammars.