Search

Your search keyword '"Leonid Libkin"' showing total 503 results
Start Over Author "Leonid Libkin"
503 results on '"Leonid Libkin"'

221. Updating graph databases with Cypher

Author

Leonid Libkin, Hannes Voigt, Petra Selmer, Stefan Plantikow, Victor Marsault, Alastair Green, Martin Schuster, Tobias Lindaaker, Paolo Guagliardo, Neo4j, School of Informatics, University of Edinburgh, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Abbot Informatics, and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Atomicity, SQL, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Information retrieval, Graph database, Syntax (programming languages), Computer science, Relational database, 05 social sciences, General Engineering, 010501 environmental sciences, Relational operator, computer.software_genre, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Set (abstract data type), 0502 economics and business, Graph (abstract data type), computer, ComputingMilieux_MISCELLANEOUS, 050203 business & management, 0105 earth and related environmental sciences, computer.programming_language
Abstract

The paper describes the present and the future of graph updates in Cypher, the language of the Neo4j property graph database and several other products. Update features include those with clear analogs in relational databases, as well as those that do not correspond to any relational operators. Moreover, unlike SQL, Cypher updates can be arbitrarily intertwined with querying clauses. After presenting the current state of update features, we point out their shortcomings, most notably violations of atomicity and non-deterministic behavior of updates. These have not been previously known in the Cypher community. We then describe the industry-academia collaboration on designing a revised set of Cypher update operations. Based on discovered shortcomings of update features, a number of possible solutions were devised. They were presented to key Cypher users, who were given the opportunity to comment on how update features are used in real life, and on their preferences for proposed fixes. As the result of the consultation, a new set of update operations for Cypher were designed. Those led to a streamlined syntax, and eliminated the unexpected and problematic behavior that original Cypher updates exhibited.

Published
2019
Full Text
View/download PDF

222. PG-Keys: Keys for Property Graphs

Author

