Database reverse engineering: From requirements to CARE tools

This paper analyzes the requirements that CASE tools should meet for effective database reverse engineering (DBRE), and proposes a general architecture for data-centered applications reverse engineering CASE environments. First, the paper describes a generic DBMS-independent DBRE methodology, then it analyzes the main characteristics of DBRE activities in order to collect a set of desirable requirements. Finally, it describes DB-MAIN, an operational CASE tool developed according to these requirements. The main features of this tool that are described in this paper are its unique generic specification model, its repository, its transformation toolkit, its user interface, the text processors, the assistants, the methodological control and its functional extensibility. Finally, the paper describes five real-world projects in which the methodology and the CASE tool were applied. This is a heavily revised and extended version of “Requirements for Information System Reverse Engineering Support” by J.-L. Hainaut, V. Englebert, J. Henrard, J.-M. Hick, D. Roland, which first appeared in the Proceedings of the Second Working Conference on Reverse Engineering, IEEE Computer Society Press, pp. 136–145, July 1995. This paper presents some results of the DB-MAIN project. This project is partially supported by the Région Wallonne, the European Union, and by a consortium comprising ACEC-OSI (Be), ARIANE-II (Be), Banque UCL (Lux), BBL (Be), Centre de recherche public H. Tudor (Lux), CGER (Be), Cockerill-Sambre (Be), CONCIS (Fr), D'Ieteren (Be), DIGITAL, EDF (Fr), EPFL (CH), Groupe S (Be), IBM, OBLOG Software (Port), ORIGIN (Be), Ville de Namur (Be), Winterthur (Be), 3 Suisses (Be). The DB-Process subproject is supported by the Communauté Fran?aise de Belgique.     

Fast index for approximate string matching

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k from the pattern are reported in $O(m+\log \log n+\text{\#}\text{matches})$ time (for constant k). The space complexity of the index is $O(n^{1+?})$ for any constant $?>0$.     

On minimizing pattern splitting in multi-track string matching

Given a pattern string P=p₁p₂p_m and K parallel text strings over an integer alphabet Σ, our task is to find the smallest integer κ>0 such that P can be split into κ pieces P=P¹…P^κ, where each Pⁱ has an occurrence in some text track T^k_i and these partial occurrences retain the order. We study some variations of this minimum splitting problem, such as splittings with limited gaps and transposition invariance, and show how to use sparse dynamic programming to solve the variations efficiently. In particular, we show that the minimum splitting problem can be interpreted as a shortest path problem on line segments.     

双层规划问题的一种模式搜索Filter方法

双层规划在工程设计和经济管理中应用广泛,结合模式搜索方法和Filter方法提出了一种解决双层规划问题的算法—模式搜索Filter方法.算法以Filter法思想构造接受准则,以模式搜索提供迭代方向和步长,能够有效的解决一类双层规划问题.     

Approximate string matching on Ziv–Lempel compressed text

We present the first nontrivial algorithm for approximate pattern matching on compressed text. The format we choose is the Ziv–Lempel family. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text allowing up to kinsertions, deletions and substitutions. On LZ78/LZW we need O(mkn+R) time in the worst case and O(k²n+mkmin(n,(mσ)^k)+R) on average where σ is the alphabet size. The experimental results show a practical speedup over the basic approach of up to 2X for moderate m and small k. We extend the algorithms to more general compression formats and approximate matching models.     

Pattern Classification by Linear Goal Programming and its Extensions

Pattern classification is one of the main themes in pattern recognition, and has been tackled by several methods such as the statistic one, artificial neural networks, mathematical programming and so on. Among them, the multi-surface method proposed by Mangasarian is very attractive, because it can provide an exact discrimination function even for highly nonlinear problems without any assumption on the data distribution. However, the method often causes many slits on the discrimination curve. In other words, the piecewise linear discrimination curve is sometimes too complex resulting in a poor generalization ability. In this paper, several trials in order to overcome the difficulties of the multi-surface method are suggested. One of them is the utilization of goal programming in which the auxiliary linear programming problem is formulated as a goal programming in order to get as simple discrimination curves as possible. Another one is to apply fuzzy programming by which we can get fuzzy discrimination curves with gray zones. In addition, it will be shown that using the suggested methods, the additional learning can be easily made. These features of the methods make the discrimination more realistic. The effectiveness of the methods is shown on the basis of some applications.     

Multi-stage scenario generation by the combined moment matching and scenario reduction method

We describe an opportunity to speed up multi-stage scenario generation and reduction using a combination of two well-known methods: the moment matching method (Høyland and Wallace, 2001) and the method for scenario reduction to approximately minimize a metric (Heitsch and Römish, 2009). Our suggestion is to combine them rather than using them in serial by making use of a stage-wise approximation to the moment matching algorithm. Computational results show that combining the methods can bring significant benefits.     

Strongest postcondition semantics as the formal basis for reverse engineering

Reverse engineering of program code is the process of constructing a higher level abstraction of an implementation in order to facilitate the understanding of a system that may be in a “legacy” or “geriatric” state. Changing architectures and improvements in programming methods, including formal methods in software development and object-oriented programming, have prompted a need to reverse engineer and re-engineer program code. This paper describes the application of the strongest postcondition predicate transformer (sp) as the formal basis for the reverse engineering of imperative program code. This work is supported in part by the National Science Foundation grants CCR-9407318, CCR-9209873, and CDA-9312389. This author is supported in part by a NASA Graduate Student Researchers Program Fellowship.