Search

Despite the huge amount of work devoted to the treatment of time within the relational context, few relevant temporal phenomena still remain to be addressed. One of them is the treatment of “ nearly periodic events ”, i.e., events/facts that occur in intervals of time which repeat periodically (e.g., a meeting occurring twice each Monday , possibly not at regular times ). Nearly periodic events are quite frequent in everyday life, and thus in many applicative contexts. Their treatment within the relational model is quite challenging, since it involves the integrated treatment of three aspects: (i) the number of repetitions, (ii) their periodicity , and (iii) temporal indeterminacy . Coping with this problem requires an in-depth extension of current temporal relational database techniques. In this paper, we introduce a new data model, and new definitions of relational algebraic operators coping with the above issues. We ascertain the properties of the new model and algebra, with emphasis on the expressiveness of our representation model, on the reducibility property, and on the correctness of the algebraic operators.

Compound approximation spaces for relational data are proposed.They are viewed as expansions of tolerance approximation spaces to a relational case.Properties of compound approximation spaces are investigated.Compound approximation spaces enable to derive new knowledge from relational data. Rough set theory provides a powerful tool for dealing with uncertainty in data. Application of variety of rough set models to mining data stored in a single table has been widely studied. However, analysis of data stored in a relational structure using rough sets is still an extensive research area. This paper proposes compound approximation spaces and their constrained versions that are intended for handling uncertainty in relational data. The proposed spaces are expansions of tolerance approximation ones to a relational case. Compared with compound approximation spaces, the constrained version enables to derive new knowledge from relational data. The proposed approach can improve mining relational data that is uncertain, incomplete, or inconsistent.

Graphical abstractDisplay Omitted HighlightsFormula-based relations defined in a granular computing framework are proposed.The relations are used to construct more informative granules.The granules are used to represent relational data and patterns.Thanks to this approach, the generation of patterns can be speeded up.The approach makes it possible to discover richer knowledge from relational data. The complex structure of relational data makes the process of knowledge discovery from data a more challenging task compared with the single table data structure. The usefulness of granular computing based approaches to mining data stored in a single table is a driving force for adapting this method to relational data. This paper proposes relation-based granules that are defined in a granular computing based approach to mining relational data. The relations are used to represent relational data and patterns to be discovered. Thanks to this representation, the generation of patterns can be speeded up. The representation also makes it possible to discover richer knowledge from relational data.

We present a new approach lo learn from relational data based on re-representation of the examples. This approach, called property-based re-representation is based on a new analysis of the structure of refinement graphs used in ILP and relational learning in general. This analysis allows the characterization of relational examples by a set of multi-relational patterns called properties. Using them, we perform a property-based re-representation of relational examples that facilitates the development of relational learning techniques. Additionally, we show the usefulness of re-representation with a collection of experiments in the context of nearest neighbor classification. © 2015 - IOS Press and the authors., Research partially supported by Projects Next-CBR (TIN2009-13692-C03-01) and Cognitio (TIN2012-38450- C03-03) and by the Generalitat de Catalunya under the grants 2009-SGR-1434.

Event relations are used in many temporal relational database approaches to represent facts occurring at time instants. However, to the best of our knowledge, none of such approaches fully copes with the definition of events as provided, e.g., by the “consensus” temporal database glossary. We propose a new approach which overcomes such a limitation, allowing one to cope with multiple events occurring in the same temporal granule. This move involves major extensions to current approaches, since indeterminacy about the time and number of occurrences of events need to be faced. Specifically, we have introduced a new data model, and new definitions of relational algebraic operators coping with the above issues, and we have studied their reducibility. Last, but not least, we have shown that our approach can be easily extended in order to cope with a general form of temporal indeterminacy. Such an extension further increases the applicability of our approach.

