Graph Databases are gaining popularity, owing to pervasiveness of graph data in social networks, physical sciences, networking, and web applications. A majority of these databases are based on the property graph model, which is characterized as key/value-based, directed, and multi-relational. In this paper, we consider the problem of supporting property graphs as RDF in Oracle Database. We introduce a property graph to RDF transformation scheme. The main challenge lies in representing the key/value properties of property graph edges in RDF. We propose three models: 1) named graph based, 2) subproperty based, and 3) (extended) reification based, all of which can be supported with RDF capabilities in Oracle Database. These models are evaluated with respect to ease of SPARQL query formulation, join complexities, skewness in generated RDF data, query performance, and storage overhead. An experimental study with a real-life Twitter social network dataset on Oracle Database 12c demonstrates the feasibility of representing property graphs as RDF and presents a quantitative performance comparison of the proposed models.

This paper describes the Semantic Indexing feature introduced in Oracle Database for indexing unstructured text (document) columns. This capability enables searching for concepts (such as people, places, organizations, and events), in addition to words or phrases, with further options for sense disambiguation and term expansion by consulting knowledge captured in OWL/RDF ontologies. The distinguishing aspects of our approach are: 1) Indexing: Instead of building a traditional inverted index of (annotated) token and/or named entity occurrences, we extract the entities, associations, and events present in a text column data and store them as RDF named graphs in the Oracle Database Semantic Store. This base content can be further augmented with knowledge bases and inferred triples (obtained by applying domain-specific ontologies and rule bases). 2) Querying: Instead of relying on proprietary extensions for specifying a search, we allow users to specify a complete SPARQL query pattern that can capture arbitrarily complex relationships between query terms. We have implemented this feature by introducing a sem_contains SQL operator and the associated sem_indextype indexing scheme. The indexing scheme employs an extensible architecture that supports indexing of unstructured text using native as well as third party text extraction tools. The paper presents a model for the semantic index and querying, describes the feature, and outlines its implementation leveraging Oracle's native support for RDF/OWL storage, inferencing, and querying. We also report a study involving use of this feature on a TREC collection of over 130,000 news articles.

Although the notion of time-constrained query was first introduced two decades ago to address the problem of long running SQL queries, none of the commercial database systems support such a feature. This is rather surprising given the fact that database systems are beginning to accommodate large datasets in the order of terabytes to petabytes. Thus, the long running SQL query problem needs to be addressed. Recently, at Oracle we investigated and proposed a mechanism of supporting time-constrained quenes to provide quick approximate answers by use of sampling for such long running SQL quenes. This we followed up by coming up with error estimates as a measure of goodness for the approximation. To further validate our time-constrained query work, in this paper we present an experimental study conducted on our time-constrained query prototype built on the Oracle Database. It is our hope that this work will revive interest in time-constrained queries.

The paper addresses the problem of visualizing large scale RDF data via a 3-S approach, namely, by using, (1) Subsets: to present only relevant data for visualisation; both static and dynamic subsets can be specified, (2) Summaries: to capture the essence of RDF data being viewed; summarized data can be expanded on demand thereby allowing users to create hybrid (summary-detail) fisheye views of RDF data, and (3) Sampling: to further optimize visualization of large-scale data where a representative sample suffices. The visualization scheme works with both asserted and inferred triples (generated using RDF(S) and OWL semantics). This scheme is implemented in Oracle by developing a plug-in for the Cytoscape graph visualization tool, which uses functions defined in a Oracle PL/SQL package, to provide fast and optimized access to Oracle Semantic Store containing RDF data. Interactive visualization of a synthesized RDF data set (LUBM 1 million triples), two native RDF datasets (Wikipedia 47 million triples and UniProt 700 million triples), and an OWL ontology (eClassOwl with a large class hierarchy including over 25,000 OWL classes, 5,000 properties, and 400,000 class-properties) demonstrates the effectiveness of our visualization scheme.

