Browsing by Author "Jayaram, Rajesh"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Counting the Answers to a Query
    (2022) Arenas, Marcelo; Croquevielle, Luis Alberto; Jayaram, Rajesh; Riveros, Cristian
    Counting the answers to a query is a fundamental problem in databases, with several applications in the evaluation, optimization, and visualization of queries. Unfortunately, counting query answers is a #P-hard problem in most cases, so it is unlikely to be solvable in polynomial time. Recently, new results on approximate counting have been developed, specifically by showing that some problems in automata theory admit fully polynomial-time randomized approximation schemes. These results have several implications for the problem of counting the answers to a query; in particular, for graph and conjunctive queries. In this work, we present the main ideas of these approximation results, by using labeled DAGs instead of automata to simplify the presentation. In addition, we review how to apply these results to count query answers in different areas of databases.
  • Thumbnail Image
    Item
    #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
    (ASSOC COMPUTING MACHINERY, 2021) Arenas, Marcelo; Alberto Croquevielle, Luis; Jayaram, Rajesh; Riveros, Cristian
    In this work, we study two simple yet general complexity classes, based on logspace Turing machines, that provide a unifying framework for efficient query evaluation in areas such as information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting, and uniform generation of solutions, and show that they have several desirable properties in this respect.