Relational similarity can be defined as the similarity between two semantic relations R and R' that exist respectively in two word pairs (A,B) and (C,D). Relational search, a novel search paradigm that is based on the relational similarity between word pairs, attempts to find a word D for the slot ? in the query {(A,B), (C,?)} such that the relational similarity between the two word pairs (A, B) and (C, D) is a maximum. However, one problem frequently encountered by a Web-based relational search engine is that the inherent noise in Web text leads to incorrect measurement of relational similarity. To overcome this problem, we propose a method for verifying a relational search result that exploits the symmetric properties in proportional analogies. To verify a candidate result D for a query {(A, B), (C, ?)}, we replace the original question mark by D to create a new query {(A,B),(?,D)} and verify that we can retrieve C as a candidate for the new query. The score of C in the new query can be seen as a complementary score of D because it reflects the reliability of D in the original query. Moreover, transformations of words in proportional analogies lead to relational symmetries that can be utilized to accurately measure the relational similarity between two semantic relations. For example, if the two word pairs (A,B) and (C, D) show a high degree of relational similarity then the two word pairs (B,A) and (D,C) also have a high degree of relational similarity. We apply this idea in relational search by using symmetric queries such as {(B, A), (D, ?)} to create six queries for verifying a candidate answer D to improve the reliability of the verification process. Our experimental results on the Scholastic Aptitude Test (SAT) analogy benchmark show that the proposed method improves the accuracy of a relational search engine by a wide margin.

The theory of nominal sets is a theory for names, freshness and binders. It has recently been suggested as a framework for modelling local store because it allows for a more elementary development than the traditional presheaf models. However, when modelling the important principle of relational reasoning for local store all these models use families of relations indexed by relations on store, and thus essentially return to presheaf models on the relational level. In this paper we show how relational reasoning can also be modelled using nominal sets. Building on a model suggested by Pitts and Shinwell we construct a relational model for local store in nominal sets in which types are interpreted as relations. These relational interpretations of types capture, in a single relation for each type, the relational reasoning principle for local store which in previous models was captured using a family of relations for each type. The relational model also demonstrates how the relations constitute a model in their own right, which hopefully means that they can be used to construct better models. Using the relational model we construct a relational parametricity principle for the operation allocating local store, and we show how this implies the relational reasoning principle.

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements. On the other hand, refinement in a process algebra takes a number of different forms depending on the exact notion of observation chosen, which can include the events a system is prepared to accept or refuse.In this paper we continue our program of deriving relational simulation conditions for process algebraic refinement by defining further embeddings into our relational model: traces, completed traces, failure traces and extension.

Relational thinking plays a central role in human cognition. However, it is not known how children and adults acquire relational concepts and come to represent them in a form that is useful for the purposes of relational thinking (i.e., as structures that can be dynamically bound to arguments). The authors present a theory of how a psychologically and neurally plausible cognitive architecture can discover relational concepts from examples and represent them as explicit structures (predicates) that can take arguments (i.e., predicate them). The theory is instantiated as a computer program called DORA (Discovery Of Relations by Analogy). DORA is used to simulate the discovery of novel properties and relations, as well as a body of empirical phenomena from the domain of relational learning and the development of relational representations in children and adults.

In the real world, many phenomena are time related and in the last three decades the database community has devoted much work in dealing with "time of facts" in databases. While many approaches incorporating time in the relational model have been already devised, most of them assume that the exact time of facts is known. However, this assumption does not hold in many practical domains, in which temporal indeterminacy of facts occurs. The treatment of valid-time indeterminacy requires in-depth extensions to the current relational approaches. In this paper, we propose a theoretically grounded approach to cope with this issue, overcoming the limitations of related approaches in the literature. In particular, we present a 1NF temporal relational model and propose a new temporal relational algebra to query it. We also formally study the properties of the new data model and algebra, thus granting that our approach is interoperable with pre-existent temporal and non-temporal relational approaches, and is implementable on top of them. Finally, we consider computational complexity, showing that only a limited overhead is added when moving from determinate to indeterminate time.

Now-related temporal data play an important role in many applications. Clifford et al.’s approach is a milestone to model the semantics of ‘now’ in temporal relational databases. Several relational representation models for now-related data have been presented; however, the semantics of such representations has not been explicitly studied. Additionally, the definition of a relational algebra to query now-related data is an open problem. We propose the first integrated approach that provides both a neat semantics for now-related data and a compact 1NF representation (data model and relational algebra) for them. Additionally, our approach also extends current approaches to consider (i) domains where it is not always possible to know when changes in the world are recorded in the database and (ii) now-related data with a bound on their persistency in the future. To do so, we explicitly model the notion of temporal indeterminacy in the future for now-related data. The properties of our approach are also analyzed both from a theoretical (semantic correctness and reducibility of the algebra) and from an experimental point of view. Experiments show that, despite the fact that our approach is a major extension to current temporal relational approaches, no significant overhead is added to deal with ‘now’.

