The rapidly growing size of RDF graphs in recent years necessitates distributed storage and parallel processing strategies. To obtain efficient query processing using computer clusters a wide variety of different approaches have been proposed. Related to the approach presented in the current paper are systems built on top of Hadoop HDFS, for example using Apache Accumulo or using Apache Spark. We present a new RDF store called PRoST (Partitioned RDF on Spark Tables) based on Apache Spark. PRoST introduces an innovative strategy that combines the Vertical Partitioning approach with the Property Table, two preexisting models for storing RDF datasets. We demonstrate that our proposal outperforms state-of-the-art systems w.r.t. the runtime for a wide range of query types and without any extensive precomputing phase.

RDF has become very popular for semantic data publishing due to its flexible and universal graph-like data model. Thus, the ever-increasing size of RDF data collections raises the need for scalable distributed approaches. We endorse the usage of existing infrastructures for Big Data processing like Hadoop for this purpose. Yet, SPARQL query performance is a major challenge as Hadoop is not intentionally designed for RDF processing. Existing approaches often favor certain query pattern shapes while performance drops significantly for other shapes. In this paper, we introduce a novel relational partitioning schema for RDF data called ExtVP that uses a semi-join based preprocessing, akin to the concept of Join Indices in relational databases, to efficiently minimize query input size regardless of its pattern shape and diameter. Our prototype system S2RDF is built on top of Spark and uses SQL to execute SPARQL queries over ExtVP. We demonstrate its superior performance in comparison to state of the art SPARQL-on-Hadoop approaches.

Navigational queries are among the most natural query patterns for RDF data, but yet most existing RDF query languages fail to cover all the varieties inherent to its triple-based model, including SPARQL 1.1 and its derivatives. As a consequence, the development of more expressive RDF languages is of general interest. With TriAL* [14], there exists an expressive algebra which subsumes many previous approaches, while adding novel features that are not expressible in most other RDF query languages based on the standard graph model. However, its algebraic notation is inappropriate for practical usage and it is not supported by any existing RDF triple store. In this paper, we propose TriAL-QL, an easy to write and grasp language for TriAL*, preserving its compositional algebraic structure. We present an implementation based on Impala, a massive parallel SQL query engine on Hadoop, using an optimized semi-naive evaluation for the recursive fragments of TriAL*. This way, we support both data-intensive ETL-like workloads and explorative ad-hoc style queries. To demonstrate the scalability and expressiveness of our approach, we conducted experiments on generated social networks with up to 1.8 billion triples and compared different execution strategies to a Hive-based solution.

The rdfs:seeAlso predicate plays an important role in linking web resources in semantic web. Based on the W3C definition, it shows that the object resource provide additional information about the subject resource. Since providing additional information can take various forms, the definition is generic. In the other words, the rdfs:seeAlso link can present different meanings to the users and it can represents different kind of patterns and relationships between web resources. These patterns are unknown and have to be specified to help organizations, and individuals to interlink, and publish their datasets on Web of Data using the rdfs:seeAlso link. In this paper, we investigate to the traditional usages of seealso and then present a methodology to specify the patterns of rdfs:seeAlso usages in Semantic Web. The results of our investigation show that the discovered patterns constitute a significant portion of rdfs:seeAlso usages in Web of Data.

Taste in music is of highly subjective nature, making the recommending of music tracks a challenging research task. With TRECS, our live prototype system, we present a weighted hybrid recommender approach that amalgamates three diverse recommender te

In recent times, it has been widely recognized that, due to their inherent scalability, frameworks based on MapReduce are indispensable for so-called "Big Data" applications. However, for Semantic Web applications using SPARQL, there is still a demand for sophisticated MapReduce join techniques for processing basic graph patterns, which are at the core of SPARQL. Renowned for their stable and efficient performance, sort-merge joins have become widely used in DBMSs. In this paper, we demonstrate the adaptation of merge joins for SPARQL BGP processing with MapReduce. Our technique supports both n-way joins and sequences of join operations by applying merge joins within the map phase of MapReduce while the reduce phase is only used to fulfill the preconditions of a subsequent join iteration. Our experiments with the LUBM benchmark show an average performance benefit between 15% and 48% compared to other MapReduce based approaches while at the same time scaling linearly with the RDF dataset size.

