This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and when the "length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vectors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the "Fiedler vector," widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a relational database

This work presents a systematic comparison between seven kernels (or similarity matrices) on a graph, namely the exponential diffusion kernel, the Laplacian diffusion kernel, the von Neumann kernel, the regularized Laplacian kernel, the commute time kernel, and finally the Markov diffusion kernel and the cross-entropy diffusion matrix - both introduced in this paper - on a collaborative recommendation task involving a database. The database is viewed as a graph where elements are represented as nodes and relations as links between nodes. From this graph, seven kernels are computed, leading to a set of meaningful proximity measures between nodes, allowing to answer questions about the structure of the graph under investigation; in particular, recommend items to users. Cross- validation results indicate that a simple nearest-neighbours rule based on the similarity measure provided by the regularized Laplacian, the Markov diffusion and the commute time kernels performs best. We therefore recommend the use of the commute time kernel for computing similarities between elements of a database, for two reasons: (1) it has a nice appealing interpretation in terms of random walks and (2) no parameter needs to be adjusted.

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted, undirected graph. It is based on a Markov-chain model of random walk through the database. The suggested quantities, representing dissimilarities (or similarities) between any two elements, have the nice property of decreasing (increasing) when the number of paths connecting those elements increases and when the "length" of any path decreases. The model is evaluated on a collaborative recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. The model, which nicely fits into the so-called "statistical relational learning" framework as well as the "link analysis" paradigm, could also be used to compute document or word similarities, and, more generally could be applied to other database or Web mining tasks.

Materialization is a powerful and ubiquitous abstraction pattern for conceptual modeling that relates a class of categories (e.g., models of cars) and a class of more concrete objects (e.g., individual cars). This paper presents materialization as a generic relationship between two classes of objects and describes an abstract implementation of it. The presentation is abstract in that it is not targeted at a specific object system. The target system is supposed to provide: 1) basic object-modeling facilities, supplemented with an explicit metaclass concept and 2) operations for dynamic schema evolution like creation or deletion of a subclass of a given class and modification of the type of an attribute of a class. The presentation is generic in that the semantics of materialization is implemented in a metaclass, which is a template to be instantiated in applications. Application classes are created as instances of the metaclass and they are thereby endowed with structure and behavior consistent with the generic semantics of materialization.

Intensional answers are conditions that tuples of values must satisfy to belong to the usual extensional answer of a query addressed to a deductive database. The authors review the concept of intensional answers and introduce a general method for generating them as logical consequences of the query and of deduction rules. The authors show how integrity constraints can filter out inadequate answers and produce simpler and more informative answers. An efficient organization for the combination of answers and constraints is described. The introduction of negation in queries and in the body of deduction rules is discussed. Beyond the mechanics of answer generation, the interest of the approach also depends on a strategy for selecting answers to a user submitting a query. This requires techniques for user modeling and dialogue management similar to those required for expert systems.>

It is shown how intentional answers can be generated as logical consequences of the query and of deduction rules and how integrity constraints can filter out inadequate answers and produce simpler and more informative answers. An efficient organization for the combination of answers and constraints is presented. The authors focus on the design of mechanisms for controlling the generation of intentional answers using integrity constraints. The assertions specified by constraints bear not only on the database but also on queries and intentional answers, since the latter specify sets of values from the database.>

This paper describes CQLF (CODASYL Query Language, Flat) [MAN081]. CQLF is a high level language for accessing and manipulating data in databases described using the 1981 ANSI dpANS version of the CODASYL Data Description Language [ANSI81]. CQLF has similarities to typical relational languages, such as SQL [ASTR76, CHAM76] and QUEL [STON76]. CQLF provides capabilities for querying and operating on databases described both in a "relational style" (having no CODASYL sets, using only values to represent interrecord relationships, and having records with no arrays), and in a "network style" (using CODASYL sets to represent interrecord relationships, and having records containing arrays).