Relational lattices are obtained by interpreting lattice connectives as natural join and inner union between database relations. Our study of their equational theory reveals that the variety generated by relational lattices has not been discussed in the existing literature. Furthermore, we show that addition of just the header constant to the lattice signature leads to undecidability of the quasiequational theory. Nevertheless, we also demonstrate that relational lattices are not as intangible as one may fear: for example, they do form a pseudoelementary class. We also apply the tools of Formal Concept Analysis and investigate the structure of relational lattices via their standard contexts. Furthermore, we show that the addition of typing rules and singleton constants allows a direct comparison with the monotonic relational expressions of Sagiv and Yannakakis.

In recent years various proposals have been offered for increasing the richness of the relational data model by addressing specific user requirements, particularly with regard to structural and behavioral expressiveness. Although there have been some criticisms of the semantic limitations of the model, few proposals have emerged to address them. In this paper we propose an extension of the model to address some of the semantic limitations around the use of multi-face attributes in everyday activity. We present a formal discussion of multi-face attributes and suggest how they can be accommodated in the relational model and relational database software systems. The resulting model offers a higher-level expressiveness and will provide the user with increased flexibility in the input, output and storage of data, and the specification of queries. Finally we outline some of the implications for database design methods that emerge for the extension.

Calendars and periodicity play a fundamental role in many applications. Recently, some commercial databases started to support user-defined periodicity in the queries in order to provide "a human-friendly way of handling time" (see, e.g., TimeSeries in Oracle 8). On the other hand, only few relational data models support user-defined periodicity in the data, mostly using "mathematical" expressions to represent periodicity. In this paper, we propose a high-level "symbolic" language for representing user-defined periodicity which seems to us more human-oriented than mathematical ones, and we use the domain of Gadia's temporal elements in order to define its properties and its extensional semantics. We then propose a temporal relational model which supports user-defined "symbolic" periodicity (e.g., to express "on the second Monday of each month") in the validity time of tuples and also copes with frame times (e.g., "from 1/1/98 to 28/2/98"). We define the temporal counterpart of the standard operators of the relational algebra, and we introduce new temporal operators and functions. We also prove that our temporal algebra is a consistent extension of the classical (atemporal) one. Moreover, we define both a fully symbolic evaluation method for the operators on the periodicities in the validity times of tuples, which is correct but not complete, and semisymbolic one, which is correct and complete, and study their computational complexity.

We propose an approach for designing an object-relational database. We inspect each case of semantic relationships (one-to-one, one-to-many, many-to-many and n -ary). For each of these cases we list the different solutions for implementation and propose some solutions. We also make a comparison with the relational data model. Our results can be applied to current RDBMS including object extensions (Oracle8, DB2-IBM, Informix…).

Many problems encountered when building applications of database systems involve the manipulation of models. By "model," we mean a complex structure that represents a design artifact, such as a relational schema, object-oriented interface, UML model, XML DTD, web-site schema, semantic network, complex document, or software configuration. Many uses of models involve managing changes in models and transformations of data from one model into another. These uses require an explicit representation of "mappings" between models. We propose to make database systems easier to use for these applications by making "model" and "model mapping" first-class objects with special operations that simplify their use. We call this capability model management.In addition to making the case for model management, our main contribution is a sketch of a proposed data model. The data model consists of formal, object-oriented structures for representing models and model mappings, and of high-level algebraic operations on those structures, such as matching, differencing, merging, selection, inversion and instantiation. We focus on structure and semantics, not implementation.

