databases.
32 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-888 | Athanassoulis et al. — Designing access methods: the RUM conjecture | The paper names three per-operation overheads of an access method, each a ratio to the base data alone (read, update and space amplification, each minimum 1.0), and conjectures that bounding any two forces a lower bound on the third. Its evidence is three one-line propositions about extreme designs over an integer array (a direct-address array, an append-only log, an unindexed dense array), a placement of known structures on a triangle, and a table of asymptotic I/O costs; nothing is proved, and the formal statement does not say how large the forced bound is, so as worded it is close to empty. The extremes themselves show the overheads are not symmetric: the space-minimal design is also update-minimal, and the read-minimal design keeps updates at 2.0, so the clean conflicts are read against space and update against both. Build cost appears in the table but is outside the triangle, there is no workload weighting, no time or deadline, and no cost of examining an item other than reading it. | Read |
| NOTE-889 | Gupta — Selection of views to materialize in a data warehouse | Gupta states view selection on general AND-OR view graphs as minimizing frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget. He proves greedy guarantees of 1 − 1/e (about 63%) of the optimal benefit, with the budget overrun by one view or up to double, but almost all of them assume no updates. Maintenance cost enters exactly one theorem: AND view graphs (each view has one way of being computed) in which every view is queried more often than it is updated. For OR view graphs, which include Harinarayan, Rajaraman and Ullman’s data cube, the paper sets update costs aside outright, so it does not add upkeep to that problem. Maintenance is an abstract per-update charge for keeping a view consistent. Nothing prices building a view, tolerated staleness or deferred refresh, and there are no experiments. | Read |
| NOTE-890 | Gupta & Mumick — Selection of views to materialize under a maintenance cost constraint | Gupta and Mumick choose views to materialize so as to minimize frequency-weighted query cost subject to a cap S on total maintenance time, the sum over chosen views of update frequency times a per-update maintenance cost that depends on which other views are stored. Because storing one view can make another cheaper to maintain, benefit per unit of maintenance is not monotone and the single-view greedy of earlier work can be arbitrarily bad. For OR view graphs (each view computed from one other, as in data cubes) a greedy that adds whole “inverted tree sets” gets at least 1 − 1/e (63%) of the benefit of an optimal solution that may use as much maintenance as the greedy did, the greedy using up to 2S, assuming no inverted-tree piece of the optimum alone exceeds S (Theorem 1, unproved here); without that assumption it gets half the optimum’s benefit per unit of maintenance (Theorem 2). Each greedy stage enumerates exponentially many sets in general; for general AND-OR graphs there is only an exact A* search with exponential worst case. Upkeep is a budget, not a term traded against query savings; build cost, storage and staleness are not modelled, and the experiments are on random graphs of 10 to 25 nodes. | Read |
| NOTE-891 | Yao — Should tables be sorted? | For storing a set of n keys from a universe {1,…,m} in a table so that the membership query (is x in S?) is answered with the fewest worst-case adaptive probes, Yao proves that when the table cells may hold only keys of S or a bounded number of pointer symbols, sorted order with binary search (⌈lg(n+1)⌉ probes) is optimal once m exceeds a Ramsey-number threshold N(n, p, q), whatever the arrangement rule, table size or hashing scheme. The threshold is astronomically large, and for small universes sorted order is beaten (one probe suffices for m = 3 with n = 2, and for m ≤ 2n − 2 with n > 2). The optimality also fails as soon as one cell may hold an arbitrary value from the universe: with a single extra “directory” cell, two probes suffice for m ≥ 2^{16n²}. Only query cost is counted; building the table is free and unconstrained, so the paper says nothing about the cost of arranging or about trading arrangement cost against lookups. | Read |
| NOTE-892 | Idreos, Kersten & Manegold — Database cracking | Database cracking builds an index as a by-product of answering range queries. Each select partitions, in place, the part of a copy of the column that the query had to touch, so that the qualifying values lie contiguously, and records the new boundaries in a small tree; later queries touch only the pieces at the edges of their range, so per-query cost falls as the column is split into more pieces. On a 10^7-value column under uniformly random range queries, the first cracking select costs 0.38 s against 0.27 s for a scan and about 3.3 s for sort-then-search, and cumulative cost stays below sorting’s until about 10^5 queries, after which upfront sorting wins. The authors claim that only ranges of past interest get organized, but every experiment uses uniformly random ranges, so that claim is not measured; there is no cost model, no rule for when a reorganization is worth making, and updates, concurrency and out-of-memory data are left as open problems. | Read |
| NOTE-893 | Karlin, Manasse, Rudolph & Sleator — Competitive snoopy caching | For a shared-bus multiprocessor whose caches can either keep a replicated block (and pay one bus cycle for every write to it) or drop it (and pay p to fetch it again if it is read), the paper gives counter-based on-line algorithms whose total bus cost on every request sequence is at most twice that of the best off-line algorithm, and proves that no deterministic on-line algorithm can guarantee better than 2. The rule is: drop a copy once the writes it has caused since it was last read have cost as much as refetching it. With a third option (reading or writing through without fetching) the lower bound rises to 3, and the algorithm given is 3-competitive ignoring writebacks, 4 counting them; with associative caches the bound becomes the paging ratio. The paper never names rent-or-buy or ski rental; its rent is upkeep paid on an idle copy, and its purchase is the refetch after dropping, the reverse orientation of building a bin. Costs are fixed constants, the guarantees are worst case only, and the authors call the practical significance “unclear”. | Read |
| NOTE-895 | Harinarayan, Rajaraman & Ullman — Implementing data cubes efficiently | Treats a data cube’s group-by queries as a lattice in which a query can be answered from any stored ancestor, prices a query at the number of rows of the smallest materialized ancestor, and chooses which views to precompute. Choosing k views to maximize the total reduction in query cost (the “benefit”) is NP-complete; a greedy rule that adds the view of largest marginal benefit gets at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimal benefit, a bound that is tight, holds unchanged with query-frequency weights, and weakens to 0.63 − f under a space budget when no view takes more than a fraction f of it. The cost of building views is represented only by their size, maintenance and updates are not modelled, the data are static, and the bound is on benefit, not on query cost. On TPC-D data the greedy order reaches nearly the minimum total query time with five views and barely more space than the base view. | Read |
| NOTE-896 | Bruno & Chaudhuri — An online approach to physical design tuning | An always-on index tuner for SQL Server. It keeps, for each candidate or existing index, the running sum of what each query would have saved with it (what-if optimizer estimates, with update costs counted as losses). It creates an index once that sum has risen by the index’s build cost above its lowest point, and drops it once the sum has fallen by the build cost from its highest point. For one index with no space limit, the authors call this 3-competitive against the optimal schedule that knows the workload in advance. The proof only gives a workload on which the ratio approaches 3, and the paper cites no competitive-analysis work, ski rental included. The general case (many interacting indexes and a storage limit) uses heuristics with no guarantee. All costs in the experiments are optimizer estimates, on synthetic and TPC-H workloads. | Read |
| NOTE-898 | Finkelstein, Schkolnick & Tiberio — Physical database design for relational databases | DBDSGN chooses, for each table, one clustered (ordering) index and a set of nonclustered indices to minimise a frequency-weighted sum of per-statement costs (access, tuple update, index maintenance) plus a weighted storage term, under an optional page limit, taking every cost from the System R optimizer’s own estimates rather than an external model. Statement costs for any configuration are computed exactly from “atomic” configurations with at most one index per table (Propositions 1 and 2), so the optimizer is consulted a linear rather than exponential number of times per table; with no elimination heuristics and a full search the tool finds the optimum, but only with respect to the optimizer’s estimates. The paper gives one worked example and no measurement of actual execution, and its claims that the heuristics usually find the best solutions are not backed by reported data. The model is steady-state over a period: it has no term for the one-time cost of building an index or sorting a table, so it prices upkeep against retrieval, not a one-off sort against later retrievals. | Read |
| NOTE-900 | Chaudhuri & Narasayya — An efficient, cost-driven index selection tool for Microsoft SQL Server | The AutoAdmin tool picks at most k indexes (single- or two-column, clustered or not) for a given workload of SQL statements, minimising the unweighted sum of the optimizer’s estimated costs of those statements, with hypothetical (“what-if”) indexes made visible to the optimizer by loading their statistics into the catalog. Its contribution is search efficiency: candidates are restricted to indexes in some single query’s best configuration, enumeration is Greedy(m, k) (an exhaustive seed of m indexes, then greedy additions), costs of most configurations are derived from a few “atomic” ones, and two-column indexes are generated only from winning single columns. On five TPC-D workloads this cut running time to 10–24% of a baseline, with estimated-cost quality 0–7% worse, and Greedy(2, 4) matched the exhaustive optimum on four of five workloads and was within 1% on the fifth. The cost model has no build cost, no storage term and no frequency weights, the budget is a count of indexes, the workload is fixed, there is no guarantee for the greedy step, and quality is never measured by executing anything. | Read |
| NOTE-901 | Gupta & Mumick — Selection of views to materialize in a data warehouse (TKDE 2005) | The journal paper merges Gupta’s 1997 space-budget results and the 1999 maintenance-budget results into one article; it adds proofs, not new problems or new guarantees. Theorem 8 (the conference Theorem 1: inverted-tree greedy on OR view graphs, at most 2S of maintenance, at least 1 − 1/e of an optimum with the same maintenance, assuming no inverted-tree piece of the optimum exceeds S) and Theorem 10 (A* is exact on AND-OR graphs) are now proved, while Theorem 9 (the assumption-free half-density bound) is referred to Gupta’s thesis. The maintenance-budget guarantee stays confined to OR view graphs, the greedy stays exponential in the worst case, and the two constraints are never combined. The only place upkeep is traded against query cost is the 1997 formulation carried over, query cost plus maintenance cost minimized under a space budget, with a guarantee only for AND view graphs in which every view is queried more often than it is updated; build cost and staleness are not modelled anywhere. | Read |
| NOTE-902 | Piatetsky-Shapiro — The optimal selection of secondary indices is NP-complete | For one relation, a known mix of equality queries and updates, single-attribute secondary indexes, and a fixed upkeep charge per index on each update, choosing the index set that minimizes average transaction cost is NP-hard: minimum set cover reduces to it, each subset becoming an attribute and each element a query that any one of its attributes’ indexes can answer. The paper calls the problem NP-complete but states only the optimization version, and the proof is a sketch of about half a page. Storage is not in the model; the only price of an index is upkeep on updates. A variant with off-line updates under an update-cost budget is asserted NP-complete without proof. The paper does not cite or discuss Comer 1978. | Read |
| NOTE-903 | Sleator & Tarjan — Amortized efficiency of list update and paging rules | For a list searched sequentially from the front, where reaching the i-th item costs i, moving each accessed item to the front costs at most twice what any other rule costs on the same sequence, including rules that know the whole sequence in advance (four times, counting move-to-front’s own moves), with no probabilistic assumption. A fixed list sorted by access frequency, and the transpose and frequency-count rules, are not within any constant factor of that. Rearranging ahead of need never pays in this model (Theorem 3). For paging, where only a small fast memory is cheap, no rule that cannot see the future can do better in the worst case than n/(n − n_MIN + 1) times the offline optimum MIN, and LRU and FIFO attain that bound up to an additive n_MIN; with equal memories the ratio is the memory size. The model is a single linear list (or a two-level memory) with uniform items and access cost depending only on position; it says nothing about partitions, bins or search that is not a scan. | Read |
| NOTE-904 | Dar, Franklin, Jónsson, Srivastava & Tan — Semantic data caching and replacement | A client cache described by the selection predicates of past queries can answer a new selection query partly from cache (the probe query, Q ∧ V) and fetch only the rest from the server (the remainder query, Q ∧ ¬V), and can evict by semantic region rather than by page or tuple. In one simulator, one client and one server, read-only selection queries on a single 10,000-tuple relation, this matched page caching on a clustered index, beat it heavily when clustering was bad, answered over 60% of small queries on an unindexed attribute with no server contact, and let a value function based on semantic distance beat LRU on a skewed workload. No replacement rule won everywhere: on regular cyclic paths MRU was best. Everything is measured, nothing is proved; updates, joins, and the CPU cost of reasoning about cache contents were not modelled. | Read |
| NOTE-905 | Indyk & Motwani — Approximate nearest neighbors: towards removing the curse of dimensionality | Approximate nearest-neighbour search in d dimensions reduces, with small overhead, to a decision problem (is there a point within r, or none within (1+ε)r), and that decision problem is solved by locality-sensitive hashing: if hash functions make near pairs collide with probability at least p1 and far pairs with at most p2, then n^ρ random hash tables with ρ = ln(1/p1)/ln(1/p2) answer queries with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, with constant success probability. For Hamming space by bit sampling, and for ℓ_p with p in [1, 2] by embedding, ρ ≤ 1/(1+ε) in the 1999 text (1/ε, for ε > 1, in STOC). The paper also gives the other end of the trade: Õ(d) query time for n·O(1/ε)^d or (nd)^{O(1)} preprocessing. It is an upper bound only: it proves no lower bound, does not claim its exponents are best, solves only the approximate problem with constant probability, and counts preprocessing as space. | Read |
| NOTE-906 | Cho & Garcia-Molina — Synchronizing a database to improve freshness (SIGMOD 2000) | For a local copy of N items, each changing as an independent Poisson process with a known rate and refreshed at fixed intervals under a fixed total refresh rate, refreshing every item equally keeps the copy fresher and younger on average than refreshing in proportion to change rate, under any distribution of rates (proved in the technical report by convexity). The freshness-optimal allocation is neither: it rises and then falls with change rate, and gives no refresh at all to items that change too fast for the budget, while the age-optimal allocation rises slowly with change rate. On estimates from 270 web sites, proportional, uniform and optimal refresh give freshness 0.12, 0.57 and 0.62. Every item matters equally, staleness is a time average with no access or query model, the refresh budget is fixed rather than priced, and refresh, change and its detection are free of any other cost. | Read |
| NOTE-907 | Chandra & Merlin — Optimal implementation of conjunctive queries in relational data bases | Defines conjunctive queries (existentially quantified conjunctions of atoms, no equality, constants naming distinct elements) and proves that two are equivalent exactly when there are homomorphisms each way between their natural models (Lemma 13). Every conjunctive query has a minimal equivalent query, unique up to isomorphism, reached by folding (Theorem 12), and that minimal query yields an evaluation program within a constant factor of optimal in the paper’s cost model (Theorem 16). The hardness results are that evaluating a boolean conjunctive query on a database is NP-complete when the query is part of the input (Theorem 7), and that deciding whether one query is a folding of another is NP-complete (Theorem 11). The paper does not state a containment theorem or the NP-completeness of containment or equivalence as such; both are standard corollaries of Lemma 13’s proof and Theorem 11’s construction, and later papers cite them to it. | Read |
| NOTE-908 | Labrinidis & Roussopoulos — WebView materialization | For a page built from database queries, the paper compares three ways to serve it on a server with online updates: compute it on each request (virt), store the query result in the DBMS and refresh it on every update (matdb), or store the finished page as a file at the web server and rewrite it on every update (matweb). It gives a cost model summing access and update costs by their frequencies and states the selection problem (choose a policy per page to minimize mean response time, no space limit, no staleness allowed), but gives no algorithm for it. On one Apache/Informix testbed with cheap indexed queries, matweb answered 10 to 230 times faster than the other two at all loads tried, and matdb was slower than virt whenever there were updates, because reading the stored result cost about as much as recomputing it. Staleness is defined as the delay from update to reply, sketched, and never measured; build cost and storage are outside the model. | Read |
| NOTE-909 | Levy, Mendelzon, Sagiv & Srivastava — Answering queries using views | For conjunctive queries and views, a view can be used in an equivalent rewriting of a query exactly when there is a containment mapping (a homomorphism of bodies) from the view into the query, so every possible use of a stored view is found among those mappings. Without comparison predicates, a minimal rewriting needs no more literals than the query and no new variables, which puts the search in NP; deciding whether some rewriting uses a given set of views (with comparisons only in the query), whether a rewriting with fewer than k literals exists, and whether a rewriting using only the views exists are each NP-complete, and with comparisons in both query and views existence is Π2p-complete. The hardness has two independent sources, the number of mappings and the choice of which query literals to drop, and a polynomial algorithm removes the redundant literals for a given mapping, exactly under stated conditions. Only equivalent rewritings are studied; contained rewritings, the cost of the resulting plan and the size of view collections are outside it. | Read |
| NOTE-910 | Indyk & Xu — Worst-case performance of popular approximate nearest neighbor search implementations | For DiskANN’s “slow preprocessing” graph (each point linked to the points that survive α-pruning of all other points, naively O(n³) time), greedy search from any start with no backtracking reaches a ((α+1)/(α−1) + ε)-approximate nearest neighbour in O(log_α(∆/((α−1)ε))) steps, each costing O((4α)^d log ∆) for doubling dimension d and aspect ratio ∆; the ratio is tight and the dependence on ∆ cannot be replaced by log n. For DiskANN with its practical “fast preprocessing”, HNSW, NSG and seven other graph indexes, the paper constructs two-dimensional point sets (constant doubling dimension) on which, in experiments with the authors’ code at the authors’ recommended parameters, the search queue must hold about 10% of the points before recall@5 becomes non-zero or the approximation ratio becomes reasonable. The linear lower bounds are empirical, for one query per constructed instance, with an informal Ω(n/R) argument for fast-preprocessing DiskANN; no theorem bounds HNSW or NSG. | Read |
| NOTE-911 | Labrinidis & Roussopoulos — Balancing performance and data freshness in web database servers | The paper poses Online View Selection for a web server whose database takes updates while serving requests: choose, as the workload runs, which page fragments (WebViews) to keep stored and refreshed on every update and which to cache and invalidate, so as to minimize mean response time while the fraction of fresh fragments served (QoD) stays above a threshold θ. Its algorithm, OVIS(θ), estimates per fragment the response-time and QoD change of switching, and periodically switches up to MAX_CHANGE fragments greedily, spending a QoD surplus on speed or buying back a deficit; it materializes everything when it detects backlog. Nothing is proved: optimality of the greedy step is asserted, and the evidence is one synthetic simulation with fixed costs, in which OVIS kept QoD near θ, answered faster than caching alone, and recovered from overload. Upkeep and query savings share one cost, but staleness is a constraint set by the user, not a priced term, and build cost, switching cost and storage are absent. | Read |
| NOTE-912 | Olston, Loo & Widom — Adaptive precision setting for cached approximate values | Olston, Loo and Widom set the width of each cached interval adaptively to minimize total refresh traffic. A narrow interval is escaped often (value-initiated refreshes, cost C_vr); a wide one is too imprecise for queries more often (query-initiated refreshes, cost C_qr). Under a model in which these probabilities go as 1/W² and W, the expected cost rate is least where ρ·P_vr = P_qr, ρ = 2C_vr/C_qr, and a rule that widens on value-initiated and narrows on query-initiated refreshes, with probabilities set by ρ, reached within 1% to 5% of the best fixed width in simulation. That the rule converges is argued, not proved. With exact copies required it matched an adaptive exact-caching algorithm, and where imprecision was allowed it beat it. Staleness is priced as refresh traffic only: there is no build cost, no cost of a wrong answer, and the interval is never wrong. | Read |
| NOTE-913 | Green, Karvounarakis & Tannen — Provenance semirings | Annotating each input tuple with an element of a commutative semiring, and computing union and projection with + and join with ·, gives one positive relational algebra (RA+) that is set semantics over the Booleans, bag semantics over the naturals, c-tables over positive Boolean expressions, event tables over sets of outcomes, and lineage over sets of tuple ids. The polynomials N[X] in the tuple ids are the most general such annotation: for any RA+ query and any commutative semiring K, the K-annotated answer is the provenance polynomial evaluated at the input’s K-annotations (Theorem 4.3). For datalog the paper needs ω-continuous semirings and formal power series N∞⟦X⟧, with the analogous factorization (Theorem 6.4) and a criterion for infinite coefficients (Theorem 6.5). Everything is positive: no negation, difference or aggregation, and revaluing inputs can only remove output tuples, never add them; trust and deletion propagation are not treated. | Read |
| NOTE-914 | Panigrahy, Talwar & Wieder — Lower bounds on near neighbor search via metric expansion | Cell-probe lower bounds for near-neighbour search follow from the expansion of the graph joining points within distance r: a deterministic t-probe structure with m cells of w bits must have (mwt/n)^t at least the vertex expansion, and a randomized one must have m^t w/n at least the robust expansion at measure 1/m^t, on random data sets with weakly overlapping neighbourhoods. For the hypercube this recovers known bounds and gives, for example, space n^{1+Ω(1/(ct))} for approximation c and n^{Ω(1/(tε²))} for 1 + ε; for symmetric (Cayley) graphs a one-probe structure matches the bound, and for dynamic low-contention structures the update time must be at least the robust expansion over poly(t). The bounds are average case, for approximate decision search, and weak in t: they fall off exponentially in the number of probes, so they are tight only for a constant number of probes and say little about structures that probe n^ρ cells. | Read |
| NOTE-915 | Gupta, Mumick & Subrahmanian — Maintaining views incrementally | Two algorithms compute the changes to a stored derived relation (a view) from changes to the base relations, without recomputing it. Counting stores, for each derived tuple, the number of its derivations and propagates signed counts through delta rules stratum by stratum; it is stated correct for nonrecursive Datalog or SQL views with stratified negation and aggregation, under set or duplicate semantics, and is argued to cost little beyond evaluating the view. DRed (delete and rederive), for recursive views under set semantics only, deletes an overestimate of what a deletion invalidates, puts back those tuples that still have a derivation from what remains, then adds what insertions derive; it is stated to yield exactly the tuples derivable from the new base. The paper is an extended abstract: the theorems are stated without proof (proofs are referred to a 1992 AT&T report), cost claims are argued, not measured, and there are no experiments. | Read |
| NOTE-917 | Beyer, Goldstein, Ramakrishnan & Shaft — When is “nearest neighbor” meaningful? | For a fixed number n of data points and a query drawn independently of them, if the variance of the p-th power of the query-to-point distance, divided by its mean, goes to zero as dimension m grows, then the farthest point is, with probability tending to one, within any factor 1 + ε of the nearest (Theorem 1). The condition holds for IID dimensions and for several correlated or non-identical workloads, and fails when data and queries lie on a low-dimensional subspace or when queries fall inside well-separated clusters. Simulations put the collapse of contrast within 10 to 20 dimensions for IID data, and two real image-feature sets showed weak contrast. The condition is sufficient, not shown necessary; the theorem is about the ratio of distances with n held fixed, and says nothing about real data of low intrinsic dimension except that such data can escape it. | Read |
| NOTE-918 | Andoni, Laarhoven, Razenshteyn & Waingarten — Optimal hashing-based time–space trade-offs for approximate near neighbors | For c-approximate near-neighbour search (find a point within cr when one lies within r) over n points in Euclidean space, the paper gives a data structure for every pair of exponents with c²√ρq + (c²−1)√ρu ≥ √(2c²−1), using space n^{1+ρu+o(1)} + O(dn) and query time n^{ρq+o(1)} + dn^{o(1)}, on worst-case data (for Hamming and ℓ_1, c√ρq + (c−1)√ρu ≥ √(2c−1)). It proves the curve cannot be beaten by list-of-points structures, the model of all known data-independent hashing schemes, on random instances, and unconditionally in the cell-probe model only at one end (query n^{o(1)}) for one or two probes. So the exact trade between space spent organizing and per-query time is known within the hashing model; outside that model, for more than two probes, it is not, and data-dependent schemes are covered only by conjecture. | Read |
| NOTE-919 | Weber, Schek & Blott — Similarity search in high-dimensional spaces: when partitioning loses to a scan | Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance, the paper estimates the average fraction of blocks that an optimal nearest-neighbour search must read in a partitioned or clustered index. That fraction reaches the 20% at which a sequential scan wins, given an assumed five-fold sequential advantage, at about 15–20 dimensions for rectangular regions, 26 for spherical ones, and below a crude 610 for any partitioning into convex clusters of two or more points. The “around 10” in the abstract is the measured crossover for an R*-tree and an X-tree on 50,000 uniform points and on 45-dimensional image features. As an alternative it proposes the VA-file, a scanned file of compact per-vector approximations that filters out all but a few vectors. The analysis says nothing about data with low intrinsic dimension; that the results carry over by fractal dimension is a conjecture. | Read |
| NOTE-920 | Buneman, Khanna & Tan — Why and where: a characterization of data provenance | The paper separates two meanings of the provenance of a piece of output data. Why-provenance is the witness basis: for each valuation of the query that produces the value, the part of the source the query’s patterns matched, one witness per derivation. Where-provenance is the location in the source a value was copied from. For a hierarchical data model and a query language that covers positive (SPJU) relational queries, the witness basis is preserved by the paper’s query rewriting, and the minimal witness basis is the same for equivalent queries with equality conditions, while where-provenance is not invariant over equivalent queries in general and is preserved by rewriting only for a restricted class it calls traceable. Proofs are omitted, and nothing covers negation, aggregation, updates or additions to the source. | Read |
| NOTE-921 | Halevy — Answering queries using views: a survey | A survey that separates two problems of answering queries from stored views: finding an equivalent rewriting, which query optimization needs, and finding a maximally-contained rewriting or all certain answers, which data integration needs when sources are incomplete. Its theoretical findings, mostly reported from other papers: an equivalent conjunctive rewriting exists only if one exists no longer than the query, so finding one is NP-complete in the size of the query and view definitions, and checking a candidate is itself NP-complete; the inverse-rules algorithm builds the maximally-contained rewriting, as a possibly recursive datalog program, in time polynomial in the query and views; and finding all certain answers is polynomial in the size of the stored data in many open-world cases, but co-NP-hard in that size under the closed-world assumption even for conjunctive views and queries, or open-world with union in the views or ≠ in the query. Choosing which views to store is left as the next problem; cost-based choice among rewritings is described for practical optimizers, without guarantees. | Read |
| NOTE-922 | Olston & Widom — Offering a precision-performance tradeoff for aggregation queries over replicated data | Olston and Widom propose TRAPP: caches hold, for each numeric value, an interval its source guarantees to contain the current value, the source pushing a refresh whenever the value leaves it. A query carries a precision constraint R, and the system chooses which values to fetch exactly so that the answer interval is at most R wide whatever the true values, at least total refresh cost. For SUM (and AVG without a predicate) that choice is a 0/1 knapsack problem, NP-complete in general and polynomial with equal costs; COUNT and MIN have simple rules. Staleness becomes bounded imprecision, never error, and the cost of the source-side upkeep that guarantees this, and of setting the bound widths, is outside the optimization. The one experiment is 90 stock prices with random costs. | Read |
| NOTE-924 | Fagin, Lotem & Naor — Optimal aggregation algorithms for middleware | Given m lists of the same N objects, each sorted by one attribute’s grade, and a monotone function combining the grades, the threshold algorithm (TA) reads the lists in parallel, random-accesses each newly seen object’s other grades, and stops once k seen objects score at least the combined score of the last grades read. It is correct for every monotone combining function, needs constant buffers, and is instance optimal among correct algorithms that make no “wild guesses”: on every database its cost is within a constant factor of any such algorithm’s, the factor being m + m(m−1)c_R/c_S, which is best possible when the combining function is strict (conjunction-like). Without the no-wild-guesses restriction no algorithm is instance optimal, and the counterexample is a two-list conjunction whose target sits in the middle of both lists, which any algorithm must search linearly. Fagin’s Algorithm’s sublinear cost O(N^((m−1)/m) k^(1/m)) is cited from Fagin, not proved here, and holds only when the lists’ orderings are probabilistically independent. The model prices queries over a given set of single-attribute sorted lists. It does not price building or keeping the lists, choosing an arrangement, or any computation beyond accesses. | Read |