The concept of time-constrained SQL queries was introduced to address the problem of long-running SQL queries. A key approach adopted for supporting time-constrained SQL queries is to use sampling to reduce the amount of data that needs to be processed, thereby allowing completion of the query in the specified time constraint. However, sampling does make the query results approximate and hence requires the system to estimate the values of the expressions (especially aggregates) occurring in the select list. Thus, coming up with estimates for aggregates is crucial for time-constrained approximate SQL queries to be useful, which is the focus of this paper. Specifically, we address the problem of estimating commonly occurring aggregates (namely, SUM, COUNT, AVG, MEDIAN, MIN, and MAX) in time-constrained approximate queries. We give both point and interval estimates for SUM, COUNT, AVG, and MEDIAN using Bernoulli sampling for various type of queries, including join processing with cross product sampling. For MIN (MAX), we give the confidence level that the proportion 100γ% of the population will exceed the MIN (or be less than the MAX) obtained from the sampled data.

The growth of RDF data makes it imperative that an efficient mechanism for bulk-loading RDF graphs be supported. Thus, the paper proposes a bulk-load scheme that allows fast loading of arbitrarily large RDF graphs into a database. Specifically, three modes of load are supported: i) loading into an empty RDF graph, ii) appending to a non-empty RDF graph, and iii) concurrent loads into multiple graphs. The bulk-load scheme is implemented as part of Oracle database semantic technologies and the performance experiments conducted with a variety of RDF graphs (from UniProt and synthesized data of Lehigh University Benchmark) demonstrate the scalability of the approach. The paper outlines the challenges involved in bulk- loading of large RDF graphs, describes the bulk-load scheme, discusses its implementation, and presents a performance study.

This inference engines are an integral part of semantic data stores. In this paper, we describe our experience of implementing a scalable inference engine for Oracle semantic data store. This inference engine computes production rule based entailment of one or more RDFS/OWL encoded semantic data models. The inference engine capabilities include (i) inferencing based on semantics of RDFS/OWL constructs and user-defined rules, (ii) computing ancillary information (namely, semantic distance and proof) for inferred triples, and (iii) validation of semantic data model based on RDFS/OWL semantics. A unique aspect of our approach is that the inference engine is implemented entirely as a database application on top of Oracle database. The paper describes the inferencing requirements, challenges in supporting a sufficiently expressive set of RDFS/OWL constructs, and techniques adopted to build a scalable inference engine. A performance study conducted using both native and synthesized semantic datasets demonstrates the effectiveness of our approach.

Partitioning is typically employed on large-scale data to improve manageability, availability, and performance. However, for tables connected by a referential constraint (capturing a parent-child relationship), the current approaches require individually partitioning each table thereby burdening the user with the task of maintaining the tables equi-partitioned, which not only is cumbersome but also error prone. This paper proposes a new partitioning method (partition by reference) that allows tables with a parent-child relationship to be logically equi-partitioned by inheriting the partition key from the parent table without duplicating the key columns. The partitioning key is resolved through an existing parent-child relationship, enforced by an active referential constraint. This logical dependency is used to automatically i) cascade partition maintenance operations performed on parent table to child tables, and ii) handle migration of child rows when partition key or parent key in parent table is updated, as a single atomic operation. This method has been introduced in Oracle Database 11gR1 with support for tables with both single level and composite partitioning methods. The paper describes the key concepts of table partitioning by reference method, discusses the design and implementation challenges, and presents an experimental study covering a usage scenario common in Information Life Cycle Management (ILM) applications.

Keywords are typically used to qualify rows in a table. However, the fact that a keyword denotes a concept, which belongs to a specific knowledge domain, is not semantically enforced in current database systems. This paper proposes defining ontology based referential constraint for such keyword columns. A query on ontology, specified as part of the referential constraint, is used to identify the domain for the keyword column. Furthermore, since ontology may evolve causing change to the domain of the keyword column, the paper proposes use of ontology based transformation functions to either automatically evolve or to recommend refinements for the values in the keyword column. Also, queries on a keyword column can perform semantic match, that is, match a keyword to related terms based on the associated ontology. Thus, the proposed approach of semantically connecting keyword columns to ontologies 1) enhances semantic data integrity, 2) facilitates evolution of keyword columns with the referenced ontology, and 3) enables semantic match queries on keyword columns.