In this paper, we present the concept of relational patterns and our approach to extract them from multiple relational tables. Relational patterns are analogous to frequent itemsets extracted by the Apriori algorithm [R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, A.I. Verkamo, Advances in Knowledge Discovery and Data Mining, AAAI Press, 1995.] in the case of a single table. However, for the multiple relational tables, relational patterns capture co-occurrences of attributes as well as the relationships between these attributes, which are essential to avoid information loss. We describe our experiences from a test-bed implementation of our approach on a real hospital's discharge abstract database. This process raised issues, which were then implemented in order to enhance an analyst's ability to explore patterns while preventing high diversity and abundance of available data from blurring subtle patterns of interest. Finally, we evaluate the usefulness of relational patterns in the context of the discharge abstract data as well in other possible domains.

An extended relational model without semantic ambiguity, called a semantic-ambiguity-free relational model, is proposed using fuzzy sets and the theory of possibility. The model features every attribute having a membership attribute whose value consists of a pair of values based on necessity and possibility measures. The membership attribute value of an attribute in a base relation is the degree to which the attribute value is compatible with integrity constraints imposed on the base relation. This clarifies the source of the membership attribute value. The model has no semantic ambiguity for interpreting membership attribute values, unlike models consisting of relations with membership attribute values attached to tuple values. We show the formulation of 8 operations - union, intersection, difference, Cartesian product, projection, join, selection, and quotient - consisting of relational algebra proposed by Codd for query processing. This approach shows how to prevent users from misinterpreting tuples in databases allowing imperfect information.

Currently, most database management systems (DBMS) are based on the relational data model. Design methods that target relational models as the end product of logical design are generally based on the entity relationship model (ER) or semantic object model. Such methods entail developing an ER or semantic object representation followed by translation to the relational representation by the designer or by a CASE tool. However, there is no popular method that uses the relational concepts directly, that is, without an intermediate representation such as ER. Mathematically rigorous approaches using decomposition or synthesis do not seem to have been adopted by designers. When user views are complex, designers may encounter difficulty in the absence of an understandable method. This paper suggests a practical method for arriving at a normalized solution of user views.

We apply the established relational theory of stored data to the management of propositions in two-valued logic. Since the truth table for a propositional formula is a virtual relation, we can establish a correspondence between the relational algebra, as applied to the management of stored data, and the same algebra, as applied to the management of logical formulas. In doing so, we present a single comprehensive framework for the management of these two types of information.

Expression and processing of vagueness, which has many real world applications, are not handled effectively in the conventional relational data model. In this paper we investigate a fuzzy extension to the relational data model and propose three fuzzy relational query languages. Two of them are the Level-1 Fuzzy Relational Algebra and Level-1 Fuzzy Relational Calculus . They are fundamental query languages and serve as a theoretical framework for the fuzzy relational database. Finally, the Fuzzy Selective Relational Algebra is presented to express fuzzy constants and fuzzy comparators, which are more effective to represent vagueness in user queries. We show that the three proposed query languages have the same expressive powers. We also present various aspects of the proposed model and its functional advantages over the conventional relational data model.

Relational search is a novel paradigm of search which focuses on the similarity between semantic relations. Given three words (A, B, C) as the query, a relational search engine retrieves a ranked list of words D, where a word D ∈ D is assigned a high rank if the relation between A and B is highly similar to that between C and D. However, if C and D has numerous co-occurrences, then D is retrieved by existing relational search engines irrespective of the relation between A and B. To overcome this problem, we exploit the symmetry in relational similarity to rank the result set D. To evaluate the proposed ranking method, we use a benchmark dataset of Scholastic Aptitude Test (SAT) word analogy questions. Our experiments show that the proposed ranking method improves the accuracy in answering SAT word analogy questions, thereby demonstrating its usefulness in practical applications.

