nucleation

databases

Graph View

93 items with this tag.

Oct 30, 2026
QUESTION-340: When does a cache replacement value based on distance from the current query beat recency-based eviction: does a competitive analysis, or an analysis under a stated distribution of query paths, say so, and do experiments in another system that vary cycle length relative to cache size recover the crossover with MRU?
- databases
- operations-research
Oct 30, 2026
QUESTION-347: On another database and web stack with native materialized views and queries of graded cost, does a stored query result kept current on every update lose to recomputation exactly when reading it costs about as much as recomputing it and its refresh runs on the resource that serves requests, and win otherwise?
- databases
- operations-research
Oct 30, 2026
THEORY-1244: No access method is optimal on read, update and memory overhead at once: bounding any two of the three forces the third above a hard lower bound that cannot be further reduced
- databases
Oct 21, 2026
THEORY-832: For strict combining functions and m attribute-sorted lists of N objects whose orderings are probabilistically independent, no correct top-k algorithm does essentially better than Fagin's Algorithm in the worst case with high probability: every one needs on the order of N^((m−1)/m) k^(1/m) accesses
- databases
- information-retrieval
Oct 20, 2026
QUESTION-224: Is Bruno and Chaudhuri's single-index online tuner within some constant, such as 3 + 2f, of the offline optimum on every workload whose per-statement savings and losses are at most a fraction f of the build cost?
- databases
- operations-research
Oct 20, 2026
QUESTION-225: Are why-provenance and, for traceable queries, where-provenance preserved by Buneman, Khanna and Tan's rewrite system, and is traceability necessary for where-provenance to be preserved?
- databases
- logic
Oct 20, 2026
QUESTION-227: Does the widen-on-push, narrow-on-fetch rule for a cached interval's width converge to within a stated factor of the best fixed width, and does it hold its cost against the best fixed width and an adaptive cache-or-not rule on data other than its authors' traces?
- databases
- operations-research
Oct 20, 2026
QUESTION-230: Do the released HNSW, NSG and fast-preprocessing DiskANN builds, run independently on Indyk and Xu's published hard instances at the stated parameters, need a search queue of about a tenth of the points before recall@5 rises above zero, and does the same trap appear on natural data with adversarially chosen queries?
- databases
- information-retrieval
Oct 20, 2026
QUESTION-237: Does semantic caching keep its ordering against page caching once probe and remainder computation and region upkeep are charged, or in an implemented client-server system?
- databases
- information-retrieval
Oct 20, 2026
QUESTION-238: Does database cracking keep its measured costs against a scan and an upfront sort in another implementation, measured over a long sequence of random range queries?
- databases
Oct 20, 2026
THEORY-815: Layering a navigable small-world graph on nested random subsets of the data, with links separated by length scale and each layer's degree capped, makes greedy nearest-neighbour search cost grow logarithmically with the number of items on data of low intrinsic dimension, where the single-layer graph's cost grows polylogarithmically
Oct 19, 2026
QUESTION-187: Does greedy layered search on the graph HNSW actually builds take expected O(log N) distance computations to a stated recall, under a stated condition on the data such as bounded doubling dimension?
Oct 19, 2026
QUESTION-188: Is delete-and-rederive correct for recursive Datalog views with stratified negation and aggregation, and how large is its overestimate of deletions against the deletions actually needed?
- databases
- logic
Oct 19, 2026
QUESTION-194: How far is a periodic greedy that switches a capped number of page fragments between caching and materializing, to keep the share of fresh fragments served above a threshold, from the best plan that meets the same threshold?
- databases
- operations-research
Oct 15, 2026
CLAIM-306: Under a deadline, search can establish presence by finding one item but absence only by exhausting the collection, so "If I can't find it, it isn't there" acts on an unfinished search as negation as failure acts on a finished one: a default stronger than either the closed-world assumption or negation as failure, safe only when the arrangement makes the full search finish within the deadline
Oct 15, 2026
CLAIM-311: A search cut off before an exhaustive pass can establish absence when the arrangement certifies that the unsearched remainder cannot hold the item: a sorted table answers non-membership in a logarithmic number of probes, and the Threshold Algorithm stops early with its answer proved, so absence needs a certificate about the remainder, not exhaustion; similarity search in high dimension is where no such certificate exists
Oct 15, 2026
CLAIM-312: "If I can't find it, it isn't there" asserts operational unavailability, that the item will not be put to use before the deadline, not absence: a search that fails by the deadline establishes unavailability outright, and licenses absence only with a certificate that the unsearched remainder cannot hold the item, from exhaustion, from an invariant of the arrangement, or from a closed-world default
Oct 15, 2026
CLAIM-313: A fixed number of bins realizes one partition only when each item is stored once: with copies, overlapping partitions coexist, as hashing-based similarity search stores each item in many partitions and pays for it in space, so sortings conflict as arrangements only under a one-copy constraint, which binds bricks but not index entries
Oct 15, 2026
CLAIM-314: Reusing a filed argument has a recognition cost that a fixed per-use price leaves out: certifying that stored answers cover a new question is NP-complete even for conjunctive queries, grows with the number and size of the stored definitions rather than being a constant per item, and is undefined for an item filed without a statement of what it answers, so each filing raises the cost of later reuse and per-item break-even decisions are not independent
Oct 15, 2026
LIT-1080: Selection of Views to Materialize in a Data Warehouse
- databases
- operations-research
Oct 15, 2026
LIT-1083: An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server
- databases
- operations-research
Oct 15, 2026
LIT-1084: Physical database design for relational databases
- databases
- operations-research
Oct 15, 2026
LIT-1085: Designing Access Methods: The RUM Conjecture
- databases
Oct 15, 2026
LIT-1086: The difficulty of optimum index selection
- databases
- mathematics
Oct 15, 2026
LIT-1089: The optimal selection of secondary indices is NP-complete
- databases
- mathematics
Oct 15, 2026
LIT-1090: Database Cracking
- databases
Oct 15, 2026
LIT-1091: Selection of views to materialize in a data warehouse
- databases
- operations-research
Oct 15, 2026
LIT-1092: Selection of Views to Materialize Under a Maintenance Cost Constraint
- databases
- operations-research
Oct 15, 2026
LIT-1093: Amortized efficiency of list update and paging rules
- databases
- mathematics
Oct 15, 2026
LIT-1094: Implementing data cubes efficiently
- databases
- operations-research
Oct 15, 2026
LIT-1095: An Online Approach to Physical Design Tuning
- databases
Oct 15, 2026
LIT-1096: Competitive snoopy caching
- databases
- mathematics
Oct 15, 2026
LIT-1097: Should Tables Be Sorted?
- databases
- mathematics
Oct 15, 2026
LIT-1099: When Is "Nearest Neighbor" Meaningful?
Oct 15, 2026
LIT-1100: Answering Queries Using Views
- databases
- logic
Oct 15, 2026
LIT-1101: Effective Page Refresh Policies for Web Crawlers
Oct 15, 2026
LIT-1102: Lower Bounds on Near Neighbor Search via Metric Expansion
- databases
- mathematics
Oct 15, 2026
LIT-1104: Why and Where: A Characterization of Data Provenance
- databases
- logic
Oct 15, 2026
LIT-1105: Balancing Performance and Data Freshness in Web Database Servers
- databases
- operations-research
Oct 15, 2026
LIT-1106: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality
Oct 15, 2026
LIT-1107: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces
- databases
- information-retrieval
Oct 15, 2026
LIT-1108: Combining Fuzzy Information from Multiple Systems
- databases
- information-retrieval
Oct 15, 2026
LIT-1109: Adaptive Precision Setting for Cached Approximate Values
- databases
- operations-research
Oct 15, 2026
LIT-1110: Provenance Semirings
Oct 15, 2026
LIT-1111: Optimal Implementation of Conjunctive Queries in Relational Data Bases
- databases
- logic
Oct 15, 2026
LIT-1112: Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
Oct 15, 2026
LIT-1113: Semantic Data Caching and Replacement
- databases
- information-retrieval
Oct 15, 2026
LIT-1114: Maintaining Views Incrementally
- databases
- logic
Oct 15, 2026
LIT-1115: Optimal Aggregation Algorithms for Middleware
- databases
- information-retrieval
Oct 15, 2026
LIT-1116: Answering Queries Using Views: A Survey
- databases
- logic
Oct 15, 2026
LIT-1117: Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data
- databases
- operations-research
Oct 15, 2026
LIT-1118: WebView Materialization
- databases
- operations-research
Oct 15, 2026
LIT-1119: Synchronizing a Database to Improve Freshness
Oct 15, 2026
LIT-1120: Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Oct 15, 2026
QUESTION-114: Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?
Oct 15, 2026
THEORY-332: For one index with no space limit, Bruno and Chaudhuri's online tuner, which builds the index once the savings it would have given have risen by its build cost above their last low and drops it once they have fallen by the build cost below their last high, is not three-competitive: when every statement's saving or loss is at most a fraction f of the build cost, a repeated workload makes it cost nearly 3 + 2f times the offline optimum, and one statement whose saving exceeds the build cost makes the ratio unbounded; no upper bound is shown
- databases
- operations-research
Oct 15, 2026
THEORY-333: Database cracking, which partitions a copy of a column in place as a side effect of each range query, measured in memory on 10^7 integers under uniformly random ranges, costs about 40% more than a scan on the first query and far less than sorting, gets cheaper per query with use, and stays cumulatively cheaper than sort-then-search until about 10^5 queries; that only the queried ranges get organized is not tested
- databases
Oct 15, 2026
THEORY-338: For a list searched from the front, where reaching the i-th item costs i, moving each found item to the front costs at most twice what any rule costs on the same sequence, including rules that know the future (four times counting its own moves), a fixed order by access frequency is within no constant factor, and paying to rearrange ahead of need never helps; for paging, no online rule beats the offline optimum by less than n/(n − n_MIN + 1), and LRU meets that bound
- databases
- mathematics
Oct 15, 2026
THEORY-340: For answering membership in a static set of n keys with the fewest worst-case cell reads, sorted order with binary search is optimal only when the key universe exceeds a Ramsey-number threshold and table cells may hold nothing but stored keys or pointer symbols; it is beaten for small universes, and by two probes once one cell may hold an encoded value
- databases
- mathematics
Oct 15, 2026
THEORY-341: Inferring not-P from failure to prove P is a deduction only under two separate conditions: Clark shows that when every branch of the search for a proof of P ends in failure, not-P is a theorem of the completed database, and a search that does not finish licenses nothing; Reiter's closed-world assumption, adding the negation of every ground atom the database does not entail, keeps a consistent Horn database consistent and can make a disjunctive one inconsistent
- logic
- databases
Oct 15, 2026
THEORY-344: An access method's read, update and memory overheads, each a ratio to the base data alone with a floor of 1.0, are conjectured to trade so that bounding any two forces a lower bound on the third; the conjecture is unproved, its formal wording says no more than the floor already does, and the paper's extreme designs show conflicts between pairs, read against memory and update against read, not a symmetric three-way trade
- databases
Oct 15, 2026
THEORY-345: Choosing indexes for a known mix of queries and updates, to minimize query cost plus a per-index upkeep, is NP-hard as the number of attributes and query types grows, and the tools built for it choose one stored order and a set of secondary indexes per table by searching configurations costed with the query optimizer's own estimates, optimal at best relative to those estimates, with no proved guarantee for their heuristics and no term for the one-time cost of building
- databases
- operations-research
Oct 15, 2026
THEORY-348: When staying in one state costs a fixed amount per request and leaving it costs a fixed one-time price, switching once the extra cost paid for staying equals that price is within 2 of the offline optimum on every request sequence, and no deterministic online rule does better; with a third option the best guaranteed ratio rises to 3
- databases
- mathematics
Oct 15, 2026
THEORY-350: Under a budget on maintenance time, a stored view's upkeep depends on which other views are stored, so upkeep is not additive and adding a view can lower it, and greedily adding the single view of best saving per unit of upkeep can be arbitrarily bad; on OR view graphs a greedy over inverted tree sets gets 1 − 1/e of the saving of an optimum given as much upkeep, using up to twice the budget, if no tree-piece of the optimum alone exceeds the budget
- databases
- operations-research
Oct 15, 2026
THEORY-356: When stored views are never updated, greedily storing the view of largest marginal saving in query cost gets at least 1 − 1/e of the optimal saving on a data-cube lattice or any OR or AND view graph, against the optimum for the same number of views or for the space the greedy ends up using, which may exceed the budget by one view
- databases
- operations-research
Oct 15, 2026
THEORY-361: When every object but one has full grade in exactly one of two attribute-sorted lists and the one has full grade in both, finding it under min takes at least about half the objects' worth of accesses for any algorithm that only reads the lists from the top and looks up objects already seen, and, with the tied objects in random order, about as many in expectation even for algorithms that may look up any object; a query on one attribute alone costs k accesses whatever the number of objects
- databases
- information-retrieval
Oct 15, 2026
THEORY-362: For nonrecursive Datalog or SQL views with safe stratified negation and stratified aggregation, under set or duplicate semantics, storing with each derived tuple only the number of its derivations suffices to maintain the view under insertions and deletions of base tuples: signed counts propagated through delta rules stratum by stratum give each tuple's change as its new count minus its old, a tuple leaves when its count reaches zero, and a MIN or MAX group whose extreme is deleted is recomputed from the stored lower stratum
- databases
- logic
Oct 15, 2026
THEORY-363: For finding the top k objects under a monotone combining function from m lists each sorted by one attribute, with sorted and random accesses the only costs, the threshold algorithm is correct and on every database costs at most a constant times what any correct algorithm that makes no wild guesses costs; the constant is m + m(m−1)c_R/c_S, no deterministic algorithm does better when the function is strict, and once wild guesses are allowed no algorithm has such a guarantee on databases with ties
- databases
- information-retrieval
Oct 15, 2026
THEORY-364: When each cached value is an interval its source guarantees to contain the current value, and a query must return an answer interval no wider than R whatever the true values, choosing the cheapest set of exact reads for a SUM is a 0/1 knapsack problem, NP-complete in general and solved by taking the narrowest intervals first when read costs are equal, and for a COUNT with a selection predicate the cheapest choice is the ⌈|T?| − R⌉ cheapest undecided tuples
- databases
- operations-research
Oct 15, 2026
THEORY-365: In one study of a stack of proximity graphs on nested random subsets of the data, each element's top layer drawn geometrically, greedy search on uniform random data in 8 dimensions needed a number of distance computations that grew no worse than logarithmically with the number of items and stayed below a single-layer navigable graph's at every size tested, and in 4 dimensions the beam width needed for a fixed recall saturated; the logarithmic bound is derived only for exact Delaunay graphs of bounded degree, which the index does not build, and on 200 million SIFT vectors the measured growth departs from it
Oct 15, 2026
THEORY-367: For SPJU relational queries, which Buneman, Khanna and Tan's tree model encodes, the minimal witnesses of an output tuple, the inclusion-minimal sets of source facts from which the query still derives it, are the minimal sets matched by single derivations and so are the same for every equivalent query, while where-provenance, the source location a value was copied from, can differ between equivalent queries
- databases
- logic
Oct 15, 2026
THEORY-368: On two-dimensional point sets constructed for the purpose, the authors' code for fast-preprocessing DiskANN, HNSW and NSG, at parameters from the original papers, in most cases found none or few of a query's five nearest neighbours until the search queue held about 10% of the points, for n from 10⁵ to 2·10⁶, and at that queue length ten graph indexes averaged recall@5 between 0.0 and 0.42; this is shown by experiment on one query per instance, and no theorem bounds these algorithms
- databases
- information-retrieval
Oct 15, 2026
THEORY-369: Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance and a fixed number of points, an optimal nearest-neighbour search over any index that partitions points into blocks or convex clusters of at least two points must read a fraction of blocks that grows toward all of them as dimension rises; with a five-fold sequential advantage for scanning, estimates put the crossover at about 15–26 dimensions for rectangular and spherical bounding regions, and two tree indexes measured on 50,000 points lost to a scan beyond about 10
Oct 15, 2026
THEORY-371: For conjunctive queries without equality or comparisons, two queries are equivalent exactly when homomorphisms run both ways between the queries read as small databases, every such query has a minimal equivalent query unique up to isomorphism obtained by deleting atoms, and evaluating one against a database is NP-complete when the query is part of the input
Oct 15, 2026
THEORY-372: For c-approximate near-neighbour search over n points in Euclidean space, space n^{1+ρu+o(1)} and query time n^{ρq+o(1)} are achievable on any data set whenever c²√ρq + (c²−1)√ρu ≥ √(2c²−1) (c√ρq + (c−1)√ρu ≥ √(2c−1) in Hamming space), and no list-of-points structure, the model of known data-independent hashing, does better on random instances; without that model the curve is matched only at query time n^{o(1)} by one or two cell probes
Oct 15, 2026
THEORY-373: For positive relational algebra on relations whose tuples are annotated from a commutative semiring, every query's annotated answer equals its answer over provenance polynomials N[X] in the input tuple ids, evaluated at the input annotations, so set, bag, c-table and event-table semantics all factor through the polynomials; revaluing inputs can remove output tuples but never add them, and nothing is shown for negation, difference or aggregation
Oct 15, 2026
THEORY-374: Given views with conjunctive definitions, deciding that they answer a conjunctive query exactly is NP-complete in the size of the query and definitions, while a maximally-contained rewriting can be built in time polynomial in that size without saying whether it is exact; and finding all certain answers from the stored contents is polynomial in their size under the open-world assumption when the views are conjunctive and the query conjunctive or datalog, but co-NP-hard in that size under the closed-world assumption even for conjunctive views and queries
- databases
- logic
Oct 15, 2026
THEORY-375: In one simulator evicting whole query-shaped cache regions, no replacement value function was best on every workload: a value based on distance from the current query beat LRU where queries clustered around a hot region or wandered with loops, while MRU was best on regular cyclic paths, by up to 2.3 times over the distance value and 9.6 times over LRU; none of the functions weighs what a region would cost to fetch again, and nothing is proved
- databases
- operations-research
Oct 15, 2026
THEORY-376: In a simulated single-client, read-only database answering selection queries on one relation, describing cached data by the predicates of past queries let each query be answered partly from cache, with only the remainder Q ∧ ¬V sent to the server; this matched page caching on a clustered index, beat it on an unclustered one, and, on an unindexed attribute with a disk cache, answered over 60% of 1% queries without contacting the server; the cost of computing probe and remainder queries was not charged
- databases
- information-retrieval
Oct 15, 2026
THEORY-377: In Olston, Loo and Widom's simulations, a rule that multiplies a cached interval's width by 1 + α on a pushed refresh with probability min{ρ, 1}, and divides it by 1 + α on a query's exact fetch with probability min{1/ρ, 1}, settled within 1% of the best fixed width on one random walk and within 5% over eight walk settings; on a 50-host network-traffic trace, restricted to exact copies, it almost matched a tuned adaptive cache-or-not rule, and with a 50-value cache, where queries tolerated imprecision, it cost less; that it converges to the best width is argued, not proved
- databases
- operations-research
Oct 15, 2026
THEORY-378: When items change as independent Poisson processes with known rates and a fixed total refresh rate is shared among them, refreshing every item equally keeps the copy at least as fresh and at most as old, averaged over time, as refreshing in proportion to change rate, for any spread of rates; the freshness-optimal share rises and then falls with change rate and gives nothing to items that change too fast for the budget
Oct 15, 2026
THEORY-379: Fagin's Algorithm finds the top k of N objects held in m attribute-sorted lists under any monotone combining function, and when the lists' orderings are independent with at least m − 1 of them uniformly random it does so with O(N^((m−1)/m) k^(1/m)) sorted and random accesses with arbitrarily high probability; with dependent orderings the bound can fail
- databases
- information-retrieval
Oct 15, 2026
THEORY-380: For datalog over a finite input instance annotated from a commutative ω-continuous semiring, with an answer's tag defined as the sum over its derivation trees of the product of its leaves' tags, the tags are the least fixed point of a finite polynomial system and factor through formal power series N∞⟦X⟧ in the input tuple ids; an answer tuple's series has an infinite coefficient exactly when one of its derivation trees contains a tuple lying on a cycle of unit rules
Oct 15, 2026
THEORY-381: In the cell-probe model, a near-neighbour structure on n random points that answers in t probes with m cells of w bits must satisfy m^t·w/n ≥ the robust expansion of the metric's neighbourhood graph at measure 1/m^t (and (mwt/n)^t ≥ its vertex expansion if deterministic), so in expanding spaces such as the hypercube fast queries need space polynomially larger than the data; the bounds are average case, approximate, and fall off exponentially in t
- databases
- mathematics
Oct 15, 2026
THEORY-382: When a web server keeps each page fragment either cached and invalidated by updates or stored and refreshed after them, materializing trades staleness for response time, and in one synthetic simulation with fixed costs a periodic greedy that moves a capped number of fragments between the two, to keep the share of fresh fragments served above a set threshold, tracked that threshold by the authors' reading of its curves, answered faster than caching alone and recovered from overload by materializing everything; no bound on its distance from the best plan is shown
- databases
- operations-research
Oct 15, 2026
THEORY-383: On one Apache and Informix server answering cheap indexed selections over 1000 pages, a page whose query result was stored in the DBMS and refreshed on every update answered more slowly than one recomputed on each request at five or more updates per second, which the authors explain by reading the stored result costing about as much as recomputing it and its refresh loading the same DBMS, while a finished page stored at the web server and rewritten on every update answered 10 to 230 times faster than either
- databases
- operations-research
Oct 15, 2026
THEORY-384: A nearest-neighbour graph built by pruning each point's links against all other points with a factor α > 1, so that from every point some link is α times closer to any other point, lets greedy search from any start reach a ((α+1)/(α−1) + ε)-approximate nearest neighbour in O(log_α(∆/((α−1)ε))) steps of cost O((4α)^d log ∆), for doubling dimension d and aspect ratio ∆; the ratio is tight and the dependence on ∆ cannot be replaced by one on n, and the build takes O(n³) time done naively
- databases
- information-retrieval
Oct 15, 2026
THEORY-385: In HNSW over 10-dimensional data in 100 isolated clusters, linking each new item to its nearest neighbours leaves part of the bottom layer unreachable from the entry point and caps recall well short of 1 however wide the query search, while linking a candidate only when it is nearer the new item than to any neighbour already kept keeps that layer connected and reaches recall near 1 with about half the links; on uniform data at 10 and 64 dimensions the two rules differ little; shown in Malkov and Yashunin's own tests on 10 million points and in an independent re-run on 30,000, which found the nearest-neighbour rule capped at a recall@10 of 0.72 to 0.83 against 0.999, at matched build cost too
Oct 15, 2026
THEORY-386: When a cached interval of width W is kept valid by its source, which pushes a refresh at cost C_vr whenever the value leaves it, and queries fetch the exact value at cost C_qr whenever it is too wide, and the chances of the two per step go as 1/W² and as W, the expected refresh cost is least at W* = (ρK₁/K₂)^(1/3) with ρ = 2C_vr/C_qr, where ρ times the chance of a pushed refresh equals the chance of a fetch
- databases
- operations-research
Oct 15, 2026
THEORY-387: For positive recursive Datalog views under set semantics, deleting every derived tuple that has any derivation through a deleted base fact, then restoring each deleted tuple that still has a derivation from what remains, then adding what insertions derive, leaves exactly the tuples derivable from the new base (E − Δ⁻) ∪ Δ⁺, with no derivation counts stored; the extension to stratified negation and aggregation is asserted, not shown, and the size of the overestimate is not measured
- databases
- logic
Oct 15, 2026
THEORY-388: Locality-sensitive hashing answers approximate near-neighbour queries over n points with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, where ρ = ln(1/p1)/ln(1/p2) is set by how much more often near pairs collide than far ones and is at most 1/(1+ε) for approximation 1+ε in Hamming space, with constant success probability per query; the paper gives upper bounds only and proves no limit on what organizing can buy
Oct 15, 2026
THEORY-389: For conjunctive queries and views without comparison predicates, a stored view can be used in an equivalent rewriting of a query exactly when the view's body maps homomorphically into the query's, a minimal rewriting needs no more literals than the query, and deciding whether a rewriting shorter than the query or one using only the views exists is NP-complete in the size of the query and view definitions; with comparisons in both, deciding whether any rewriting uses the views is Π2p-complete
- databases
- logic
Oct 14, 2026
LIT-1158: A neural algorithm for a fundamental computing problem

Created with Quartz v5.0.0 © 2026

Repository
Quartz