Most commercial SQL database systems support user-defined functions that can be used in WHERE clause filters, SELECT list items, or in sorting/grouping clauses. Often, user-defined functions are used as inexact search filters and then the filtered rows are sorted by a relevance measure. This is commonplace in Web search engines, multimedia, and personalization applications. We refer to the values, such as relevance measure, associated with the filtered rows as ancillary values, and address the problem of efficiently and expressively supporting queries involving them in Oracle. In our approach, the filtering operator is designated as the primary operator, and the associated ancillary values are modeled by additional operators that are declared to be ancillary to the primary operator. An ancillary operator can represent any auxiliary value for the filtered rows, including relevance values (e.g. a score which describes how well a document matches the text search query) and additional properties (e.g. the nature of spatial relationship for objects that overlap a given region). The query execution is optimized by allowing the primary and ancillary operator invocations to share computations via a shared context. Also, queries involving ancillary values can exploit user defined indexes and their capability to return results in the order of ancillary values. We present the key concepts, describes our implementation scheme and optimization techniques, and discusses alternative approaches for supporting ancillary values. Finally, we provide an experimental study that illustrates the scalability and effectiveness of our approach.

Any auxiliary structure, such as a bitmap or a B+-tree index, that refers to rows of a table stored as a primary B+-tree (e.g., tables with clustered index in Microsoft SQL Server, or index-organized tables in Oracle) by their physical addresses would require updates due to inherent volatility of those addresses. To address this problem, we propose a mapping mechanism that 1) introduces a single mapping table, with each row holding one key value from the primary B+-tree, as an intermediate structure between the primary B+-tree and the associated auxiliary structures, and 2) augments the primary B+-tree structure to include in each row the physical address of the corresponding mapping table row. The mapping table row addresses can then be used in the auxiliary structures to indirectly refer to the primary B+-tree rows. The two key benefits are: 1) the mapping table shields the auxiliary structures from the volatility of the primary B+-tree row addresses, and 2) the method allows reuse of existing conventional table mechanisms for supporting auxiliary structures on primary B+-trees. The mapping mechanism is used for supporting bitmap indexes on index-organized tables in Oracle9i. The analytical and experimental studies show that the method is storage efficient, and (despite the mapping table overhead) provides performance benefits that are similar to those provided by bitmap indexes implemented on conventional tables.

Most commercial database systems support B/sup +/-tree indexes using either: physical row identifiers, for example, DB2; or logical row identifiers, for example, NonStop SQL. Physical row identifiers provide fast access to data. However, unlike logical row identifiers, they need to be updated whenever the row moves. This paper describes an alternate approach where hybrid row identifiers are used. A hybrid row identifier consists of two components: a logical component, namely, the primary key of the base table row; and a physical component, namely, the database block address (DBA) of the row. By treating the DBA as a guess regarding where the row may be found, performance comparable to physical B/sup +/-tree indexes is attained for valid guess-DBAs. This scheme retains the logical index advantage of avoiding an immediate index update when the base table row moves. Instead, an online utility can be used to lazily fix the invalid guess-DBAs. This scheme has been used to implement B/sup +/-tree indexes for Oracle8i index-organized tables (primary B/sup +/-tree like structure) which encounter both row movement and table reorganization.

Over the last decade, database system products have been extended to provide support for defining, storing, updating, indexing and retrieving complex data with full transaction semantics. Oracle, IBM, Informix and others have used extensibility technology to build database system extensions for text, image, spatial, audio/video, chemical, genetic and other types of complex data. Currently, we find database systems being deployed in support of e-commerce. In many cases, these e-commerce database applications use only simple SQL data types to represent items such as office supplies, computers, books and CDs. There is also a large and important set of e-commerce applications that employ complex data formats such as EDI, SWIFT and HL7. The database extensibility features initially developed to support text, spatial and similar forms of complex data are now being used to build e-commerce applications. Thus, database extensibility technology is evolving into an important mechanism to enable the development of e-commerce systems.

Extensible indexing is a SQL-based framework that allows users to define domain-specific indexing schemes, and integrate them into the Oracle8i server. Users register a new indexing scheme, the set of related operators, and additional properties through SQL data definition language extensions. The implementation for an indexing scheme is provided as a set of Oracle Data Cartridge Interface (ODCIIndex) routines for index-definition, index-maintenance, and index-scan operations. An index created using the new indexing scheme, referred to as domain index, behaves and performs analogous to those built natively by the database system. The Oracle8i server implicitly invokes user-supplied index implementation code when domain index operations are performed, and executes user-supplied index scan routines for efficient evaluation of domain-specific operators. This paper provides an overview of the framework and describes the steps needed to implement an indexing scheme. The paper also presents a case study of Oracle Cartridges (intermedia text, spatial, and visual information retrieval), and Daylight (Chemical compound searching) Cartridge, which have implemented new indexing schemes using this framework and discusses the benefits and limitations.