Data exchange has been defined as the problem of taking data structured under a source schema and materializing an instance of a target schema that reflects as accurately as possible the source data [19]. In the last years, the need for data exchange applications has increased, particularly due to the proliferation of web data in various formats (relational, XML, RDF, etc) and the emergence of e-business applications that need to communicate data yet remain autonomous. Responding to this demand, commercial data exchange systems have been built recently [12]. Even though data exchange is an old and common data management problem, its most foundational aspects had not been studied until very recently. There are two reasons for this. First, most of the early research on databases concentrated on the stand-alone relational model, and much less on interoperability, integration, and exchange. Second, there were no solid foundation, nor even a proper formal model, for the problem of data exchange. Such a model was finally proposed in 2003 by Fagin, Kolaitis, Miller and Popa [19], and was quickly adopted as the right model for data exchange. A survey on the topic has already appeared in the premier conference on database theory, PODS, [30], and two workshops on exchange and integration of data have already been held [10, 39]. This survey is organized as follows. In Section 2, we present the basics of data exchange. One of the goals of data exchange is materializing a target instance that is consistent both with the source data and the specification of the relationship between the source and the target. Such a target instance is called a solution for the given source data. The work of Fagin et al. [19] identified a class of solutions, called universal solutions, with good properties for data exchange. We introduce the class of universal solutions in Section 3. In Section 4, we study the problem of the materialization of universal solutions. In particular, we show that there is a meaningful class of data exchange settings for which universal solutions are guaranteed to exist, if a solution exists at all, and, if that is the case, then a universal solution can always be constructed in polynomial time. Also in Section 4 we study the core of the universal solutions, which happens to be the smallest universal solution.

Many methods are available for computing semantic similarity between individual words, but certain NLP tasks require the comparison of word pairs. This paper presents a kernel-based framework for application to relational reasoning tasks of this kind. The model presented here combines information about two distinct types of word pair similarity: lexical similarity and relational similarity. We present an efficient and flexible technique for implementing relational similarity and show the effectiveness of combining lexical and relational models by demonstrating state-of-the-art results on a compound noun interpretation task.

Problems associated with defining normal forms of relational tables relevant to statistical processing are discussed. The concepts of derived identifier, class identifier, derived class-counts, count domains, compact domains, and uniform domains for statistical relational tables are introduced. The structures of the first and the second statistical-normal forms and the relational decompositions needed to achieve them are also discussed. It is shown that the statistical-normal form can be an important method to determine whether the usual statistical analysis techniques are valid. Some suggestions are presented for extending the structured query language (SQL) statements to achieve these operations on statistical relational tables. Some results linking Codd's normal forms with statistical normal forms are discussed. Relational statistical abnormalities, called outlyers, are also discussed. >

Recently there has been a considerable interest in extending the relational model of data, in order to make it useful for data modeling in the context of nonstandard applications of database systems. As a result, a variety of models has been proposed, which concur in allowing more structure, complex objects, recursion, or other aspects within relational databases. However, no consensus has been reached yet on how general such an extension should be, or which model is the ‘best’ in the sense that it may become the ‘sucessor’ of the relational model. While answers to both questions probably depend on the respective application, this paper is an attempt to unify notable extended relational models into a common framework, the SUXESS model, in order to clarify the situation and to explore the current modeling power of these approaches.

Exploiting the complex structure of relational data enables to build better models by taking into account the additional information provided by the links between objects. We extend this idea to the Semantic Web by introducing our novel SPARQL-ML approach to perform data mining for Semantic Web data. Our approach is based on traditional SPARQL and statistical relational learning methods, such as Relational Probability Trees and Relational Bayesian Classifiers. We analyze our approach thoroughly conducting three sets of experiments on synthetic as well as real-world data sets. Our analytical results show that our approach can be used for any Semantic Web data set to perform instance-based learning and classification. A comparison to kernel methods used in Support Vector Machines shows that our approach is superior in terms of classification accuracy.

Artificial intelligence aims at developing agents that learn and act in complex environments. Realistic environments typically feature a variable number of objects, relations amongst them, and non-deterministic transition behavior. Standard probabilistic sequence models provide efficient inference and learning techniques, but typically cannot fully capture the relational complexity. On the other hand, statistical relational learning techniques are often too inefficient. In this paper, we present a simple model that occupies an intermediate position in this expressiveness/efficiency trade-off. It is based on CP-logic, an expressive probabilistic logic for modeling causality. However, by specializing CP-logic to represent a probability distribution over sequences of relational state descriptions, and employing a Markov assumption, inference and learning become more tractable and effective. We show that the resulting model is able to handle probabilistic relational domains with a substantial number of objects and relations. acceptance rate = 16% ispartof: pages:506-521 ispartof: Lecture Notes in Computer Science vol:5212 issue:PART 2 pages:506-521 ispartof: 19th European Conference on Machine Learning location:Antwerp, Belgium date:15 Sep - 19 Sep 2008 status: published

