Author name cluster

Mark Kaminski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

1 author row

AIJ Journal 2022 Journal Article

The delay and window size problems in rule-based stream reasoning

Alessandro Ronca
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

In recent years, there has been an increasing interest in extending stream processing engines with rule-based temporal reasoning capabilities. To ensure correctness, such systems must be able to output results over the partial data received so far as if the entire (infinite) stream had been available; furthermore, these results must be streamed out as soon as the relevant data is received, thus incurring the minimum possible delay; finally, due to memory limitations, systems can only keep a limited history of previous facts in memory to perform further computations. These requirements pose significant theoretical and practical challenges since temporal rules can derive new information and propagate it both towards past and future time points; as a result, streamed answers can depend on data that has not yet been received, as well as on data that arrived far in the past. Towards developing a solid foundation for practical rule-based stream reasoning, we propose and study in this paper a suite of decision problems that can be exploited by stream reasoning algorithms to tackle the aforementioned challenges, and provide tight complexity bounds for a core temporal extension of Datalog. All of the problems we consider can be solved at design time (under reasonable assumptions), prior to the processing of any data. Solving these problems enables the use of reasoning algorithms that process the input streams incrementally using a sliding window, while at the same time supporting an expressive rule-based knowledge representation language and minimising both latency and memory consumption.

Details DOI

AAAI Conference 2020 Conference Paper

Complexity and Expressive Power of Disjunction and Negation in Limit Datalog

Mark Kaminski
Bernardo Cuenca Grau
Egor V. Kostylev
Ian Horrocks

Limit Datalog is a fragment of DatalogZ—the extension of Datalog with arithmetic functions over the integers—which has been proposed as a declarative language suitable for capturing data analysis tasks. In limit Datalog programs, all intensional predicates with a numeric argument are limit predicates that keep maximal (or minimal) bounds on numeric values. Furthermore, to ensure decidability of reasoning, limit Datalog imposes a linearity condition restricting the use of multiplication in rules. In this paper, we study the complexity and expressive power of limit Datalog programs extended with disjunction in the heads of rules and non-monotonic negation under the stable model semantics. We show that allowing for unrestricted use of negation leads to undecidability of reasoning. Decidability can be restored by stratifying the use of negation over predicates carrying numeric values. We show that the resulting language is ΠEXP 2 -complete in combined complexity and that it captures ΠP 2 over ordered structures in the sense of descriptive complexity. We also provide a study of several fragments of this language: we show that the complexity and expressive power of the full language are already reached for disjunction-free programs; furthermore, we show that semi-positive disjunctive programs are coNEXPcomplete and that they capture coNP.

PDF Details

KR Conference 2020 Conference Paper

DatalogMTL over the Integer Timeline

Przemysław A. Wałęga
Bernardo Cuenca Grau
Mark Kaminski
Egor V. Kostylev

We study DatalogMTL—an extension of Datalog with metric temporal operators—under integer semantics, where the temporal domain of both interpretations and temporal operators consists of integer time points only. This is in contrast to the standard semantics, which is defined over the rational timeline. DatalogMTL under integer semantics is an interesting KR language: on the one hand, one can often assume the integer timeline in applications; on the other hand, it captures prominent temporal extensions of Datalog such as Datalog1S. We show that the choice of integer semantics leads to more favourable computational properties. We first show that reasoning over integers is at most as hard as reasoning over rationals for DatalogMTL and its natural fragments. Then, we investigate fragments of DatalogMTL where adopting the integer semantics makes reasoning easier. In particular, we show that complexity drops from P-hard to NC1-complete for the propositional fragment (where all object variables are grounded), and from TC0-hard to ACC0 for the linear fragment where the past diamond operator is the only metric operator allowed in rule bodies. Thus, reasoning in such fragments is both tractable and highly parallelisable, which suggests their appropriateness for data-intensive applications.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Tractable Fragments of Datalog with Metric Temporal Operators

Przemysław A. Wałęga
Bernardo Cuenca Grau
Mark Kaminski
Egor V. Kostylev

We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the core fragment, which disallows conjunction in rule bodies, and show that reasoning remains PSPACE-hard. Intractability prompts us to also limit the kinds of temporal operators allowed in rules, and we propose a practical core fragment for which reasoning becomes TC0-complete. Finally, we show that this fragment can be extended by allowing linear conjunctions in rule bodies, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