Keith W. Hare, George H. L. Fletcher, Sławek Staworko, Michael Schmidt, Leonid Libkin, Jan Hidders, Stefania Dumbrava, Angela Bonifati, Victor E. Lee, Bei Li, Filip Murlak, Juan F. Sequeda, Wim Martens, Ognjen Savkovic, Dominik Tomaszuk, Renzo Angles, Josh Perryman, Universidad de Talaca, Université Claude Bernard Lyon 1 - Faculté des sciences (UCBL FS), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Institut Polytechnique de Paris (IP Paris), Eindhoven University of Technology [Eindhoven] (TU/e), JCC Consulting Inc, Neo4j, Birkbeck College [University of London], TigerGraph, Google LLC, Laboratory for the Foundations of Computer Science [Edinburgh] (LFCS), University of Edinburgh, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), University of Bayreuth, Uniwersytet Warszawski, Interos Inc., Free University of Bozen-Bolzano, Amazon Web Services [Seattle] (AWS), data.world, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Bialystok, Réponse efficace aux requêtes sous mises à jourEQUUS - ANR-19-CE48-0019AAPG2019 - 2019, Université Claude Bernard Lyon 1 - Faculté des sciences et technologies (UCBL FST), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), École normale supérieure - Paris (ENS Paris), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Focus (computing), Property (philosophy), [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Standardization, Computer science, business.industry, key constraints, 0102 computer and information sciences, 02 engineering and technology, Linked data, 01 natural sciences, 010201 computation theory & mathematics, 020204 information systems, Data integrity, Benchmark (surveying), 0202 electrical engineering, electronic engineering, information engineering, Position (finance), Use case, Software engineering, business, property graphs
Abstract

International audience; We report on a community effort between industry and academia to shape the future of property graph constraints. The standardization for a property graph query language is currently underway through the ISO Graph Query Language (GQL) project. Our position is that this project should pay close attention to schemas and constraints, and should focus next on key constraints. The main purposes of keys are enforcing data integrity and allowing the referencing and identifying of objects. Motivated by use cases from our industry partners, we argue that key constraints should be able to have different modes, which are combinations of basic restriction that require the key to be exclusive, mandatory, and singleton. Moreover, keys should be applicable to nodes, edges, and properties since these all can represent valid real-life entities. Our result is PG-Keys, a flexible and powerful framework for defining key constraints, which fulfills the above goals. PG-Keys is a design by the Linked Data Benchmark Council's Property Graph Schema Working Group, consisting of members from industry, academia, and ISO GQL standards group, intending to bring the best of all worlds to property graph practitioners. PG-Keys aims to guide the evolution of the standardization efforts towards making systems more useful, powerful, and expressive. CCS CONCEPTS • Information systems → Integrity checking; • Theory of computation → Data modeling; Database constraints theory.

Published
2021
Full Text
View/download PDF

243. Knowledge-Preserving Certain Answers for SQL-like Queries

Author

Leonid Libkin, Paolo Guagliardo, Etienne Toussaint, University of Edinburgh, Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Work partially supported by EPSRC grants M025268 and N023056, EPSRC Centre for Doctoral Training in Data Science, a grant from the Foundation Sciences Mathématiquesde Paris under the FSMP Chairs program, and the Royal Society through a Wolfson Research Merit Award., Calvanese, Diego, Erdem, Esra, Thielscher, Michael, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
SQL, Information retrieval, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Relational database, Computer science, Semantics (computer science), media_common.quotation_subject, 02 engineering and technology, Certainty, Query language, Data modeling, Set (abstract data type), Data model, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, computer, media_common, computer.programming_language
Abstract

International audience; Answering queries over incomplete data is based on finding answers that are certainly true, independently of how missing values are interpreted. This informal description has given rise to several different mathematical definitions of certainty. To unify them, a framework based on "explanations", or extra information about incomplete data, was recently proposed. It partly succeeded in justifying query answering methods for relational databases under set semantics, but had two major limitations. First, it was firmly tied to the set data model, and a fixed way of comparing incomplete databases with respect to their information content. These assumptions fail for reallife database queries in languages such as SQL that use bag semantics instead. Second, it was restricted to queries that only manipulate data, while in practice most analytical SQL queries invent new values, typically via arithmetic operations and aggregation. To leverage our understanding of the notion of certainty for queries in SQL-like languages, we consider incomplete databases whose information content may be enriched by additional knowledge. The knowledge order among them is derived from their semantics, rather than being fixed a priori. The resulting framework allows us to capture and justify existing notions of certainty, and extend these concepts to other data models and query languages. As natural applications, we provide for the first time a well-founded definition of certain answers for the relational bag data model and for valueinventing queries on incomplete databases, addressing the key shortcomings of previous approaches.

Published
2020
Full Text
View/download PDF

244. Coping with Incomplete Data: Recent Advances

Author

Paolo Guagliardo, Leonid Libkin, Etienne Toussaint, Marco Console, University of Edinburgh, Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Most results presented here were obtained by the authors while they were supported by EPSRC projects M025268 'VADA: Value Added Data Systems' and N023056 'Managing Incomplete Data – New Foundations'. Work on the semantics of SQL was in conjunction with our collaboration with Neo4j Inc, supported by a grant from them. Finally, the third author is grateful to Foundation Sciences Mathématiques de Paris for supporting his stay in Paris in the Fall of 2019, during which some of this work was done., Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
SQL, Coping (psychology), Correctness, Computer science, Relational database, media_common.quotation_subject, 02 engineering and technology, Many-valued logics, Complete information, 020204 information systems, incomplete information, 0202 electrical engineering, electronic engineering, information engineering, approximate query answering, certain answers, many-valued logics, naive evaluation, relational databases, Relational databases, media_common, computer.programming_language, Information retrieval, Naiveevaluation, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Probabilistic logic, Certain answers, Certainty, Approximate query answering, 020201 artificial intelligence & image processing, computer, Incomplete information
Abstract

International audience; Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on threevalued logic. Can we find a middle ground, and produce correct answers efficiently? The paper surveys results of the last few years motivated by this question. We reexamine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers.

Published
2020
Full Text
View/download PDF

245. Reasoning about measures of unmeasurable sets

Author

Matthias F. J. Hofer, Marco Console, Leonid Libkin, University of Edinburgh, Value from Data (VALDA ), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Work partially supported by EPSRC grants M025268, N023056, and S003800., Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
Discrete mathematics, Unit sphere, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Lebesgue measure, Intersection (set theory), Computer science, Incomplete Information, Measurable Sets, 010102 general mathematics, 02 engineering and technology, Space (mathematics), 01 natural sciences, Measure (mathematics), Set (abstract data type), VC dimension, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Incomplete Information, Measurable Sets, Point (geometry), 0101 mathematics
Abstract

International audience; In a variety of reasoning tasks, one estimates the likelihood of events by means of volumes of sets they define. Such sets need to be measurable, which is usually achieved by putting bounds, sometimes ad hoc, on them. We address the question how unbounded or unmeasurable sets can be measured nonetheless. Intuitively, we want to know how likely a randomly chosen point is to be in a given set, even in the absence of a uniform distribution over the entire space. To address this, we follow a recently proposed approach of taking intersection of a set with balls of increasing radius, and defining the measure by means of the asymptotic behavior of the proportion of such balls taken by the set. We show that this approach works for every set definable in first-order logic with the usual arithmetic over the reals (addition, multiplication, exponentiation, etc.), and every uniform measure over the space, of which the usual Lebesgue measure (area, volume, etc.) is an example. In fact we establish a correspondence between the good asymptotic behavior and the finiteness of the VC dimension of definable families of sets. Towards computing the measure thus defined, we show how to avoid the asymptotics and characterize it via a specific subset of the unit sphere. Using definability of this set, and known techniques for sampling from the unit sphere, we give two algorithms for estimating our measure of unbounded unmeasurable sets, with deterministic and probabilistic guarantees, the latter being more efficient. Finally we show that a discrete analog of this measure exists and is similarly well-behaved.

Published
2020
Full Text
View/download PDF

248. Relational and XML Data Exchange

Author

Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Filip Murlak, Marcelo Arenas, Pablo Barcelo, Leonid Libkin, and Filip Murlak

Subjects
Data structures (Computer science), Information theory
Abstract

Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Such a target instance should correctly represent information from the source instance under the constraints imposed by the target schema, and it should allow one to evaluate queries on the target instance in a way that is semantically consistent with the source data. Data exchange is an old problem that re-emerged as an active research topic recently, due to the increased need for exchange of data in various formats, often in e-business applications. In this lecture, we give an overview of the basic concepts of data exchange in both relational and XML contexts. We give examples of data exchange problems, and we introduce the main tasks that need to addressed. We then discuss relational data exchange, concentrating on issues such as relational schema mappings, materializing target instances (including canonical solutions and cores), query answering, and query rewriting. After that, we discuss metadata management, i.e., handling schema mappings themselves. We pay particular attention to operations on schema mappings, such as composition and inverse. Finally, we describe both data exchange and metadata management in the context of XML. We use mappings based on transforming tree patterns, and we show that they lead to a host of new problems that did not arise in the relational case, but they need to be addressed for XML. These include consistency issues for mappings and schemas, as well as imposing tighter restrictions on mappings and queries to achieve tractable query answering in data exchange. Table of Contents: Overview / Relational Mappings and Data Exchange / Metadata Management / XML Mappings and Data Exchange

Published
2022

250. Correctness of SQL Queries on Databases with Nulls

Author

Leonid Libkin and Paolo Guagliardo

Subjects
SQL, Theoretical computer science, Correctness, Database, Computer science, InformationSystems_DATABASEMANAGEMENT, 0102 computer and information sciences, 02 engineering and technology, Relational algebra, computer.software_genre, 01 natural sciences, Null (SQL), 010201 computation theory & mathematics, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Query by Example, computer, Software, Information Systems, computer.programming_language
Abstract

Multiple issues with SQL's handling of nulls have been well documented. Having efficiency as its main goal, SQL disregards the standard notion of correctness on incomplete databases -- certain answers -- due to its high complexity. As a result, the evaluation of SQL queries on databases with nulls may produce answers that are just plain wrong. However, SQL evaluation can be modified, at least for relational algebra queries, to approximate certain answers, i.e., return only correct answers. We examine recently proposed approximation schemes for certain answers and analyze their complexity, both theoretical bounds and real-life behavior

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results