The fuzzy relational database model proposed by Buckles and Petry is a formal method for organizing and using fuzzy information in relational databases. The model possesses two key properties that hold for classical relational databases: no two tuples have identical interpretations and each relational algebra operation has a unique result. The original fuzzy relational database model was based on similarity relations which were defined on finite scalar domains. Buckles and Petry later extended the model to incorporate fuzzy number domains; this extension was done without loss of consistency with the representation or the relational algebra. In a recent paper we have extended the original model to proximity relations which generalize similarity relations; the key properties of Buckles and Petry's model are preserved in the extension. In this work we demonstrate that the existence of partitions on finite scalar domains in the fuzzy relational model is the key to preserving the important properties of the classical relational model. We explain how proximity relations defined on finite scalar domains are used to partition the domains. Further, we show that normal fuzzy sets can be employed as domain values. These fuzzy sets become members of fi nite scalar domains and their characteristic functions are employed in generating the proximity relations of the fuzzy relational database model.

A major obstacle to fully integrated deployment of many data mining algorithms is the assumption that data sits in a single table, even though most real-world databases have complex relational structures. We propose an integrated approach to statistical modelling from relational databases. We structure the search space based on "refinement graphs", which are widely used in inductive logic programming for learning logic descriptions. The use of statistics allows us to extend the search space to include richer set of features, including many which are not Boolean. Search and model selection are integrated into a single process, allowing information criteria native to the statistical model, for example logistic regression, to make feature selection decisions in a step-wise manner. We present experimental results for the task of predicting where scientific papers will be published based on relational data taken from CiteSeer. Our approach results in classification accuracies superior to those achieved when using classical "flat" features. The resulting classifier can be used to recommend where to publish articles.

Model induction from relational data requires aggregation of the values of attributes of related entities. This paper makes three contributions to the study of relational learning. (1) It presents a hierarchy of relational concepts of increasing complexity, using relational schema characteristics such as cardinality, and derives classes of aggregation operators that are needed to learn these concepts. (2) Expanding one level of the hierarchy, it introduces new aggregation operators that model the distributions of the values to be aggregated and (for classification problems) the differences in these distributions by class. (3) It demonstrates empirically on a noisy business domain that more-complex aggregation methods can increase generalization performance. Constructing features using target-dependent aggregations can transform relational prediction tasks so that well-understood feature-vector-based modeling algorithms can be applied successfully.

The relational model and its extensions are often considered incompatible with object-orientation. However, on the one hand nested relations provide the complex object features demanded by object models. Particularly, powerful query languages exploit the complex data structure while keeping the advantages of the declarative, set-oriented paradigm. On the other hand, object models provide semantically rich constructs for advanced modeling, and abstractions of operations as well as data. In this paper, we show an evolutionary path from relational, essentially nested relational, to object-oriented data models and query languages. Basically, allowing nested relation schemes to be recursively defined yields the necessary flexibility w.r.t structure. The query language, i.e., nested relational algebra, carries over to this ldquonetworkrdquo model. As a first step towards the object-oriented integration of cooperative systems, different views onto the objects have to be supported. We present a powerful view definition facility that basically allows object views as well as relational views to be defined in our object algebra.

The aim of this paper is to present the results of an investigation in so-called relational retrieval languages. These languages are often used by non-programmers employing as information model or external schema the normalized relational model. The relational retrieval languages known to the author contain two aspects which are specially inconvenient for a non-mathematician, namely in the majority of non-trivial questions one needs a long and complicated query formulation and the forced use of variables. In this paper a relational retrieval language will be discussed, which offers a solution to avoid these inconveniences.

The designer of a relational data base must use dependency structures of data to model semantic situations that arise in data. He must further ensure that these dependencies are not violated during operations on the data base. In this paper we study a subclass of dependencies, namely, root-dependencies and introduce a common graphical picture (S-diagram) for all of them. This effort offers a possible application of graph theory to the study of relational data bases. The S-diagram offers a pictorial insight to all the root-dependencies. We also discuss, briefly, other possible uses of our work such as automatic constraint checking and recovery of data in a damaged data base.