DatalogMTL: Computational Complexity and Expressive Power

Przemysław A. Wałęga
Bernardo Cuenca Grau
Mark Kaminski
Egor V. Kostylev

We study the complexity and expressive power of DatalogMTL - a knowledge representation language that extends Datalog with operators from metric temporal logic (MTL) and which has found applications in ontology-based data access and stream reasoning. We establish tight PSpace data complexity bounds and also show that DatalogMTL extended with negation on input predicates can express all queries in PSpace; this implies that MTL operators add significant expressive power to Datalog. Furthermore, we provide tight combined complexity bounds for the forward-propagating fragment of DatalogMTL, which was proposed in the context of stream reasoning, and show that it is possible to express all PSpace queries in the fragment extended with the falsum predicate.

PDF Details

AIJ Journal 2019 Journal Article

Foundations of ontology-based data access under bag semantics

Charalampos Nikolaou
Egor V. Kostylev
George Konstantinidis
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign to ontology predicates views over the data. The conventional semantics of OBDA is set-based—that is, the extension of the views defined by the mappings does not contain duplicate tuples. This treatment is, however, in disagreement with the standard semantics of database views and database management systems in general, which is based on bags and where duplicate tuples are retained by default. The distinction between set and bag semantics in databases is very significant in practice, and it influences the evaluation of aggregate queries. In this article, we propose and study a bag semantics for OBDA which provides a solid foundation for the future study of aggregate and analytic queries. Our semantics is compatible with both the bag semantics of database views and the set-based conventional semantics of OBDA. Furthermore, it is compatible with existing bag-based semantics for data exchange recently proposed in the literature. We show that adopting a bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability of query answering, we consider suitable restrictions along three dimensions, namely, the query language, the ontology language, and the adoption of the unique name assumption. Our investigation shows a complete picture of the computational properties of query answering under bag semantics over ontologies in the DL-Lite family.

Details DOI

AAAI Conference 2019 Conference Paper

Reasoning over Streaming Data in Metric Temporal Datalog

Przemysław Andrzej Wałęga
Mark Kaminski
Bernardo Cuenca Grau

We study stream reasoning in datalogMTL—an extension of Datalog with metric temporal operators. We propose a sound and complete stream reasoning algorithm that is applicable to a fragment datalogMTLFP of datalogMTL, in which propagation of derived information towards past time points is precluded. Memory consumption in our algorithm depends both on the properties of the rule set and the input data stream; in particular, it depends on the distances between timestamps occurring in data. This is undesirable since these distances can be very small, in which case the algorithm may require large amounts of memory. To address this issue, we propose a second algorithm, where the size of the required memory becomes independent on the timestamps in the data at the expense of disallowing punctual intervals in the rule set. Finally, we provide tight bounds to the data complexity of standard query answering in datalogMTLFP without punctual intervals in rules, which yield a new PSPACE lower bound to the data complexity of the full datalogMTL.

PDF Details

IJCAI Conference 2019 Conference Paper

Satisfaction and Implication of Integrity Constraints in Ontology-based Data Access

Charalampos Nikolaou
Bernardo Cuenca Grau
Egor V. Kostylev
Mark Kaminski
Ian Horrocks

We extend ontology-based data access with integrity constraints over both the source and target schemas. The relevant reasoning problems in this setting are constraint satisfaction—to check whether a database satisfies the target constraints given the mappings and the ontology—and source-to-target (resp. , target-to-source) constraint implication, which is to check whether a target constraint (resp. , a source constraint) is satisfied by each database satisfying the source constraints (resp. , the target constraints). We establish decidability and complexity bounds for all these problems in the case where ontologies are expressed in DL-LiteR and constraints range from functional dependencies to disjunctive tuple-generating dependencies.

PDF Details

IJCAI Conference 2018 Conference Paper

Stratified Negation in Limit Datalog Programs

Mark Kaminski
Bernardo Cuenca Grau
Egor V. Kostylev
Boris Motik
Ian Horrocks

There has recently been an increasing interest in declarative data analysis, where analytic tasks are specified using a logical language, and their implementation and optimisation are delegated to a general-purpose query engine. Existing declarative languages for data analysis can be formalised as variants of logic programming equipped with arithmetic function symbols and/or aggregation, and are typically undecidable. In prior work, the language of limit programs was proposed, which is sufficiently powerful to capture many analysis tasks and has decidable entailment problem. Rules in this language, however, do not allow for negation. In this paper, we study an extension of limit programs with stratified negation-as-failure. We show that the additional expressive power makes reasoning computationally more demanding, and provide tight data complexity bounds. We also identify a fragment with tractable data complexity and sufficient expressivity to capture many relevant tasks.