Taste in music is of highly subjective nature, making the recommending of music tracks a challenging research task. With TRecS, our live prototype system, we present a weighted hybrid recommender approach that amalgamates three diverse recommender techniques into one comprehensive score. Moreover, our system peppers the generated result list with recommendations based on a simple serendipity heuristic. This way, users can benefit from recommendations aligned with their current taste in music while gaining some exploratory diversification. An explanation feature helps the user understand the rationale behind each of the tracks being recommended to him. Empirical evaluations of the live system, based on an online evaluation, assess the overall recommendation quality as well as the impact of each of the three sub-recommenders.

Similarity estimation between interconnected objects appears in many real-world applications and many domain-related measures have been proposed. This work proposes a new perspective on specifying the similarity between resources in linked data, and

We study fundamental aspects related to the efficient processing of the SPARQL query language for RDF, proposed by the W3C to encode machine-readable information in the Semantic Web. Our key contributions are (i) a complete complexity analysis for all operator fragments of the SPARQL query language, which -- as a central result -- shows that the SPARQL operator Optional alone is responsible for the PSpace-completeness of the evaluation problem, (ii) a study of equivalences over SPARQL algebra, including both rewriting rules like filter and projection pushing that are well-known from relational algebra optimization as well as SPARQL-specific rewriting schemes, and (iii) an approach to the semantic optimization of SPARQL queries, built on top of the classical chase algorithm. While studied in the context of a theoretically motivated set semantics, almost all results carry over to the official, bag-based semantics and therefore are of immediate practical relevance.

Both semantic and type-based query optimization rely on the idea that queries often exhibit non-trivial rewritings if the state space of the database is restricted. Despite their close connection, these two problems to date have always been studied separately. We present a unifying, logic-based framework for query optimization in the presence of data dependencies and type information. It builds upon the classical chase algorithm and extends existing query minimization techniques to considerably larger classes of queries and dependencies. In particular, our setting requires chasing conjunctive queries (possibly with union and negation) in the presence of dependencies containing negation and disjunction. We study the applicability of the chase in this setting, develop novel conditions that guarantee its termination, identify fragments for which minimal query computation is always possible (w.r.t. a generic cost function), and investigate the complexity of related decision problems.

Recently, the SPARQL query language for RDF has reached the W3C recommendation status. In response to this emerging standard, the database community is currently exploring efficient storage techniques for RDF data and evaluation strategies for SPARQL queries. A meaningful analysis and comparison of these approaches necessitates a comprehensive and universal benchmark platform. To this end, we have developed SP2Bench, a publicly available, language-specific SPARQL performance benchmark. SP2Bench is settled in the DBLP scenario and comprises both a data generator for creating arbitrarily large DBLP-like documents and a set of carefully designed benchmark queries. The generated documents mirror key characteristics and social-world distributions encountered in the original DBLP data set, while the queries implement meaningful requests on top of this data, covering a variety of SPARQL operator constellationsand RDF access patterns. As a proof of concept, we apply SP2Bench to existing engines and discuss their strengths and weaknesses that follow immediately from the benchmark results.

