Browsing by Author "Libkin, Leonid"

Now showing 1 - 12 of 12
  • Thumbnail Image
    Item
    Game-based notions of locality over finite models
    (2008) Arenas, Marcelo; Barceló, Pablo; Libkin, Leonid
    Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighbourhood of its free variables. Such notions have proved to be useful in many applications. They all, however, refer to isomorphisms of neighbourhoods, which most local logics cannot test. A stronger notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighbourhood. Since the expressiveness of many logics can be characterized by games, one can also say that the truth value of a formula is determined by the type, with respect to a game, of that small neighbourhood. Such game-based notions of locality can often be applied when traditional isomorphism-based notions of locality cannot. Our goal is to study game-based notions of locality. We work with an abstract view of games that subsumes games for many logics. We look at three, progressively more complicated locality notions. The easiest requires only very mild conditions on the game and works for most logics of interest. The other notions, based on Hanf's and Gaifman's theorems, require more restrictions. We state those restrictions and give examples of logics that satisfy and fail the respective game-based notions of locality. (c) 2007 Elsevier B.V. All rights reserved.
  • No Thumbnail Available
    Item
    Graph path navigation
    (2019) Arenas Saavedra, Marcelo Alejandro; Barceló, Pablo; Libkin, Leonid; Sakr, Sherif; Zomaya, Albert Y.
  • Thumbnail Image
    Item
    On the complexity of verifying consistency of XML specifications
    (SIAM PUBLICATIONS, 2008) Arenas, Marcelo; Fan, Wenfei; Libkin, Leonid
    XML specifications often consist of a type definition (typically, a document type definition (DTD)) and a set of integrity constraints. It has been shown previously that such specifications can be inconsistent, and thus it is often desirable to check consistency at compile time. It is known [W. Fan and L. Libkin, J. ACM, 49 (2002), pp. 368 - 406] that for general keys, foreign keys, and DTDs the consistency problem is undecidable; however, it becomes NP-complete when all keys are one-attribute (unary) and tractable, if no foreign keys are used. In this paper, we consider a variety of previously studied constraints for XML data and investigate the complexity of the consistency problem. Our main conclusion is that, in the presence of foreign key constraints, compile-time veri. cation of consistency is infeasible. We look at absolute constraints that hold in the entire document and relative constraints that hold only in a part of the document. For absolute constraints, we prove decidability and establish complexity bounds for primary multiattribute keys and unary foreign keys and study unary constraints that involve regular expressions. For relative constraints, we prove that even for unary constraints the consistency problem is undecidable. We also show that results continue to hold for extended DTDs, a more expressive typing mechanism for XML.
  • Thumbnail Image
    Item
    Querying Graphs with Data
    (2016) Libkin, Leonid; Martensm, Wim; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Querying Regular Graph Patterns
    (2014) Barcelo, Pablo; Libkin, Leonid; Reutter, Juan L.
    Graph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, that is, graph patterns. While queries need to be posed against such data, techniques for querying patterns are generally lacking, and properties of such queries are not well understood.
  • Thumbnail Image
    Item
    Regular expressions for data words
    (2015) Libkin, Leonid; Tan, Tony; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
    (2011) Arenas, Marcelo; Barcelo, Pablo; Libkin, Leonid
    Nested words provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words.
  • Thumbnail Image
    Item
    Research Directions for Principles of Data Management (Abridged)
    (2016) Abiteboul, Serge; Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Bienvenu, Meghyn; Calvanese, Diego; Claire, David; Hull, Richard; Hüllermeier, Eyke; Kimelfeld, Benny; Libkin, Leonid
  • Thumbnail Image
    Item
    Solutions and query rewriting in data exchange
    (2013) Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Fagin, Ronald; Libkin, Leonid
  • No Thumbnail Available
    Item
    Static analysis and query answering for incomplete data trees with constraints
    (2013) Gheerbrant, Amélie; Libkin, Leonid; Reutter de la Maza, Juan Lorenzo; Tannen, Val; Wong, Limsoon; Libkin, Leonid; Fan, Wenfei; Tan, Wang Chiew; Fourman, Michael
  • Thumbnail Image
    Item
    Trial: A Navigational Algebra for RDF Triplestores
    (2018) Libkin, Leonid; Reutter de la Maza, Juan; Soto Suárez, Adrián Andrés; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    XML data exchange: Consistency and query answering
    (ASSOC COMPUTING MACHINERY, 2008) Arenas, Marcelo; Libkin, Leonid
    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. Theoretical foundations of data exchange have recently been investigated for relational data.