Cognitive Science Program

Genetic algorithms for the traveling salesman problem (1985)
John Grefenstette, Rajeev Gopal, Brian Rosmaita and Dirk Van Gucht
Lawrence Erlbaum. 160 (168), 160-168

Abstract

This paper presents some approaches to the application of Genetic Algorithms to the Traveling Salesman Problem. A number of representation issues are discussed along with several recombination operators. Some preliminary analysis of the Adjacency List representation is presented, as well as some promising experimental results.

A graph-oriented object database model (1994)
Marc Gyssens, Jan Paredaens, Jan Van den Bussche and Dirk Van Gucht
IEEE Transactions on Knowledge & Data Engineering, (4), 572-586

Abstract

A graph-oriented object database model (GOOD) is introduced as a theoretical basis for database systems in which manipulation as well as conceptual representation of data is transparently graph-based. In the GOOD model, the scheme as well as the instance of an object database is represented by a graph, and the data manipulation is expressed by graph transformations. These graph transformations are described using five basic operations and a method construct, all with a natural semantics. The basic operations add and delete objects and edges as a function of the matchings of a pattern. The expressiveness of the model in terms of object-oriented modeling and data manipulation power is investigated.

The structure of the relational database model (1989)
Jan Paredaens, Paul De Bra, Marc Gyssens and Dirk Van Gucht
Springer Science & Business Media. 17

Abstract

This book presents an overview of the most fundamental aspects of the theory that underlies the Relational Database Model. As such it is self-contained though experience with formal models and abstract data manipulating on the one hand and with the practical use of a relational system on the other hand can help the reader. Such experience will offer the reader a better understanding of and a motivation for the different concepts, theories and results mentioned in the book. We have focussed on the most basic concepts and aspects of the relational model, without trying to give a complete overview of the state of the art of database theory. Recently a lot of books on databases in general and on the relational model in particular have been published. Most of them describe the use of database systems.'Some clarify how information has to be structured and organized before it can be used to build applications. Others help the user in writing down his applications or in finding tricky ways to optimize the running time or the necessary space. Another category of books treat more fundamental and more general aspects such as the description of the relational model, independent of any implementation, the decomposition in normal forms or the global design of distributed databases. Few, however, are the books that describe in a formal way some of the subjects mentioned above.

The effects of population size, heuristic crossover and local improvement of a genetic algorithm for the traveling salesman problem (1989)
Prasanna Jog
Proc. 3rd ICGA, 110-115

Abstract

CiNii 国立情報学研究所 学術情報ナビゲータ[サイニィ]. メニュー 検索 …

Image registration by genetic search (1984)
J Michael Fitzpatrick
Proc. Southeastcon 84, Louisville, KY, April, 460-464

Abstract

CiNii 国立情報学研究所 学術情報ナビゲータ[サイニィ]. メニュー 検索 …

Towards a theory of spatial database queries (1994)
Jan Paredaens, Jan Van den Bussche and Dirk Van Gucht
ACM. 279-288

Abstract

A general model for spatial databases is considered, which extends the relational model by allowing as tuple components not only atomic values but also geometrical figures. The model, which is inspired by the work of Kanellakis, Kuper and Revesz on constraint query languages, includes a calculus and an algebra which are equivalent. Given this framework, the concept of spatial database query is investigated. Thereto, Chandra and Harel's well-known consistency criterion for classical relational queries is adapted. Various adaptations are proposed, depending on the kinds of geometry in which the spatial information in the database is to be interpreted. The consistency problem for calculus queries is studied. Expressiveness issues are examined. The main purpose of the paper is to open up new grounds for theoretical research in the area of spatial database systems. Consequently, many open problems are …

Incorporating Heuristic Information into Genetic Search (1987)
Jung Y Suh and D Van Gucht
JJ Grefen,

Abstract

Genetic Algorithms have been shown to be robust optimization algorithms for {positive} real-valued functions defined over domains of the form ll"[R denotes the real numbers}.Only recently have there been attempts to apply genetic algorithms to other optimization problems, such as combinatorial optimization problems. In this paper, we identify several obstacles which need to be overcome to successfully apply genetic algorithms to such problems and indicate how integrating heuristic information related to the problem under consideration helps in overcoming these obstacles. We illustrate the validity of our approach by providing genetic algorithm lor the Traveling Salesman Problem and the Sliding Block Puzzle,

A graph-oriented object model for database end-user interfaces (1990)
Marc Gyssens, Jan Paredaens and Dirk Van Gucht
ACM Press.

Abstract