Workload characteristics in a modern networking environment are very dynamic. In order to maximize performance continuously, it is natural to explore the possibility of intelligent systems which can take cognizance of the workload dynamics and adapt themselves for future control applications. In this paper, we propose a mechanism which represents the previous state of the system as a string. The user is allowed to define relevant information for better management as substrings. The adaptive workload model, which is called the SVR model (named after the first author's initials), predicts the short-term future as a string in which the information content (conveyed as a substring) reflects the future. We illustrate the applicability of the SVR model through Web traffic generation and ATM bandwidth management. We use genetic algorithms as the vehicle to address the learning aspects of the model.

Future versions of the Oracle Server will provide an open and extensible framework for supporting complex data domains including, but not limited to, text, image, spatial, video, and OLAP. This framework encompasses features for defining, storing, updating, indexing, and retrieving complex forms of data with full transaction semantics. The underpinning for these features is an extended Oracle Server that is an object-relational database management system (ORDBMS).

The full integration of information retrieval (IR) features into a database management system (DBMS) has long been recognized as both a significant goal and a challenging undertaking. By full integration we mean: i) support for document storage, indexing, retrieval, and update, ii) transaction semantics, thus all database operations on documents have the ACID properties of atomicity, consistency, isolation, and durability, iii) concurrent addition, update, and retrieval of documents, and iv) database query language extensions to provide ranking for document retrieval operations. It is also necessary for the integrated offering to exhibit scaleable performance for document indexing and retrieval processes. To identify the implementation requirements imposed by the desired level of integration, we layered a representative IR application on Oracle Rdb and then conducted a number of database load and document retrieval experiments. The results of these experiments suggest that infrastructural extensions are necessary to obtain both the desired level of IR integration and scaleable performance. With the insight gained from our initial experiments, we developed an approach, called cooperative indexing, that provides a framework to achieve both scaleability and full integration of IR and RDBMS technology. Prototype implementations of system-level extensions to support cooperative indexing were evaluated with a modified version of Oracle Rdb. Our experimental findings validate the cooperative indexing scheme and suggest alternatives to further improve performance.

O-Raid [1, 2] uses a layered approach to provide support for objects on top of a distributed relational database system called RAID [3], It reuses the replication controller of RAID to allow replication of simple objects as well as replication of composite objects. In this paper, we first describe the experiments conducted on O-Raid that measure the overheads incurred in supporting objects through a layered implementation, and the overheads involved in replicating objects. The overheads are low (e.g. 4ms for an insert query involving objects). We present experiments that evaluate three replication strategies for composite objects, namely, full replication, selective replication and no replication in a two-site and a four-site O-Raid system. For composite object experiments, the selective replication strategy demonstrated the flexibility of tuning replication of member objects based on the patterns of access. The experimentation is performed in different networking environments (LANs and WANs) to further evaluate the replication schemes. The results indicate that selective replication scheme has greater benefits in WAN than in LAN.

The authors present the query language SQL++ used in the O-Raid object-oriented database system. SQL++ is an extension to the relational query language SQL that adds object-oriented capabilities. It supports object-oriented database capabilities such as subobject referencing, method invocation, navigational queries, and 'implicit joins' while maintaining the relational capabilities and closure property of SQL. SQL++ also has an application program interface that solves the 'impedance mismatch' problem for C++ application programs, allowing them to store and retrieve objects in the database without the need to translate from one data format to another.>

The behavior and performance of replica control protocols (RCP) that deal with network partitions is investigated using a quorum-based replicated database system called Seth. Seth is designed to be used as a transaction processing system, as well as a flexible experimentation tool. Seth's experimentation domain includes failures (site/link failure/repair rates), transactions (arrival rate, size, type, read/write ratio), quorum assignment, communications (communication protocols, network type, topology, number of sites), and transaction protocols (quorum-based RCPs, distributed commitment, concurrency control). The design and implementation of Seth are discussed, and two experiments are presented. The first studies the behavior of the quorum consensus protocol against different transition loads. The second experiment shows how expensive quorum-based replication is in terms of network traffic.>