The Experts below are selected from a list of 6267 Experts worldwide ranked by ideXlab platform
Jerzy Marcinkowski - One of the best experts on this subject based on the ideXlab platform.
-
red spider meets a rainworm Conjunctive Query finite determinacy is undecidable
Symposium on Principles of Database Systems, 2016Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of the Red Spider method invented in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance Q0, Q= \Q1, Q2, ... Qk} such that the set Q of CQs does not determine CQ Q0 but finitely determines it. Finally, we claim that while Q0 is finitely determined by Q, there is no FO-rewriting of Q0, with respect to Q
-
red spider meets a rainworm Conjunctive Query finite determinacy is undecidable
arXiv: Databases, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of our Red Spider method which we developed in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance $Q_0$, ${\cal Q}= \{Q_1, Q_2, \ldots Q_k\}$ such that the set $\cal Q$ of CQs does not determine CQ $Q_0$ but finitely determines it. Finally, we claim that while $Q_0$ is finitely determined by $\cal Q$, there is no FO-rewriting of $Q_0$, with respect to $\cal Q$, and we outline a proof of this claim
-
the hunt for a red spider Conjunctive Query determinacy is undecidable
arXiv: Databases, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known, long-standing open problem in relational databases theory, showing that the Conjunctive Query determinacy problem (in its "unrestricted" version) is undecidable.
-
LICS - The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
2015 30th Annual ACM IEEE Symposium on Logic in Computer Science, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known, long-standing open problem in relational databases theory, showing that the Conjunctive Query determinacy problem (in its "unrestricted" version) is undecidable.
Ian Horrocks - One of the best experts on this subject based on the ideXlab platform.
-
introducing nominals to the combined Query answering approaches for el
arXiv: Artificial Intelligence, 2013Co-Authors: Giorgio Stefanoni, Boris Motik, Ian HorrocksAbstract:So-called combined approaches answer a Conjunctive Query over a description logic ontology in three steps: first, they materialise certain consequences of the ontology and the data; second, they evaluate the Query over the data; and third, they filter the result of the second phase to eliminate unsound answers. Such approaches were developed for various members of the DL-Lite and the EL families of languages, but none of them can handle ontologies containing nominals. In our work, we bridge this gap and present a combined Query answering approach for ELHO---a logic that contains all features of the OWL 2 EL standard apart from transitive roles and complex role inclusions. This extension is nontrivial because nominals require equality reasoning, which introduces complexity into the first and the third step. Our empirical evaluation suggests that our technique is suitable for practical application, and so it provides a practical basis for Conjunctive Query answering in a large fragment of OWL 2 EL.
-
Conjunctive Query answering for the description logic shiq
Journal of Artificial Intelligence Research, 2008Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, Conjunctive Query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the Query. In this paper, we consider unions of Conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show decidability of Query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query, which is optimal. Regarding data complexity, we prove containment in co-NP.
-
Conjunctive Query answering for the description logic shiq
International Joint Conference on Artificial Intelligence, 2007Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether Conjunctive Query answering over DL knowledge bases is decidable if transitive roles are admitted in the Query. In this paper, we consider Conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show that Query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query. Regarding data complexity, we prove co-NP-completeness.
-
IJCAI - Conjunctive Query answering for the description logic SHIQ
2007Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether Conjunctive Query answering over DL knowledge bases is decidable if transitive roles are admitted in the Query. In this paper, we consider Conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show that Query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query. Regarding data complexity, we prove co-NP-completeness.
-
Conjunctive Query entailment for shoq
Description Logics, 2007Co-Authors: Birte Glimm, Ian Horrocks, Ulrike SattlerAbstract:An important reasoning task, in addition to the standard DL reasoning services, is Conjunctive Query answering. In this paper, we present a decision procedure for Conjunctive Query entailment in the expressive Description Logic SHOQ. This is, to the best of our knowledge, the first decision procedure for Conjunctive Query entailment in a logic that allows for nominals. We achieve this by combining the techniques used in the Conjunctive Query entailment procedure for SHIQ with the techniques proposed for a restricted class of Conjunctive queries in SHOQ.
Birte Glimm - One of the best experts on this subject based on the ideXlab platform.
-
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Journal of Artificial Intelligence Research, 2010Co-Authors: Sebastian Rudolph, Birte GlimmAbstract:Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard Query language in databases, have recently gained significant attention as an expressive formalism for Querying Description Logic knowledge bases. Several different techniques for deciding Conjunctive Query entailment are available for a wide range of DLs. Nevertheless, the combination of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL causes unsolvable problems for the techniques hitherto available. We tackle this problem and present a decidability result for entailment of unions of Conjunctive queries in the DL ALCHOIQb that contains all three problematic constructors simultaneously. Provided that queries contain only simple roles, our result also shows decidability of entailment of (unions of) Conjunctive queries in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards Conjunctive Query entailment decision procedures for the Description Logics underlying the OWL standards.
-
status qio Conjunctive Query entailment is decidable
Principles of Knowledge Representation and Reasoning, 2010Co-Authors: Birte Glimm, Sebastian RudolphAbstract:Description Logics (DLs) are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries (CQs), the standard Query language in databases, have recently gained significant attention for Querying DL knowledge bases. Several different techniques are available for a wide range of DLs. Nevertheless, for OWL 1 DL and OWL 2 DL, decidability of CQ entailment is an open problem. So far, the combination of nominals, inverse roles, and number restrictions caused unsolvable problems. We tackle this problem and present a decidability result for entailment of unions of CQs in a DL with all three problematic constructors. For queries with only simple roles, our result also shows decidability in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards CQ entailment decision procedures for OWL.
-
Conjunctive Query answering for the description logic shiq
Journal of Artificial Intelligence Research, 2008Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, Conjunctive Query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the Query. In this paper, we consider unions of Conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show decidability of Query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query, which is optimal. Regarding data complexity, we prove containment in co-NP.
-
Conjunctive Query answering for the description logic shiq
International Joint Conference on Artificial Intelligence, 2007Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether Conjunctive Query answering over DL knowledge bases is decidable if transitive roles are admitted in the Query. In this paper, we consider Conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show that Query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query. Regarding data complexity, we prove co-NP-completeness.
-
IJCAI - Conjunctive Query answering for the description logic SHIQ
2007Co-Authors: Birte Glimm, Ian Horrocks, Carsten Lutz, Uli SattlerAbstract:Conjunctive queries play an important role as an expressive Query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether Conjunctive Query answering over DL knowledge bases is decidable if transitive roles are admitted in the Query. In this paper, we consider Conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the Query and the knowledge base. We show that Query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for Query answering that needs time single exponential in the size of the KB and double exponential in the size of the Query. Regarding data complexity, we prove co-NP-completeness.
Tomasz Gogacz - One of the best experts on this subject based on the ideXlab platform.
-
red spider meets a rainworm Conjunctive Query finite determinacy is undecidable
Symposium on Principles of Database Systems, 2016Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of the Red Spider method invented in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance Q0, Q= \Q1, Q2, ... Qk} such that the set Q of CQs does not determine CQ Q0 but finitely determines it. Finally, we claim that while Q0 is finitely determined by Q, there is no FO-rewriting of Q0, with respect to Q
-
red spider meets a rainworm Conjunctive Query finite determinacy is undecidable
arXiv: Databases, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of our Red Spider method which we developed in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance $Q_0$, ${\cal Q}= \{Q_1, Q_2, \ldots Q_k\}$ such that the set $\cal Q$ of CQs does not determine CQ $Q_0$ but finitely determines it. Finally, we claim that while $Q_0$ is finitely determined by $\cal Q$, there is no FO-rewriting of $Q_0$, with respect to $\cal Q$, and we outline a proof of this claim
-
the hunt for a red spider Conjunctive Query determinacy is undecidable
arXiv: Databases, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known, long-standing open problem in relational databases theory, showing that the Conjunctive Query determinacy problem (in its "unrestricted" version) is undecidable.
-
LICS - The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
2015 30th Annual ACM IEEE Symposium on Logic in Computer Science, 2015Co-Authors: Tomasz Gogacz, Jerzy MarcinkowskiAbstract:We solve a well known, long-standing open problem in relational databases theory, showing that the Conjunctive Query determinacy problem (in its "unrestricted" version) is undecidable.
Paraschos Koutris - One of the best experts on this subject based on the ideXlab platform.
-
ranked enumeration of Conjunctive Query results
International Conference on Database Theory, 2021Co-Authors: Shaleen Deep, Paraschos KoutrisAbstract:We study the problem of enumerating answers of Conjunctive Queries ranked according to a given ranking function. Our main contribution is a novel algorithm with small preprocessing time, logarithmic delay, and non-trivial space usage during execution. To allow for efficient enumeration, we exploit certain properties of ranking functions that frequently occur in practice. To this end, we introduce the notions of decomposable and compatible (w.r.t. a Query decomposition) ranking functions, which allow for partial aggregation of tuple scores in order to efficiently enumerate the output. We complement the algorithmic results with lower bounds that justify why restrictions on the structure of ranking functions are necessary. Our results extend and improve upon a long line of work that has studied ranked enumeration from both a theoretical and practical perspective.
-
ranked enumeration of Conjunctive Query results
arXiv: Databases, 2019Co-Authors: Shaleen Deep, Paraschos KoutrisAbstract:We investigate the enumeration of top-k answers for Conjunctive queries against relational databases according to a given ranking function. The task is to design data structures and algorithms that allow for efficient enumeration after a preprocessing phase. Our main contribution is a novel priority queue based algorithm with near-optimal delay and non-trivial space guarantees that are output sensitive and depend on structure of the Query. In particular, we exploit certain desirable properties of ranking functions that frequently occur in practice and degree information in the database instance, allowing for efficient enumeration. We introduce the notion of {\em decomposable} and {\em compatible} ranking functions in conjunction with Query decomposition, a property that allows for partial aggregation of tuple scores in order to efficiently enumerate the ranked output. We complement the algorithmic results with lower bounds justifying why certain assumptions about properties of ranking functions are necessary and discuss popular conjectures providing evidence for optimality of enumeration delay guarantees. Our results extend and improve upon a long line of work that has studied ranked enumeration from both theoretical and practical perspective.
-
PODS - Compressed Representations of Conjunctive Query Results
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018Co-Authors: Shaleen Deep, Paraschos KoutrisAbstract:Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole materialized output if we plan to reuse it further down a data processing pipeline. Motivated by this problem, we study the construction of space-efficient compressed representations of the output of Conjunctive queries, with the goal of supporting the efficient access of the intermediate compressed result for a given access pattern. In particular, we initiate the study of an important tradeoff: minimizing the space necessary to store the compressed result, versus minimizing the answer time and delay for an access request over the result. Our main contribution is a novel parameterized data structure, which can be tuned to trade off space for answer time. The tradeoff allows us to control the space requirement of the data structure precisely, and depends both on the structure of the Query and the access pattern. We show how we can use the data structure in conjunction with Query decomposition techniques in order to efficiently represent the outputs for several classes of Conjunctive queries.
-
Compressed Representations of Conjunctive Query Results
arXiv: Databases, 2017Co-Authors: Shaleen Deep, Paraschos KoutrisAbstract:Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole materialized output if we plan to reuse it further down a data processing pipeline. Motivated by this problem, we study the construction of space-efficient compressed representations of the output of Conjunctive queries, with the goal of supporting the efficient access of the intermediate compressed result for a given access pattern. In particular, we initiate the study of an important tradeoff: minimizing the space necessary to store the compressed result, versus minimizing the answer time and delay for an access request over the result. Our main contribution is a novel parameterized data structure, which can be tuned to trade off space for answer time. The tradeoff allows us to control the space requirement of the data structure precisely, and depends both on the structure of the Query and the access pattern. We show how we can use the data structure in conjunction with Query decomposition techniques, in order to efficiently represent the outputs for several classes of Conjunctive queries.