The current database research trend is towards systems which can deal with advanced data applications that go beyond the data standard "enterprise" of "office" database application. This trend is reflected in the research on extension architectures and object-oriented databases. Along with this trend, the need for better and easier-to-use database and end-user interfaces has been stressed. Therefore, we propose a graph-based data model which shares many features with existing data models, but which better facilitates the rigorous study of graphical database end-user interfaces. Graphs have been an integral part of the database design process ever since the introduction of semantic data models. Their usage in data manipulation languages, however, is far more sparse. To deal with data manipulation,typically, schemes in semantic data models are transformed into a conceptual data model such as the relational model. The required database language features then become those of the conceptual model. Object-oriented data models on the other hand, often offer computational complete, non-graphical data languages, usually in the style of object-oriented programming languages such as Smalltalk. Due to their expressiveness, however, these languages do not lend themselves easily as high-level data languages. The first graphical database end-user interfaces were developed for the relational model (for example Zloof's Query-By-Example (QBE)). The earliest graphical database end-user interfaces for semantic models were associated with the Entity-Relationship model. Subsequently graphical interfaces were developed for more complex …

Parallel genetic algorithms applied to the traveling salesman problem (1991)
Prasanna Jog, Jung Y Suh and Dirk Van Gucht
SIAM Journal on Optimization, 1 (4), 515-529

Abstract

Genetic algorithms are adaptive search algorithms that have been shown to be robust optimization algorithms for multimodal real-valued functions and a variety of combinatorial optimization problems. In contrast to more standard search algorithms, genetic algorithms base their progress on the performance of a population of candidate solutions, rather than on a single candidate solution.The authors will concentrate on the application of genetic algorithms to the traveling salesman problem. For this problem, there exist several such algorithms, ranging from pure genetic algorithms to genetic algorithms that incorporate heuristic information. These algorithms will be reviewed and their performance contrasted.A serious drawback of genetic algorithms is their inefficiency when implemented on a sequential machine. However, due to their inherent parallel properties, they can be successfully implemented on parallel …

Converting nested algebra expressions into flat algebra expressions (1992)
Jan Paredaens and Dirk Van Gucht
ACM Transactions on Database Systems (TODS), 17 (1), 65-93

Abstract

Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same “flat information” from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.

First-order queries on finite structures over the reals (1998)
Jan Paredaens, Jan Van den Bussche and Dirk Van Gucht
SIAM Journal on Computing, 27 (6), 1747-1763

Abstract

We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite …

Possibilities and limitations of using flat operators in nested algebra expressions (1988)
Jan Paredaens and Dirk Van Gucht
ACM. 29-38

Abstract

In 19Y7 Makmoucb [18] proposed to generahze the relational database model by removmg the first normal form assumption Jaeschke and Schek [15] mtraduced a generallzatlon of the ordmary relational model by allowmg relations with set-valued attributes and adding two restructuring operators, the nest and the unnest operators, to manipulate such (one-level) nested relations Thomas and Fischer 1261 generalized Jaeschke and Schek’s model and allowed nested relations of arbitrary (but fixed) depth Roth, Korth and Sllberschatz [23] defined a calculus like query language for the nested relational model of Thomas and Flscher Since then numerous SQL-hhe query languages [17, 20, 21, 22], graphical-oriented query languages [13] and datalog-hke languages [3, 4, 7, 16] have been mtroduced for this model or slight generahzatlons of It Also, various groups [5, 10, 11, 12, 19, 25] have started to implement the nested relational database model, some on top of an exlstmg database management system, others from scratchPermIssIon to copy wthout fee all or part of this matenal IS granted provtded that the copzs are not made or dlstrlbuted for direct commerclal advantage, the ACM copyright notlce and the title of the pubhcatlon and Its date appear, and notlce IS gwen that copymg IS by permlsslon of the Assoclatlon for Computmg Machmery To copy otherwse or to repubhsh, reqmres a fee and/or specific permlsston

Interactions between dependencies and nested relational structures (1985)
Patrick C Fischer, Lawrence V Saxton, Stan J Thomas and Dirk Van Gucht
Journal of Computer and System Sciences, 31 (3), 343-354

Abstract

Nesting is a way of transforming a first-normal-form relation into a structure with set-valued entries in some positions instead of atomic entries. In this paper we study how functional and multivalued dependencies interact with nesting. We describe how nesting preserves, alters, or destroys dependencies holding in a first-normal-form relation. We then consider dependencies which hold in each block of the horizontally decomposed relation induced by nesting and study the relationship between these “local” dependencies and “global” dependencies in the normalized relation.

The powerset algebra as a result of adding programming constructs to the nested relational algebra (1988)
Marc Gyssens and Dirk Van Gucht
ACM. 17 (3), 225-232

Abstract

In this paper, we discuss augmentations of the nested relational algebra with programming constructs, such as while-loops and for-loops. We show that the algebras obtained in this way are equivalent to a slight extension of the powerset algebra, thus emphasizing both the strength and the naturalness of the powerset algebra as a tool to manipulate nested relations, and, at the same time, indicating more direct ways to implement this algebra.

An overview of GOOD (1992)
Jan Paredaens, Jan Van den Bussche, Marc Andries, Marc Gemis, Marc Gyssens, Inge Thyssens ...
ACM SIGMOD Record, 21 (1), 25-31

Abstract

GOOD is an acronym, standing for Graph-Oriented Object Database. GOOD is being developed as a joint research effort of Indiana University and the University of Antwerp. The main thrust behind the project is to indicate general concepts that are fundamental to any graph-oriented database user-interface. GOOD does not restrict its attention to well-considered topics such as ad-hoc query facilities, but wants to cover the full spectrum of database manipulations. The idea of graph-pattern matching as a uniform object manipulation primitive offers a uniform framework in which this can be accomplished.