Search

A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases. In this paper we extend this result to the case of higher-order Datalog. In particular, we demonstrate that on ordered databases, for all $k\geq2$, $k$-order Datalog captures $(k-1)$-EXPTIME. This result suggests that higher-order extensions of Datalog possess superior expressive power and they are worthwhile of further investigation both in theory and in practice. This paper is under consideration for acceptance in TPLP., Paper presented at the 35th International Conference on Logic Programming (ICLP 2019), Las Cruces, New Mexico, USA, 20-25 September 2019, 24 pages, LaTeX

We introduce the notion of a lexicographic lattice structure, namely a lattice whose elements can be viewed as stratified entities and whose ordering relation compares elements in a lexicographic manner with respect to their strata. These lattices arise naturally in many non-monotonic formalisms, such as normal logic programs, higher-order logic programs with negation, and boolean grammars. We consider functions over such lattices that may overall be non-monotonic, but retain a restricted form of monotonicity inside each stratum. We demonstrate that such functions always have a least fixed point which is also their least pre-fixed point. Moreover, we prove that the sets of pre-fixed and post-fixed points of such functions, are complete lattices. For the special case of a trivial lexicographic lattice structure whose elements essentially consist of a unique stratum, our theorem gives as a special case the well-known Knaster-Tarski fixed point theorem. Moreover, our work considerably simplifies and extends recent results on non-monotonic fixed point theory, providing in this way a useful and convenient tool in the semantic investigation of non-monotonic formalisms.

We consider the problem of concisely representing and handling preferences in logic programming and relational databases. Our starting point is the well-known proposal developed in [2] which advocates the embedding of first-order preference formulas into relational algebra through a winnow operator that is parameterized by a database relation and a preference formula. We argue that despite its elegance, the above proposal has certain shortcomings: only intrinsic preference formulas are supported, the preference relations and the preference queries are expressed in two different languages, and there is no direct way to define alternative operators beyond winnow. We propose the use of higher-order logic programming as a logical framework that remedies the above deficiencies. In particular, the proposed framework supports both intrinsic and extrinsic preference formulas, it can represent both preference relations as-well-as queries, and it can be used to define a variety of interesting alternative operators beyond winnow. We demonstrate the feasibility of our approach by presenting an implementation and an experimental evaluation of all the proposed concepts in the higher-order logic programming language Hilog.

Higher-order logic programming is an interesting extension of traditional logic programming that allows predicates to appear as arguments and variables to be used where predicates typically occur. Higher-order characteristics are indeed desirable but on the other hand they are also usually more expensive to support. In this paper we propose a program specialization technique based on partial evaluation that can be applied to a modest but useful class of higher-order logic programs and can transform them into first-order programs without introducing additional data structures. The resulting first-order programs can be executed by conventional logic programming interpreters and benefit from other optimizations that might be available. We provide an implementation and experimental results that suggest the efficiency of the transformation.

Robotics and IoT applications are perfect candidates that can benefit from the functional reactive programming paradigm. Moreover, since a typical program can be represented as a dataflow graph, the application can be conceptually separated and distributed in different machines and the several graph partitions can run in parallel and possibly in different execution stacks. In this paper we propose a general-purpose reactive framework that can express complex applications, seamlessly and transparently integrating different sources and middlewares. The framework is abstract and extensible, making it easy to integrate with well-established technologies that rely on the PubSub model. We demonstrate the usability of the framework by providing application examples in the domain of robotics and IoT.

We define a novel, extensional, three-valued semantics for higher-order logic programs with negation. The new semantics is based on interpreting the types of the source language as three-valued Fitting-monotonic functions at all levels of the type hierarchy. We prove that there exists a bijection between such Fitting-monotonic functions and pairs of two-valued-result functions where the first member of the pair is monotone-antimonotone and the second member is antimonotone-monotone. By deriving an extension of consistent approximation fixpoint theory (Denecker et al. 2004) and utilizing the above bijection, we define an iterative procedure that produces for any given higher-order logic program a distinguished extensional model. We demonstrate that this model is actually a minimal one. Moreover, we prove that our construction generalizes the familiar well-founded semantics for classical logic programs, making in this way our proposal an appealing formulation for capturing the well-founded semantics for higher-order logic programs. This paper is under consideration for acceptance in TPLP., Comment: Paper presented at the 34nd International Conference on Logic Programming (ICLP 2018), Oxford, UK, July 14 to July 17, 2018 31 pages, LaTeX

