Logic-based query optimization for object databases

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method     

The Relationlog system prototype

The Relationlog system is a novel persistent deductive database system for advanced data and knowledge‐based applications. It directly supports the storage and inference of data with complex structures, especially data supported in nested relational and complex‐object models. The Relationlog system supports the Relationlog query language, which is a typed extension of Datalog with tuples and sets and stands in the same relationship to the nested relational and complex‐object models as Datalog stands to the relational model. It also supports an SQL‐like data definition language and a declarative data manipulation language. This article introduces the Relationlog language, discusses the system architecture, the design decisions incorporated within its implementation, and our experience in developing the system. Copyright © 2001 John Wiley & Sons, Ltd.     

Datalog extension for nested relations

The nested relational model allows relations that are not in first normal form. This paper gives an extension of Datalog rules for nested relations. In our approach, nested Datalog is a natural extension of Datalog introduced for the relational data model. A nested Datalog program has a hierarchical structure of rules and subprograms to manipulate relation values of nested relations. We introduce a new category of predicate symbols, the variable predicate symbols to refer to tuples of subrelations. The notion of soundness, safety and consistency is defined to avoid undesirable nested Datalog programs. The evaluation of nested Datalog is given in terms of the nested relational algebra. Finally, we relate the expressive power of nonrecursive nested Datalog to the power of nested relational algebra and safe nested tuple relational calculus.     

Index configuration in object-oriented databases

In relational databases, an attribute of a relation can have only a single primitive value, making it cumbersome to model complex objects. The objectoriented paradigm removes this difficulty by introducing the notion of nested objects, which allows the value of an object atribute to be another object or a set of other objects. This means that a class consists of a set of attributes, and the values of the attributes are objects that belong to other classes; that is, the definition of a class forms a hierarchy of classes. All attributes of the nested classes are nested attributes of the root of the hierarchy. A branch of such hierarchy is called apath. In this article, we address the problem of index configuration for a given path. We first summarize some basic concepts, and introduce the concept of index configuration for a path. Then we present cost formulas to evaluate the costs of the various configurations. Finally, we present the algorithm that determines the optimal configuration, and show its correctness.     

A semantic framework and software design to enable the transparent integration,reorganization and discovery of natural systems knowledge

I present a conceptualization that attempts to unify diverse representations of natural knowledge while providing a workable computational framework, based on current semantic web theory, for developing, communicating, and running integrated simulation models. The approach is based on a long-standing principle of scientific investigation: the separation of the ontological character of the object of study from the semantics of the observation context, the latter including location in space and time and other observation-related aspects. I will show how current Knowledge Representation theories coupled with the object-oriented paradigm allow an efficient integration through the abstract model of a domain, which relates to the idea of aspect in software engineering. This conceptualization allows us to factor out two fundamental causes of complexity and awkwardness in the representation of knowledge about natural system: (a) the distinction between data and models, both seen here as generic knowledge sources; (b) the multiplicity of states in data sources, handled through the hierarchical composition of independently defined domain objects, each accounting for all states in one well-known observational dimension. This simplification leaves modelers free to work with the bare conceptual bones of the problem, encapsulating complexities connected to data format, and scale. I will then describe the design of a software system that implements the approach, referring to explicit ontologies to unambiguously characterize the semantics of the objects of study, and allowing the independent definition of a global observation context that can be redefined as required. I will briefly discuss applications to multi-scale, multi-paradigm modeling, intelligent database design, and web-based collaboration.     

Fast relational learning using bottom clause propositionalization with artificial neural networks