We study the termination problem of the chase algorithm, a central tool in various database problems such as the constraint implication problem, Conjunctive Query optimization, rewriting queries using views, data exchange, and data integration. The basic idea of the chase is, given a database instance and a set of constraints as input, to fix constraint violations in the database instance. It is well-known that, for an arbitrary set of constraints, the chase does not necessarily terminate (in general, it is even undecidable if it does or not). Addressing this issue, we review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow us to establish weaker sufficient conditions. In particular, we introduce two novel termination conditions called safety and inductive restriction , and use them to define the so-called T-hierarchy of termination conditions. We then study the interrelations of our termination conditions with previous conditions and the complexity of checking our conditions. This analysis leads to an algorithm that checks membership in a level of the T -hierarchy and accounts for the complexity of termination conditions. As another contribution, we study the problem of data-dependent chase termination and present sufficient termination conditions w.r.t. fixed instances. They might guarantee termination although the chase does not terminate in the general case. As an application of our techniques beyond those already mentioned, we transfer our results into the field of query answering over knowledge bases where the chase on the underlying database may not terminate, making existing algorithms applicable to broader classes of constraints.

The goal of the Semantic Web is to support semantic interoperability between applications exchanging data on the web. The idea heavily relies on data being made available in machine readable format, using semantic markup languages. In this regard, the W3C has standardized RDF as the basic markup language for the Semantic Web. In contrast to relational databases, where data relationships are implicitly given by schema information as well as primary and foreign key constraints, relationships in semantic markup languages are made explicit. When mapping relational data into RDF, it is desirable to maintain the information implied by the origin constraints. As an improvement over existing approaches, our scheme allows for translating conventional databases into RDF without losing general constraints and vital key information. As much as in the relational model, those information are indispensable for data consistency and, as shown by example, can serve as a basis for semantic query optimization. We underline the practicability of our approach by showing that SPARQL, the most popular query language for RDF, can be used as a constraint language, akin to SQL in the relational context. As a theoretical contribution, we also discuss satisfiability for interesting classes of constraints and combinations thereof. 1.

The design of containment checking algorithms for conjunctive queries with arithmetic comparisons and safe negations (CQ­s) is fundamental to many database applications. However, it is a challenging task due to the intractability of the problem. Existing algorithms are either computationally too expensive, or capable to deal with only a fragment of these extensions.

We present a browser-extending Semantic Web extraction system that maps HTML documents to tables and, where possible, to rules. First, the basic data extractor ViPER distills and reorganizes semi-structured information into a tabular data structure, which can again be browsed and/or submitted to further machine processing. Second, exemplifying the latter, the extended knowledge extractor Rex ViPER mines the resulting tables for structural properties and functional dependencies. Rules are generated to obtain a more compact and manageable, often also enriched, knowledge representation. The resulting fully structured information, RuleML-serialized facts and rules, can be stored along with the orginal documents, queried by rule engines such as OO jDREW and FLORID, and interchanged between Web Services. Thus Rex ViPER contributes to automating the construction of a machine-processable Semantic Web.

Taxonomic measures of semantic proximity allow us to compute the relatedness of two concepts. These metrics are versatile instruments required for diverse applications, e.g., the Semantic Web, linguistics, and also text mining. However, most approaches are only geared towards hand-crafted taxonomic dictionaries such as WordNet, which only feature a limited fraction of real-world concepts. More specific concepts, and particularly instances of concepts, i.e., names of artists, locations, brand names, etc., are not covered.The contributions of this paper are two fold. First, we introduce a framework based on Google and the Open Directory Project (ODP), enabling us to derive the semantic proximity between arbitrary concepts and instances. Second, we introduce a new taxonomy-driven proximity metric tailored for our framework. Studies with human subjects corroborate our hypothesis that our new metric outperforms benchmark semantic proximity metrics and comes close to human judgement.

In this paper we address the problem of unsupervised Web data extraction. We show that unsupervised Web data extraction becomes feasible when supposing pages that are made up of repetitive patterns, as it is the case, e.g., for search engine result pages. Hereby the extraction rules are generated automatically without any training or human interaction, by means of operating on the DOM tree respectively the flat tag token sequence of a single page.Our contribution to automatic data extraction through this paper is twofold. First, we identify and rank potential repetitive patterns with respect to the user's visual perception of the Web page, well aware that location and size of matching elements within a Web page constitute important criteria for defining relevance. Second, matching sub-sequences of the pattern with the highest weightiness are aligned with global multiple sequence alignment techniques. Experimental results show that our system is able to achieve high accuracy in distilling and aligning regularly structured objects inside complex Web pages.