PDF Details

AAAI Conference 2018 Conference Paper

Stream Reasoning in Temporal Datalog

Alessandro Ronca
Mark Kaminski
Bernardo Cuenca Grau
Boris Motik
Ian Horrocks

In recent years, there has been an increasing interest in extending traditional stream processing engines with logical, rule-based, reasoning capabilities. This poses signiﬁcant theoretical and practical challenges since rules can derive new information and propagate it both towards past and future time points; as a result, streamed query answers can depend on data that has not yet been received, as well as on data that arrived far in the past. Stream reasoning algorithms, however, must be able to stream out query answers as soon as possible, and can only keep a limited number of previous input facts in memory. In this paper, we propose novel reasoning problems to deal with these challenges, and study their computational properties on Datalog extended with a temporal sort and the successor function—a core rule-based language for stream reasoning applications.

PDF Details

KR Conference 2018 Conference Paper

The Window Validity Problem in Rule-Based Stream Reasoning

Alessandro Ronca
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

Rule-based temporal query languages provide the expressive power and flexibility required to capture in a natural way complex analysis tasks over streaming data. Stream processing applications, however, typically require near real-time response using limited resources. In particular, it becomes essential that the underpinning query language has favourable computational properties and that stream processing algorithms are able to keep only a small number of previously received facts in memory at any point in time without sacrificing correctness. In this paper, we propose a recursive fragment of temporal Datalog with tractable data complexity and study the properties of a generic stream reasoning algorithm for this fragment. We focus on the window validity problem as a way to minimise the number of time points for which the stream reasoning algorithm needs to keep data in memory at any point in time.

IJCAI Conference 2017 Conference Paper

Foundations of Declarative Data Analysis Using Limit Datalog Programs

Mark Kaminski
Bernardo Cuenca Grau
Egor V. Kostylev
Boris Motik
Ian Horrocks

Motivated by applications in declarative data analysis, we study DatalogZ---an extension of positive Datalog with arithmetic functions over integers. This language is known to be undecidable, so we propose two fragments. In limit DatalogZ predicates are axiomatised to keep minimal/maximal numeric values, allowing us to show that fact entailment is coNExpTime-complete in combined, and coNP-complete in data complexity. Moreover, an additional stability requirement causes the complexity to drop to ExpTime and PTime, respectively. Finally, we show that stable DatalogZ can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.

PDF Details

IJCAI Conference 2017 Conference Paper

The Bag Semantics of Ontology-Based Data Access

Charalampos Nikolaou
Egor V. Kostylev
George Konstantinidis
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign views over the data to ontology predicates. Motivated by the need for OBDA systems supporting database-style aggregate queries, we propose a bag semantics for OBDA, where duplicate tuples in the views defined by the mappings are retained, as is the case in standard databases. We show that bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability, we consider a rather general class of queries and show its rewritability to a generalisation of the relational calculus to bags.

PDF Details

AIJ Journal 2016 Journal Article

Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies

Mark Kaminski
Yavor Nenov
Bernardo Cuenca Grau

We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i. e. , one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be rewritten into a linear program (i. e. , having at most one IDB body atom in each rule), thus providing a novel characterisation of Datalog rewritability in terms of linearisability. Motivated by this result, we propose the class of markable programs, which extends both Datalog and linear Disjunctive Datalog and admits Datalog rewritings of polynomial size. We show that our results can be seamlessly applied to ontological reasoning and identify two classes of non-Horn ontologies that admit Datalog rewritings of polynomial and exponential size, respectively. Finally, we shift our attention to conjunctive query answering and extend our results to the problem of computing a rewriting of a Disjunctive Datalog program that yields the same answers to a given query w. r. t. arbitrary data. Our empirical results suggest that a fair number of non-Horn ontologies are Datalog rewritable and that query answering over such ontologies becomes feasible using a Datalog engine.

Details DOI

JAIR Journal 2016 Journal Article

Module Extraction in Expressive Ontology Languages via Datalog Reasoning

Ana Armas Romero
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