This paper outlines the motivation for and the basic concepts on which relational-product architectures are built. The examples of relational expressions given here were chosen rather to demonstrate the great power of unification of relational representations across the seemingly unrelated branches of information processing, than to give technical details, which can be found elsewhere. Because the relational products can also capture the classical, probabilistic, and fuzzy inference in a unified form, the architectures are particularly suitable for implementation of intelligent knowledge based and expert systems. Relational is used here in the sense of mathematical crisp and fuzzy relations. Codd's relational forms used in data-base design can be viewed as rather special subspecies of mathematical relations; their properties and construction can be also expressed by relational products. However, they are only very special instances of relational structures, and our approach presents a much wider repertory of structures and algorithms for their manipulation.

Since the introduction of the relational data model, relational algebra has been used to gauge the completeness of relational query languages. As a concise language for formulating queries against relational databases, relational algebra is unmatched. Furthermore, human factor studies have shown that for difficult queries, users perform better using the procedurally-oriented relational algebra than using a non-procedural, specification-based, language such as SQL. Still, the current implementations of relational algebra in database management systems are not “friendly” when it comes to formulation of queries involving universal quantification. The algebraic operation of division normally used for this purpose is difficult for most users to comprehend and work with and is incapable of expressing queries that demand the comparison of sets of values associated with matching groups of tuples in two relations. This paper introduces a new algebraic operation, called grouped generalized division (GGD), which overcomes such shortcomings. We also show how the GGD operation can be expressed in terms of the other more “primitive” algebraic operations. As such, the implementors of algebraic languages can support the GGD operation at the user interface with minimal effort.

Motivated by new applications of database systems we introduce relations which may have relation-valued attributes and propose a related algebra. Formal definitions for this extended relational model can be given by applying usual notions recursively. The main problem considered in this paper is the formal definition of an appropriate relational algebra for these non-first-normal-form relations. We allow the application of the basic relational operators to any relation-valued attribute within a relation. This leads to a (hierarchically) nested relational algebra.

This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied in a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by using a specified subset Ω of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in Ω are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, positive selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a conditional table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions containing arbitrarily many different relation symbols, and no form of the universal relation assumption is required. Categories and Subject Descriptors: H.2.3 [Database Management]: Languages— query languages; H.2.4 [Database Management]: Systems— query processing General Terms: Theory