Relational learning can be described as the task of learning first-order logic rules from examples. It has enabled a number of new machine learning applications, e.g. graph mining and link analysis. Inductive Logic Programming (ILP) performs relational learning either directly by manipulating first-order rules or through propositionalization, which translates the relational task into an attribute-value learning task by representing subsets of relations as features. In this paper, we introduce a fast method and system for relational learning based on a novel propositionalization called Bottom Clause Propositionalization (BCP). Bottom clauses are boundaries in the hypothesis search space used by ILP systems Progol and Aleph. Bottom clauses carry semantic meaning and can be mapped directly onto numerical vectors, simplifying the feature extraction process. We have integrated BCP with a well-known neural-symbolic system, C-IL²P, to perform learning from numerical vectors. C-IL²P uses background knowledge in the form of propositional logic programs to build a neural network. The integrated system, which we call CILP++, handles first-order logic knowledge and is available for download from Sourceforge. We have evaluated CILP++ on seven ILP datasets, comparing results with Aleph and a well-known propositionalization method, RSD. The results show that CILP++ can achieve accuracy comparable to Aleph, while being generally faster, BCP achieved statistically significant improvement in accuracy in comparison with RSD when running with a neural network, but BCP and RSD perform similarly when running with C4.5. We have also extended CILP++ to include a statistical feature selection method, mRMR, with preliminary results indicating that a reduction of more than 90 % of features can be achieved with a small loss of accuracy.     

Acquiring object-knowledge

Abstract

A novel approach to interactively acquire knowledge about new objects in a logic environment is presented. When the user supplies an unknown fact containing unknown objects (constants), the system will ask interesting membership and existential queries about the objects. The answers to these questions allow the system to update its knowledge base. Two basic strategies are implemented: one that examines existing Horn clauses for the predicate and another one that uses types. Furthermore, a powerful heuristic based on analogy, to pose the most interesting questions first, is presented.     

Querying sequence databases with transducers

This paper develops a database query language called Transducer Datalog motivated by the needs of a new and emerging class of database applications. In these applications, such as text databases and genome databases, the storage and manipulation of long character sequences is a crucial feature. The issues involved in managing this kind of data are not addressed by traditional database systems, either in theory or in practice. To address these issues, we recently introduced a new machine model called a generalized sequence transducer. These generalized transducers extend ordinary transducers by allowing them to invoke other transducers as “subroutines.” This paper establishes the computational properties of Transducer Datalog, a query language based on this new machine model. In the process, we develop a hierarchy of time-complexity classes based on the Ackermann function. The lower levels of this hierarchy correspond to well-known complexity classes, such as polynomial time and hyper-exponential time. We establish a tight relationship between levels in this hierarchy and the depth of subroutine calls within Transducer Datalog programs. Finally, we show that Transducer Datalog programs of arbitrary depth express exactly the sequence functions computable in primitive-recursive time. Received: 12 March 1998 / 30 August 1999     

What you always wanted to know about Datalog (and never dared toask)

Datalog, a database query language based on the logic programming paradigm, is described. The syntax and semantics of Datalog and its use for querying a relational database are presented. Optimization methods for achieving efficient evaluations of Datalog queries are classified, and the most relevant methods are presented. Various improvements of Datalog currently under study are discussed, and what is still needed in order to extend Datalog's applicability to the solution of real-life problems is indicated     

Foundations for object-oriented query processing

A minimal framework for an object-oriented query language standard should (1) include a formal definition of a high-level data model and the syntax and semantics of associated query languages, (2) provide the functionality of relational query languages, and (3) support proofs of correctness of transformations for logical query optimization. In this paper, a high-level conceptual model for object-oriented query processing is discussed; the model includes widely-used structural abstractions such as the isa relationship, associations (properties) between complex objects and complex objects/values, and inheritance of properties. A formal, algebraic query language for the model, inspired by relational algebra, is presented. Operators of the algebra allow queries based on values, queries that manipulate entire objects, and queries that construct new objects from existing objects/values. All queries retain connections to existing database objects, providing logical access paths to data. Each query result is a class, so the algebra has the closure property. The intensional and extensional results of query operators are summarized. Two forms of logical query optimization supported by the query algebra are outlined: algebraic transformations and classifier-based optimizations (optimizations which employ inclusion and exclusion dependencies between classes).     