In this work we present topic diversification, a novel method designed to balance and diversify personalized recommendation lists in order to reflect the user's complete spectrum of interests. Though being detrimental to average accuracy, we show that our method improves user satisfaction with recommendation lists, in particular for lists generated using the common item-based collaborative filtering algorithm.Our work builds upon prior research on recommender systems, looking at properties of recommendation lists as entities in their own right rather than specifically focusing on the accuracy of individual recommendations. We introduce the intra-list similarity metric to assess the topical diversity of recommendation lists and the topic diversification approach for decreasing the intra-list similarity. We evaluate our method using book recommendation data, including offline analysis on 361, !, 349 ratings and an online study involving more than 2, !, 100 subjects.

Recommender systems have been subject to an enormous rise in popularity and research interest over the last ten years. At the same time, very large taxonomies for product classification are becoming increasingly prominent among e-commerce systems for diverse domains, rendering detailed machine-readable content descriptions feasible. Amazon.com makes use of an entire plethora of hand-crafted taxonomies classifying books, movies, apparel, and various other goods. We exploit such taxonomic background knowledge for the computation of personalized recommendations. Hereby, relationships between super-concepts and sub-concepts constitute an important cornerstone of our novel approach, providing powerful inference opportunities for profile generation based upon the classification of products that customers have chosen. Ample empirical analysis, both offline and online, demonstrates our proposal's superiority over common existing approaches when user information is sparse and implicit ratings prevail.

The fact that, most of the time, the integration of different catalogs implies the generation, maintenance and adaptation of a global catalog that forwards the appropriate queries to the corresponding local catalogs for evaluation, requires us to perform query rewriting in order to provide the user with an answer. We provide some insight on the adaptive evaluation techniques for querying XML-based electronic catalogs. This technique eliminates the need to perform an explicit query rewriting when performing a query upon a global catalog, while still obtaining accurate answers, as we show in our experiments.

Summary form only given. FLORID-F-LOgic Reasoning In Databases-is a deductive object oriented database system incorporating F-logic (M. Kifer et al., 1995) as a data definition and query language and combining the advantages of deductive databases with the rich modelling capabilities of object oriented concepts. F-logic provides complex objects, uniform handling of data and metadata, rule defined class hierarchy and signatures, nonmonotonic multiple inheritance, equating of objects by rules and variables ranging over methods and classes. Moreover, FLORID extends F-logic by path expressions (J. Frohn et al., 1994) to facilitate object navigation. Because of its powerful properties, F-logic cannot be mapped onto a relational data model by transforming classes into relations. Hence, it was a major design goal to use an object oriented data representation in FLORID. All information about one object is stored in an object frame which has a unique OID. Several (external) object names may refer to the same OID, thus defining an equivalence relation between objects. Frames consist of slots for method applications or class membership, enabling schema modifications during the evaluation by deriving new signatures, subclass relationships or class memberships. The collection of all frames forms an object world.

Referential actions are specialized triggers used to automatically maintain referential integrity.While their local behavior can be grasped easily, it is far from clear what the combined effect of a set of referential actions, i.e., their global semantics should be.For example, different execution orders may lead to ambiguities in determining the final set of updates to be applied.To resolve these problems, we propose an abstract logical framework for rule-based maintenance of referential integrity: First, we identify desirable abstract properties like admissibility of updates which lead to a non-constructive global semantics of referential actions.We obtain a constructive definition by formalizing a set of referential actions RA as logical rules, and show that the declarative semantics of the resulting logic program PRA captures the intended abstract semantics: The well-founded model of PRA yields a unique set of updates, which is a safe, sceptical approximation of the set of all maximal admissible updates; the thud truth-value undefined is assigned to all controversiaI updates.Finally, we show how to obtain a characterization of all maximal admissible subsets of a given set of updates using certain maximal stable models.-.-.--... .