The relationship between semantic data models and object-oriented database systems is examined. In particular, it is described how the Aspect Project has taken a semantic data model (the extended relational model RM(T) and, with the addition of an abstraction mechanism, moved towards providing an object-oriented database as the basis of an integrated project support environment (IPSE).

We present a relational representation of diagrams which accommodates the three fundamental categories of graphical object: points, lines and regions, uniformly. This representation permits a large variety of queries and processes to be performed on the graphical data using the extended relational algebra. We describe a relational picture editor, which we have implemented, which creates the diagrams in the first place and allows them to be displayed and modified. We discuss a low-level data structure, based on dynamic multipaging, which combines the best of the polygon and the pixel representations of pictures, and we examine the interactions of this data structure with the relational representation.

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution. Activities of users at terminals and most application programs should remain unaffected when the internal representation of data is changed and even when some aspects of the external representation are changed. Changes in data representation will often be needed as a result of changes in query, update, and report traffic and natural growth in the types of stored information. Existing noninferential, formatted data systems provide users with tree-structured files or slightly more general network models of the data. In Section 1, inadequacies of these models are discussed. A model based on n -ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced. In Section 2, certain operations on relations (other than logical inference) are discussed and applied to the problems of redundancy and consistency in the user's model.

It is shown how the theory of cylindric algebras (a notion introduced by Tarski and others as a tool in the algebraization of the first order predicate calculus) can give a new insight into Codd's relational model of data. The relational algebra of Codd can be embedded in a natural way into a cylindric algebra where the join operation becomes the usual set-theoretical intersection. It is shown, by using known facts from the theory of cylindric algebras, that a version of the relational algebra is not finitely axiomatizable and that the equivalence problem for certain relational expressions is undecidable. A duality between the project-join and selectunion operator pairs is also briefly discussed.

E.F. Codd's (1970) relational view is extended to represent statistical data and to achieve its analysis. A new view called a statistical relational table is presented to meet the needs of statisticians, and some of Codd's relational operators are extended to statistical relational tables. New operators based on these tables are introduced for communicating requests for statistical analysis. A new query language called the query-by-statistical-relational-table (which has some similarities to query-by-example) is introduced. Extensions of the SQL language for processing the commands of the new query language are also discussed. Creation and storage of metadata for fast statistical analysis are considered. Some problems related to privacy in statistical databases are also examined.

The relational model of data bases is studied from three interdependent viewpoints. Relational data bases are first modelled by directed hypergraphs, a concept derived in a straightforward way from Berge's hypergraph theory. Then the abstract directed hypergraphs are interpreted using a linguistic model, and finally are represented as a necessary step towards computer implementation. The normalization of relations is briefly discussed in the context of the three approaches.

Relational models are commonly used in scene analysis systems. Most such systems are experimental and deal with only a small number of models. Unknown objects to be analyzed are usually sequentially compared to each model. In this paper, we present some ideas for organizing a large database of relational models. We define a simple relational distance measure, prove it is a metric, and using this measure, describe two organizational/access methods: clustering and binary search trees. We illustrate these methods with a set of randomly generated graphs.

Two important issues in the design of relational model banks are the degree to which they should be aggregated or disaggregated and the methods by which disaggregated model banks might be integrated in response to user queries. Three topics relevant to this issue are addressed in this paper. The first is whether a universal model and its projections may possess the lossy join property. We will show that they do not. The second is the development of a relational algebra for the specification of join implementation in model banks, and the third is the realization of such an algebra in a language similar to Query-by-Example.

Vector representation is a common approach for expressing the meaning of a relational pattern. Most previous work obtained a vector of a relational pattern based on the distribution of its context words (e.g., arguments of the relational pattern), regarding the pattern as a single ‘word’. However, this approach suffers from the data sparseness problem, because relational patterns are productive, i.e., produced by combinations of words. To address this problem, we propose a novel method for computing the meaning of a relational pattern based on the semantic compositionality of constituent words. We extend the Skip-gram model (Mikolov et al., 2013) to handle semantic compositions of relational patterns using recursive neural networks. The experimental results show the superiority of the proposed method for modeling the meanings of relational patterns, and demonstrate the contribution of this work to the task of relation extraction.

We propose a novel framework for generating classification rules from relational data. This is a specialized version of the general framework intended for mining relational data and is defined in granular computing theory. In the framework proposed in this paper we define a method for deriving information granules from relational data. Such granules are the basis for generating relational classification rules. In our approach we follow the granular computing idea of switching between different levels of granularity of the universe. Thanks to this a granule-based relational data representation can easily be replaced by another one and thereby adjusted to a given data mining task, e.g. classification. A generalized relational data representation, as defined in the framework, can be treated as the search space for generating rules. On account of this the size of the search space may significantly be limited. Furthermore, our framework, unlike others, unifies not only the way the data and rules to be derived are expressed and specified, but also partially the process of generating rules from the data. Namely, the rules can be directly obtained from the information granules or constructed based on them.

This paper decribes a computational treatment of the semantics of relational nouns. It covers relational nouns such as "sister" and "commander", and focuses especially on a particular subcategory of them, called function nouns ("speed", "distance", "rating"). Relational nouns are usually viewed as either requiring non-compositional semantic interpretation, or causing an undesirable proliferation of syntactic rules. In contrast to this, we present a treatment which is both syntactically uniform and semantically compositional. The core ideas of this treatment are: (1) The recognition of different levels of semantic analysis; in particular, the distinction between an English-oriented and a domain-oriented level of meaning representation. (2) The analysis of relational nouns as denoting relation-extensions.The paper shows how this approach handles a variety of linguistic constructions involving relational nouns. The treatment presented here has been implemented in BBN's Spoken Language System, an experimental spoken language interface to a database/graphics system.

The commenter contends that the universal-relation data model proposed in the above mentioned paper (ibid., vol.5, no.2, p.80-5, Mar. 1988) fails completely as an alternative to the relational data model, and presents supporting arguments. The author replies that the commenter has read into the article claims that are not there and rebuts the commenters arguments point by point. >