Dataset description vocabularies focus on provenance, ver-sioning, licensing, and similar metadata. VoID is a notable exception, providing some expressivity for describing subsets and their contents and can, to some extent, be used for discovering relevant resources and for optimizing querying. In this paper we describe the Sevod vocabulary, an extension of VoID that provides the expressivity needed in order to support the query planning methods typically used in federated querying. We also present a tool for automatically scraping such metadata from RDF dumps and give statistics about the size of the descriptions for the FedBench datasets.

In this paper we present SPREFQL, an extension of the SPARQL language that allows appending a "PREFER" clause that expresses ‘soft’ preferences over the query results obtained by the main body of the query. The extension does not add expressivity and any SPREFQL query can be transformed to an equivalent standard SPARQL query. However, clearly separating preferences from the ‘hard’ patterns and filters in the "WHERE" clause gives queries where the intention of the client is more cleanly expressed, an advantage for both human readability and machine optimization. In the paper we formally define the syntax and the semantics of the extension and we also provide empirical evidence that optimizations specific to SPREFQL improve run-time efficiency by comparison to the usually applied optimizations on the equivalent standard SPARQL query.

The management and analysis of large-scale datasets - described with the term Big Data - involves the three classic dimensions volume, velocity and variety. While the former two are well supported by a plethora of software components, the variety dimension is still rather neglected. We present the BDE platform - an easy-to-deploy, easy-to-use and adaptable (cluster-based and standalone) platform for the execution of big data components and tools like Hadoop, Spark, Flink, Flume and Cassandra. The BDE platform was designed based upon the requirements gathered from seven of the societal challenges put forward by the European Commission in the Horizon 2020 programme and targeted by the BigDataEurope pilots. As a result, the BDE platform allows to perform a variety of Big Data flow tasks like message passing, storage, analysis or publishing. To facilitate the processing of heterogeneous data, a particular innovation of the platform is the Semantic Layer, which allows to directly process RDF data and to map and transform arbitrary data into RDF. The advantages of the BDE platform are demonstrated through seven pilots, each focusing on a major societal challenge.

This paper presents work in progress towards developing a new benchmark for federated query processing systems. Unlike other popular benchmarks, our queryset is not driven by technical evaluation, but is derived from workflows established by the pharmacology community. The value of this queryset is that it is realistic but at the same time it comprises complex queries that test all features of modern query processing systems.

Two distinct research approaches have been proposed for assigning a purely extensional semantics to higher-order logic programming. The former approach uses classical domain theoretic tools while the latter builds on a fixed-point construction defined on a syntactic instantiation of the source program. The relationships between these two approaches had not been investigated until now. In this paper we demonstrate that for a very broad class of programs, namely the class of definitional programs introduced by W. W. Wadge, the two approaches coincide (with respect to ground atoms that involve symbols of the program). On the other hand, we argue that if existential higher-order variables are allowed to appear in the bodies of program rules, the two approaches are in general different. The results of the paper contribute to a better understanding of the semantics of higher-order logic programming., Comment: In Proceedings FICS 2015, arXiv:1509.02826

We describe an Inductive Logic Programming (ILP) approach to learning descriptions in Description Logics (DL) under uncertainty. The approach is based on implementing many-valued DL proofs as propositionalizations of the elementary DL constructs and then providing this implementation as background predicates for ILP. The proposed methodology is tested on a many-valued variation of eastbound-trains and Iris, two well known and studied Machine Learning datasets.

The DARE platform has been designed to help research developers deliver user-facing applications and solutions over diverse underlying e-infrastructures, data and computational contexts. The platform is Cloud-ready, and relies on the exposure of APIs, which are suitable for raising the abstraction level and hiding complexity. At its core, the platform implements the cataloguing and execution of fine-grained and Python-based dispel4py workflows as services. Reflection is achieved via a logical knowledge base, comprising multiple internal catalogues, registries and semantics, while it supports persistent and pervasive data provenance. This paper presents design and implementation aspects of the DARE platform, as well as it provides directions for future development.