The Experts below are selected from a list of 3105 Experts worldwide ranked by ideXlab platform
Toni Urpí - One of the best experts on this subject based on the ideXlab platform.
-
Checking Query Containment with the CQC method
Data & Knowledge Engineering, 2005Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present the Constructive Query Containment (CQC) method to check Query Containment and Query Containment under constraints for queries over databases with safe negation in both IDB and EDB subgoals and with or without built-in predicates. The aim of the CQC method is to construct a counterexample that proves that the Query Containment relationship being checked does not hold. The method uses different Variable Instantiation Patterns (VIPs) to generate only relevant counterexamples according to the syntactic properties of the queries and the databases considered in each test.The main contribution of the CQC method is threefold: it handles broader cases of queries and database schemas than most previous methods, it checks "true" Containment instead of uniform Containment (which is a sufficient but not necessary condition for Containment) and it is not less efficient than other methods for the cases that they handle. Moreover, we prove also soundness and completeness of our method both for success and for failure.
-
Query Containment with negated idb predicates
Lecture Notes in Computer Science, 2003Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a method that checks Query Containment for queries with negated IDB predicates. Existing methods either deal only with restricted cases of negation or do not check actually Containment but uniform Containment, which is a sufficient but not necessary condition for Containment. Additionally, our queries may also contain equality, inequality and order comparisons. The generality of our approach allows our method to deal straightforwardly with Query Containment under constraints. Our method is sound and complete both for success and for failure and we characterize the databases where these properties hold. We also state the class of queries that can be decided by our method.
-
the constructive method for Query Containment checking
Database and Expert Systems Applications, 1999Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a new method that checks Query Containment for queries with negated derived atoms and/or integrity constraints. Existing methods for Query Containment checking that deal with these cases do not check actually Containment but another related property called Uniform Containment, which is a sufficient but not necessary condition for Containment. Our method can be seen as an extension of the canonical databases approach beyond the class of conjunctive queries.
-
Query Containment checking as a view updating problem
Database and Expert Systems Applications, 1998Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:In this paper we present a new approach that handles Query Containemnt problems by expressing them as a view updating problem. Since this approach is independent of any particular view updating method, it provides a general framework that joins research efforts in both the Query Containment checking and view updating fields. In particular, the larger development of current view updating technology allows us to check properly Query Containment when considering negative-derived literals or integrity constraints. Existing methods for Query Containment checking that deal with these cases do not check actually Containment but another related property called uniform Containment, which is a sufficient but not necessary condition for Containment.
Carles Farré - One of the best experts on this subject based on the ideXlab platform.
-
Checking Query Containment with the CQC method
Data & Knowledge Engineering, 2005Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present the Constructive Query Containment (CQC) method to check Query Containment and Query Containment under constraints for queries over databases with safe negation in both IDB and EDB subgoals and with or without built-in predicates. The aim of the CQC method is to construct a counterexample that proves that the Query Containment relationship being checked does not hold. The method uses different Variable Instantiation Patterns (VIPs) to generate only relevant counterexamples according to the syntactic properties of the queries and the databases considered in each test.The main contribution of the CQC method is threefold: it handles broader cases of queries and database schemas than most previous methods, it checks "true" Containment instead of uniform Containment (which is a sufficient but not necessary condition for Containment) and it is not less efficient than other methods for the cases that they handle. Moreover, we prove also soundness and completeness of our method both for success and for failure.
-
Query Containment with negated idb predicates
Lecture Notes in Computer Science, 2003Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a method that checks Query Containment for queries with negated IDB predicates. Existing methods either deal only with restricted cases of negation or do not check actually Containment but uniform Containment, which is a sufficient but not necessary condition for Containment. Additionally, our queries may also contain equality, inequality and order comparisons. The generality of our approach allows our method to deal straightforwardly with Query Containment under constraints. Our method is sound and complete both for success and for failure and we characterize the databases where these properties hold. We also state the class of queries that can be decided by our method.
-
the constructive method for Query Containment checking
Database and Expert Systems Applications, 1999Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a new method that checks Query Containment for queries with negated derived atoms and/or integrity constraints. Existing methods for Query Containment checking that deal with these cases do not check actually Containment but another related property called Uniform Containment, which is a sufficient but not necessary condition for Containment. Our method can be seen as an extension of the canonical databases approach beyond the class of conjunctive queries.
-
Query Containment checking as a view updating problem
Database and Expert Systems Applications, 1998Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:In this paper we present a new approach that handles Query Containemnt problems by expressing them as a view updating problem. Since this approach is independent of any particular view updating method, it provides a general framework that joins research efforts in both the Query Containment checking and view updating fields. In particular, the larger development of current view updating technology allows us to check properly Query Containment when considering negative-derived literals or integrity constraints. Existing methods for Query Containment checking that deal with these cases do not check actually Containment but another related property called uniform Containment, which is a sufficient but not necessary condition for Containment.
Ernest Teniente - One of the best experts on this subject based on the ideXlab platform.
-
Query Containment in entity sql
International Conference on Management of Data, 2013Co-Authors: Guillem Rull, Philip A Bernstein, Ivo Jose Garcia Dos Santos, Yannis Katsis, Sergey Melnik, Ernest TenienteAbstract:We describe a software architecture we have developed for a constructive Containment checker of Entity SQL queries defined over extended ER schemas expressed in Microsoft's Entity Data Model. Our application of interest is compilation of object-to-relational mappings for Microsoft's ADO.NET Entity Framework, which has been shipping since 2007. The supported language includes several features which have been individually addressed in the past but, to the best of our knowledge, they have not been addressed all at once before. Moreover, when embarking on an implementation, we found no guidance in the literature on how to modularize the software or apply published algorithms to a commercially-supported language. This paper reports on our experience in addressing these real-world challenges.
-
Query Containment in entity sql extended abstract
International Conference on Management of Data, 2013Co-Authors: Guillem Rull, Philip A Bernstein, Ivo Jose Garcia Dos Santos, Yannis Katsis, Sergey Melnik, Ernest TenienteAbstract:We describe a software architecture we have developed for a constructive Containment checker of Entity SQL queries defined over extended ER schemas expressed in Microsoft’s Entity Data Model. Our application of interest is compilation of object-torelational mappings for Microsoft's ADO.NET Entity Framework, which has been shipping since 2007. The supported language includes several features which have been individually addressed in the past but, to the best of our knowledge, they have not been addressed all at once before. Moreover, when embarking on an implementation, we found no guidance in the literature on how to modularize the software or apply published algorithms to a commercially-supported language. This paper reports on our experience in addressing these real-world challenges.
-
Checking Query Containment with the CQC method
Data & Knowledge Engineering, 2005Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present the Constructive Query Containment (CQC) method to check Query Containment and Query Containment under constraints for queries over databases with safe negation in both IDB and EDB subgoals and with or without built-in predicates. The aim of the CQC method is to construct a counterexample that proves that the Query Containment relationship being checked does not hold. The method uses different Variable Instantiation Patterns (VIPs) to generate only relevant counterexamples according to the syntactic properties of the queries and the databases considered in each test.The main contribution of the CQC method is threefold: it handles broader cases of queries and database schemas than most previous methods, it checks "true" Containment instead of uniform Containment (which is a sufficient but not necessary condition for Containment) and it is not less efficient than other methods for the cases that they handle. Moreover, we prove also soundness and completeness of our method both for success and for failure.
-
Query Containment with negated idb predicates
Lecture Notes in Computer Science, 2003Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a method that checks Query Containment for queries with negated IDB predicates. Existing methods either deal only with restricted cases of negation or do not check actually Containment but uniform Containment, which is a sufficient but not necessary condition for Containment. Additionally, our queries may also contain equality, inequality and order comparisons. The generality of our approach allows our method to deal straightforwardly with Query Containment under constraints. Our method is sound and complete both for success and for failure and we characterize the databases where these properties hold. We also state the class of queries that can be decided by our method.
-
the constructive method for Query Containment checking
Database and Expert Systems Applications, 1999Co-Authors: Carles Farré, Ernest Teniente, Toni UrpíAbstract:We present a new method that checks Query Containment for queries with negated derived atoms and/or integrity constraints. Existing methods for Query Containment checking that deal with these cases do not check actually Containment but another related property called Uniform Containment, which is a sufficient but not necessary condition for Containment. Our method can be seen as an extension of the canonical databases approach beyond the class of conjunctive queries.
Nabil Layaïda - One of the best experts on this subject based on the ideXlab platform.
-
SPARQL Query Containment Under Schema
Journal on Data Semantics, 2018Co-Authors: Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, Nabil LayaïdaAbstract:Query Containment is defined as the problem of determining if the result of a Query is included in the result of another Query for any dataset. It has major applications in Query optimization and knowledge base verification. To date, testing Query Containment has been performed using different techniques: Containment mapping, canonical databases, automata theory techniques and through a reduction to the validity problem in logic. Here, we use the latter technique to test Containment of SPARQL queries using an expressive modal logic called $$\mu $$ μ -calculus. For that purpose, we define an RDF graph encoding as a transition system which preserves its characteristics. In addition, queries and schema axioms are encoded as $$\mu $$ μ -calculus formulae. Thereby, Query Containment can be reduced to testing validity in the logic. We identify various fragments of SPARQL and description logic schema languages for which Containment is decidable. Additionally, we provide theoretically and experimentally proven procedures to check Containment of these decidable fragments. Finally, we propose a benchmark for Containment solvers which is used to test and compare the current state-of-the-art Containment solvers.
-
sparql Query Containment with shex constraints
Advances in Databases and Information Systems, 2017Co-Authors: Abdullah Abbas, Pierre Genevès, Cecile Roisin, Nabil LayaïdaAbstract:ShEx (Shape Expressions) is a language for expressing constraints on RDF graphs. We consider the problem of SPARQL Query Containment in the presence of ShEx constraints. We first propose a sound and complete procedure for the problem of Containment with ShEx, considering several SPARQL fragments. Particularly our procedure considers OPTIONAL Query patterns, that turns out to be an important fragment to be studied with schemas. We then show the complexity bounds of our problem with respect to the fragments considered. To the best of our knowledge, this is the first work addressing SPARQL Query Containment in the presence of ShEx constraints.
-
evaluating and benchmarking sparql Query Containment solvers
International Semantic Web Conference, 2013Co-Authors: Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, Nabil LayaïdaAbstract:Query Containment is the problem of deciding if the answers to a Query are included in those of another Query for any queried database. This problem is very important for Query optimization purposes. In the SPARQL context, it can be equally useful. This problem has recently been investigated theoretically and some Query Containment solvers are available. Yet, there were no benchmarks to compare theses systems and foster their improvement. In order to experimentally assess implementation strengths and limitations, we provide a first SPARQL Containment test benchmark. It has been designed with respect to both the capabilities of existing solvers and the study of typical queries. Some solvers support optional constructs and cycles, while other solvers support projection, union of conjunctive queries and RDF Schemas. No solver currently supports all these features or OWL entailment regimes. The study of Query demographics on DBPedia logs shows that the vast majority of queries are acyclic and a significant part of them uses UNION or projection. We thus test available solvers on their domain of applicability on three different benchmark suites. These experiments show that (i) tested solutions are overall functionally correct, (ii) in spite of its complexity, SPARQL Query Containment is practicable for acyclic queries, (iii) state-of-the-art solvers are at an early stage both in terms of capability and implementation.
-
A Benchmark for Semantic Web Query Containment, Equivalence and Satisfiability
2012Co-Authors: Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, Nabil LayaïdaAbstract:The problem of SPARQL Query Containment has recently attracted a lot of attention due to its fundamental purpose in Query optimization and information integration. New approaches to this problem, have been put forth, that can be implemented in practice. However, these approaches suffer from various limitations: coverage (size and type of queries), response time (how long it takes to determine Containment), and the technique applied to encode the problem. In order to experimentally assess implementation limitations, we designed a benchmark suite offering different experimental settings depending on the type of queries, projection and reasoning (RDFS). We have applied this benchmark to three available systems using different techniques highlighting the strengths and weaknesses of such systems.
-
SPARQL Query Containment under RDFS Entailment Regime
2012Co-Authors: Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, Nabil LayaïdaAbstract:The problem of SPARQL Query Containment is defined as determining if the result of one Query is included in the result of another for any RDF graph. Query Containment is important in many areas, including information integration, Query optimization, and reasoning about Entity-Relationship diagrams. We encode this problem into an expressive logic called mu-calculus: where RDF graphs become transition systems, queries and schema axioms become formulas. Thus, the Containment problem is reduced to formula satisfiability test. Beyond the logic's expressive power, satisfiability solvers are available for it. Hence, this study allows to exploit these advantages.
Andrea Calì - One of the best experts on this subject based on the ideXlab platform.
-
taming the infinite chase Query answering under expressive relational constraints
Journal of Artificial Intelligence Research, 2013Co-Authors: Andrea Calì, Georg Gottlob, Michael KiferAbstract:The chase algorithm is a fundamental tool for Query evaluation and for testing Query Containment under tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates. This paper introduces expressive classes of TGDs defined via syntactic restrictions: guarded TGDs (GTGDs) and weakly guarded sets of TGDs (WGT-GDs). For these classes, the chase procedure is not guaranteed to terminate and thus may have an infinite outcome. Nevertheless, we prove that the problems of conjunctive-Query answering and Query Containment under such TGDs are decidable. We provide decision procedures and tight complexity bounds for these problems. Then we show how EGDs can be incorporated into our results by providing conditions under which EGDs do not harmfully interact with TGDs and do not affect the decidability and complexity of Query answering. We show applications of the aforesaid classes of constraints to the problem of answering conjunctive queries in F-Logic Lite, an object-oriented ontology language, and in some tractable Description Logics.
-
conjunctive Query Containment under access limitations
International Conference on Conceptual Modeling, 2008Co-Authors: Andrea Calì, Davide MartinenghiAbstract:Access limitations may occur when Querying data sources over the web or heterogeneous data sources presented as relational tables: this happens, for instance, in Data Exchange and Integration, Data Warehousing, and Web Information Systems. Access limitations force certain attributes to be selected in order to access the tables. It is known that evaluating a conjunctive Query under such access restrictions amounts to evaluating a possibly recursive Datalog program. We address the problem of checking Containment of conjunctive queries under access limitations, which is highly relevant in Query optimization. Checking Containment in such a setting would amount to checking Containment of recursive Datalog programs of a certain class, while, for general Datalog programs, this problem is undecidable. We propose a decision procedure for Query Containment based on the novel notion of crayfish-chase, showing that Containment can be decided in co- nexptime , which improves upon the known bound of 2exptime . Moreover, by means of a direct proof, our technique provides a new insight into the structure of the problem.
-
taming the infinite chase Query answering under expressive relational constraints
Principles of Knowledge Representation and Reasoning, 2008Co-Authors: Andrea Calì, Georg Gottlob, Michael KiferAbstract:A crucial task in Knowledge Representation is answering queries posed over a knowledge base, represented as a set of facts plus a set of rules. In this paper we address the problem of answering conjunctive queries posed over knowledge bases where rules are an extension of Datalog rules, called Datalog∃ rules, that may have existentially quantified variables in the head; this kind of rules are traditionally called tuple-generating dependencies (TGDs) in the database literature, but they are broadly used in description logics and in ontological reasoning. In this setting, the chase algorithm is an important tool for Query answering. So far, most of the research has concentrated on cases where the chase terminates. We define and study large classes of TGDs under which the Query evaluation problems remain decidable even in case the chase does not terminate. We provide tight complexity bounds for such cases. Our results immediately extend to Query Containment.
