Browsing by Subject "Conjunctive queries"

Now showing items 1-4 of 4

    • A more general theory of static approximations for conjunctive queries 
      Barceló, Pablo; Romero, Miguel; Zeume, Thomas (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018)
      Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. Approximating a hard CQ by a query from such a fragment can thus allow for an efficient approximate evaluation. ...
    • Efficient approximations of conjunctive queries 
      Barceló Baeza, Pablo; Libkin, Leonid; Romero, Miguel (Society for Industrial and Applied Mathematics, 2014)
      When finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. ...
    • Semantic Acyclicity on Graph Databases 
      Barceló Baeza, Pablo; Romero Orth, Miguel; Vardi, Moshe (SIAM, 2016)
      It is known that unions of acyclic conjunctive queries (CQs) can be evaluated in linear time, as opposed to arbitrary CQs, for which the evaluation problem is NP-complete. It follows from techniques in the area of ...
    • The complexity of reverse engineering problems for conjunctive queries 
      Barceló Baeza, Pablo; Romero, Miguel (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      Reverse engineering problems for conjunctive queries (CQs), such as query by example (QBE) ordefinability, take a set of user examples and convert them into an explanatory CQ. Despite theirimportance, the complexity of ...