Module extraction is the task of computing a (preferably small) fragment M of an ontology T that preserves a class of entailments over a signature of interest S. Extracting modules of minimal size is well-known to be computationally hard, and often algorithmically infeasible, especially for highly expressive ontology languages. Thus, practical techniques typically rely on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations ensure that M preserves all second-order entailments of T w.r.t. S, which is a stronger condition than is required in many applications, and may lead to unnecessarily large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach generalises existing approximations in an elegant way. More importantly, it allows extraction of modules that are tailored to preserve only specific kinds of entailments, and thus are often significantly smaller. Our evaluation on a wide range of ontologies confirms the feasibility and benefits of our approach in practice.

PDF Details DOI

IJCAI Conference 2015 Conference Paper

Computing Horn Rewritings of Description Logics Ontologies

Mark Kaminski
Bernardo Cuenca Grau

We study the problem of rewriting an ontology O1 expressed in a DL L1 into an ontology O2 in a Horn DL L2 such that O1 and O2 are equisatisfiable when extended with an arbitrary dataset. Ontologies that admit such rewritings are amenable to reasoning techniques ensuring tractability in data complexity. After showing undecidability whenever L1 extends ALCF, we focus on devising efficiently checkable conditions that ensure existence of a Horn rewriting. By lifting existing techniques for rewriting Disjunctive Datalog programs into plain Datalog to the case of arbitrary first-order programs with function symbols, we identify a class of ontologies that admit Horn rewritings of polynomial size. Our experiments indicate that many real-world ontologies satisfy our sufficient conditions and thus admit polynomial Horn rewritings.

PDF Details

AAAI Conference 2015 Conference Paper

Ontology Module Extraction via Datalog Reasoning

Ana Armas Romero
Mark Kaminski
Bernardo Cuenca Grau
Ian Horrocks

Module extraction—the task of computing a (preferably small) fragment M of an ontology T that preserves entailments over a signature Σ—has found many applications in recent years. Extracting modules of minimal size is, however, computationally hard, and often algorithmically infeasible. Thus, practical techniques are based on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations, however, ensure that M preserves all second-order entailments of T w. r. t. Σ, which is stronger than is required in many applications, and may lead to large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach not only generalises existing approximations in an elegant way, but it can also be tailored to preserve only specific kinds of entailments, which allows us to extract significantly smaller modules. An evaluation on widely-used ontologies has shown very encouraging results.

PDF Details

JAIR Journal 2015 Journal Article

PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner

Yujiao Zhou
Bernardo Cuenca Grau
Yavor Nenov
Mark Kaminski
Ian Horrocks

Answering conjunctive queries over ontology-enriched datasets is a core reasoning task for many applications. Query answering is, however, computationally very expensive, which has led to the development of query answering procedures that sacrifice either expressive power of the ontology language, or the completeness of query answers in order to improve scalability. In this paper, we describe a hybrid approach to query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable `pay-as-you-go' performance. The key feature of our approach is that it delegates the bulk of the computation to the datalog reasoner and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. Furthermore, although our main goal is to efficiently answer queries over OWL 2 ontologies and data, our technical results are very general and our approach is applicable to first-order knowledge representation languages that can be captured by rules allowing for existential quantification and disjunction in the head; our only assumption is the availability of a datalog reasoner and a fully-fledged reasoner for the language of interest, both of which are used as `black boxes'. We have implemented our techniques in the PAGOdA system, which combines the datalog reasoner RDFox and the OWL 2 reasoner HermiT. Our extensive evaluation shows that PAGOdA succeeds in providing scalable pay-as-you-go query answering for a wide range of OWL 2 ontologies, datasets and queries.

PDF Details DOI

AAAI Conference 2014 Conference Paper

Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning

Mark Kaminski
Yavor Nenov
Bernardo Cuenca Grau

We study the problem of rewriting a disjunctive datalog program into plain datalog. We show that a disjunctive program is rewritable if and only if it is equivalent to a linear disjunctive program, thus providing a novel characterisation of datalog rewritability. Motivated by this result, we propose weakly linear disjunctive datalog—a novel rule-based KR language that extends both datalog and linear disjunctive datalog and for which reasoning is tractable in data complexity. We then explore applications of weakly linear programs to ontology reasoning and propose a tractable extension of OWL 2 RL with disjunctive axioms. Our empirical results suggest that many non-Horn ontologies can be reduced to weakly linear programs and that query answering over such ontologies using a datalog engine is feasible in practice.

PDF Details