A Note on Complexity Measures for Inductive Classes in Constructive Type Theory

It is notoriously hard to express computational complexity properties of programs in programming logics based on a semantics which respects extensional function equality. That is a serious impediment to applications of programming logics requiring reasoning about complexity. This paper shows how to use existing mechanisms to define internal computational complexity measures in logics that support inductively defined types, dependent products, and functions. The method exploits a feature of inductive definitions in constructive type theory, namely that implicit proof codes are kept with the objects showing how they are presented in the inductive class. The idea is illustrated by giving a formal inductive definition ofPTimebased on ideas from Leivant's work and on Bellantoni and Cook's approach. Then a complexity measure is defined on elements of this class. This paper discusses the limitations of this idea and the need forfaithfulnessguarantees that link internal complexity classes to the implementation of the logic. The paper concludes with a definition ofresource bounded logicsand a discussion of interesting lines of investigation of these logics which have the potential to make practical uses of results from computational complexity theory in formal reasoning about the efficiency of programs.     

Extensions to SQL for historical databases

A historical management system (HDBMS) is described which uses an extended relational data model with state-oriented, instead of `cubic', conceptualization. Two types of historical relations, called state and event relations, are provided for modeling real-world objects. The query language SQL has been extended for definition, retrieval, and update of historical relations. The extended SQL, called HSQL, is a superset of SQL. The author defines a few primitive algebra operations for historical relations, and uses them as a basis for extensions to SQL. In this way, HSQL retains the elegant structural and algebraic framework of SQL. HSQL contains a few new clauses, many operations and built-in functions on time domain, and facilities for retrospective updates and time-rollback     

A set‐oriented method definition language for object databases and its semantics

In this paper we propose a set‐oriented rule‐based method definition language for object‐oriented databases. Most existing object‐oriented database systems exploit a general‐purpose imperative object‐oriented programming language as the method definition language. Because methods are written in a general‐purpose imperative language, it is difficult to analyze their properties and to optimize them. Optimization is important when dealing with a large amount of objects as in databases. We therefore believe that the use of an ad hoc, set‐oriented language can offer some advantages, at least at the specification level. In particular, such a language can offer an appropriate framework to reason about method properties. In this paper, besides defining a set‐oriented rule‐based language for method definition, we formally define its semantics, addressing the problems of inconsistency and non‐determinism in set‐oriented updates. Moreover, we characterize some relevant properties of methods, such as conflicts among method specifications in sibling classes and behavioral refinement in subclasses. Copyright © 2003 John Wiley & Sons, Ltd.     

Volumetric Billboards

We introduce an image‐based representation, called volumetric billboards, allowing for the real‐time rendering of semi‐transparent and visually complex objects arbitrarily distributed in a 3D scene. Our representation offers full parallax effect from any viewing direction and improved anti‐aliasing of distant objects. It correctly handles transparency between multiple and possibly overlapping objects without requiring any primitive sorting. Furthermore, volumetric billboards can be easily integrated into common rasterization‐based renderers, which allows for their concurrent use with polygonal models and standard rendering techniques such as shadow‐mapping. The representation is based on volumetric images of the objects and on a dedicated real‐time volume rendering algorithm that takes advantage of the GPU geometry shader. Our examples demonstrate the applicability of the method in many cases including levels‐of‐detail representation for multiple intersecting complex objects, volumetric textures, animated objects and construction of high‐resolution objects by assembling instances of low‐resolution volumetric billboards.     

Integrated implementation of dynamic untyped object‐based operator overloading

Operator overloading, a popular mechanism in the C++ language, is a form of ad hoc polymorphism on operator functions, allowing alternative implementations for different argument types. Classless languages with untyped objects are languages that lack classes and treat all objects as compliant to a common Object type. Languages in this category are flexible, dynamic, and easy‐to‐use, with popular examples being JavaScript, Lua, and ActionScript (the latter being hybrid by also offering classes). This paper presents an integrated implementation of untyped operator overloading which enable users to handle dynamically the full range of operators on objects. The focus is on features not supported by other languages, such as (i) arithmetic and relational operators allowing to separately handle caller lhs and rhs positions; (ii) an assignment operator with an untyped analogy of type casting; (iii) a slot access operator allowing user‐defined policies for editing object slots; and (iv) a function‐call operator to support functors. Operators are treated as first‐class object slots, distinguished by reserved indices that match the respective operator lexemes. All reported techniques have been applied in implementing the operator overloading features of the Delta language. Copyright © 2010 John Wiley & Sons, Ltd.     

An object design framework for structural engineering

Object-oriented principles have introduced several useful concepts for developing complex software systems. As a result, several methodologies have been suggested for the overall design of software systems based on these concepts. Methodologies and frameworks for designing objects that are to be part of the software systems are currently lacking. This paper proposes anobject design framework andmethodology, which utilizes the object-oriented concepts, for planning, organizing and designing structural engineering design objects. Design objects in an integrated structural engineering system are complex and often related to each other in various different ways. The paper also identifies several important relationships among structural engineering design objects. These relationships serve as communication channels through wich design objects send messages to and receive responses from each other. Several examples, drawn from reinforced concrete structures, will be presented to demonstrate the object design methodology and to illustrate how the framework is effective in reducing the complexity of design objects in an integrated structural engineering system.     

An Overview of the Rule-Based Object Language

This paper presents an overview of a novel strongly typed deductive object database language, called Rule-based Object Language, which is being developed at the University of Regina. Rule-based Object Language is a uniform language for defining, querying, and manipulating a database, which integrates important features of deductive databases and object databases. It supports object identity, complex objects, classes, class hierarchies, multiple inheritance with overriding and blocking, and schema definition. It also supports structured values such as functor objects and sets, treating them as first class citizens and providing powerful mechanisms for representing both partial and complete information about sets. Important integrity constraints such as domain, referential, functional dependency, multi-valued dependency, and cardinality are built-in in a uniform framework. Rule-based Object Language directly supports non-first normal form relations and is an extension of the pure valued-oriented deductive languages such as Datalog and LDL (without grouping) and subsumes them as special cases. It supports schema, object, fact and rule queries in a uniform framework. It also supports schema, fact and rule updates.     

Querying datalog programs with temporal logic

Temporal logic queries on Datalog and negated Datalog programs are studied, and their relationship to Datalog queries on these programs is explored. It is shown that, in general, temporal logic queries have more expressive power than Datalog queries on Datalog and negated Datalog programs. It is also shown that anexistential domain-independent fragment of temporal logic queries has the same expressive power as Datalog queries on negated Datalog programs with inflationary semantics. This means that for finite structures this class of queries has the power of the fixpoint logic.     

Concept Formation During Interactive Theory Revision

This article examines the problem of concept formation in machine learning, and focuses in particular on the problem of aggregation, i .e., the decision of which objects are to be grouped together into a new concept. While existing concept formation approaches have mainly concentrated on aggregation constraints that rely on structural or correlational properties of the concepts themselves, we argue that in an integrated learning system, other learning activities can provide an additional context that focuses concept formation before structural criteria are applied. In particular, we present the concept formation method realized by the KRT and CLT components of the integrated learning system MOBAL. In MOBAL, a concept formation attempt is triggered whenever no existing concept can adequately capture the rule instance and exception sets as they arise from the theory revision activities of the system. We describe how the so-proposed aggregate is characterized by a set of (function-free) first-order Horn clauses and how these are evaluated according to structural criteria to decide about the introduction of the concept into the representation. We show how a structural criterion can be used to ensure that any new concept improves the structure of the knowledge base, and we empirically evaluate how the introduction of new concepts according to different criteria affects the classification accuracy of learned rules.