We propose a novel formalism, calledFrame Logic(abbr., F-logic), that accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages. These features include object identity, complex objects, inheritance, polymorphic types, query methods, encapsulation, and others. In a sense, F-logic stands in the same relationship to the object-oriented paradigm as classical predicate calculus stands to relational programming. F-logic has a model-theoretic semantics and a sound and complete resolution-based proof theory. A small number of fundamental concepts that come from object-oriented programming have direct representation in F-logic; other, secondary aspects of this paradigm are easily modeled as well. The paper also discusses semantic issues pertaining to programming with a deductive object-oriented language based on a subset of F-logic.

We show how classical datalog semantics can be used directly and very simply to provide semantics to a syntactic extension of datalog with methods, classes, inheritance, overloading and late binding. Several approaches to resolution are considered, implemented in the model, and formally compared. They range from resolution in C++ style to original kinds of resolution suggested by the declarative nature of the language. We show connections to view specification and a further extension allowing runtime derivation of the class hierarchy.

A Datalog program consists of function-free Horn clause rules.The main problem in evaluating Datalog programs is to achieve an acceptable performance.The reason is, that Datalog programs usually are evaluated bottom-up to compute in an iterative way the fixpoint of the program.Given a large amount of base facts, program evaluation can be a very lengthy process.In the paper parallel processing of decomposable Datalog programs is considered to overcome this problem.A decomposable program can be evaluated in parallel such that neither a communication nor a synchronization of the processors haa to be established [WS88].The concept of generalized pivoting is proposed, which is a sufficient condition for decomposability of arbitrary Datalog programs.Moreover, the clam of completely decomposable programs is introduced and it is shown, that generalized pivoting is also a necessary condition for complete decomposability.

We propose a database logic which accounts in a clean declarative fashion for most of the “object-oriented” features such as object identity, complex objects, inheritance, methods, etc. Furthermore, database schema is part of the object language, which allows the user to browse schema and data using the same declarative formalism. The proposed logic has a formal semantics and a sound and complete resolution-based proof procedure, which makes it also computationally attractive.

Many widely used specification techniques for information systems are based on a hierarchy of information flow diagrams. A method is introduced which preserves the benefits of these techniques and adds the precision of the Petri net formalism. Information-flow diagram hierarchies are formalized by notions of net theory. The bottom-level nets of a hierarchy are treated as Petri nets. The behavior model of the information system is the Petri net derived by repeatedly replacing each part of a net by its associated refinement. As a prerequisite for such replacements, the data abstractions relation information flows of different level are specified by a semantic hierarchy data model. The nets in the hierarchy are appended by dynamic counterparts of the abstractions so that a consistent replacement becomes possible. The interface behavior of the nets in the hierarchy is analyzed, using the concept of behavior constraints as a formal measure of correct interface behavior. The behavior model can be derived in an iterative bottom-up way by first analyzing a net for fulfillment of its associated behavior constraint and afterward integrating it into the next-higher-level net.>

The purpose of a database concurrency control mechanism is to control a transaction system in such a way that only serializable executions of transactions are possible; that is, safety is enforced. Locking is an appropriate means to achieve safety. In this paper the following problem is considered:Can the set of all serializable schedules (in the sense of conflict-preserving serializability) of a transaction system be defined by locking, i.e., can maximal concurrency be achieved by locking?An efficient algorithm exists for the problem in the case of two-transaction systems, but in general the problem is NP-complete. In the case in which maximal concurrency indeed is achievable by locking a locking policy realizing maximal concurrency can be constructed efficiently. Finally, an easy-to-test sufficient condition under which maximal concurrency is achieved by locking is discussed.