Does the database schema usually stay fixed?

Often, yes, but the exact problem definition must state what is fixed.

Is data complexity the same as sample complexity?

No. Sample complexity concerns how much data a learning procedure needs for a statistical guarantee, rather than the computational cost of evaluating a fixed logical task.

Can two implementations have the same asymptotic bound but different runtimes?

Yes. Memory layout, indexes, constants and data distributions can produce substantial differences within the same broad bound.

AI Glossary / Graphs and symbolic AI / Advanced

Data complexity

Definition

Data complexity measures the computational difficulty of a task as the data grows while the query, rule set or other specified logical description is held fixed. It is a formal analysis viewpoint used in databases and knowledge representation.

What it means

A query system has more than one source of input size. The database may contain many facts, while the question may itself be a long expression involving numerous conditions. Data complexity separates these dimensions by fixing the question and varying the data.

For example, “Does a route connect warehouse A to warehouse B?” can remain the same logical question while the transport graph grows. A data-complexity analysis studies that growth under a stated representation and evaluation task.

This is different from calling a dataset complicated because it has missing values, many formats or unusual business meanings. Those issues affect implementation and analysis, but they are not the formal definition of data complexity used here.

How it works

Specify the evaluation problem first: perhaps deciding whether a Boolean query is true, whether a tuple is an answer, or producing all answers. Identify which parts of the query language, schema and rules are fixed, and measure the changing database size.

Then analyze the resources needed as that size increases. A polynomial bound means that, for the fixed logical description, the resource requirement can be bounded by a polynomial in data size under the stated computational model.

Combined complexity instead lets both the query and database vary. These perspectives can yield very different classifications. A query language may have manageable data complexity but much harder combined complexity because the logical question itself becomes increasingly elaborate.

The constants and exponents hidden by fixing the query still matter. If an evaluation approach has cost proportional to N^k, where k depends on the query, each fixed k gives a polynomial in N. That fact does not make a large k operationally inexpensive. Formal complexity also differs from a stopwatch measurement on one database instance.

Three practical examples

A knowledge-base team studies how one fixed set of inference rules behaves as more facts are imported.
A reporting team benchmarks the same query across increasing database sizes to investigate data-scaling behavior.
A query-tool designer distinguishes a larger customer dataset from a more complicated user-generated query when analyzing performance limits.

Think of it this way

Think of keeping the recipe fixed while increasing the amount of food to prepare. This isolates the effect of quantity. Allowing both the quantity and the recipe's number of stages to grow asks a different question.

The analogy is limited because database joins and logical dependencies can make work grow much faster than the amount of input. Doubling the records does not necessarily mean doubling the computation.

Worked example

Fixing the query changes the analysis

Suppose a deliberately simple evaluator answers a fixed three-variable query by trying every assignment of its variables over a domain with N objects. Assume each candidate assignment takes constant time to check under the chosen representation.

There are N³ assignments. At N=20, that is 8,000 checks. At N=40, it is 64,000 checks: doubling N multiplies this particular procedure's work by eight.

For the fixed three-variable query, the procedure has a cubic data-size dependence when size is represented by the domain count in this illustration. It is an upper-bound example for this evaluator, not a claim that every such query requires cubic work or that domain count always equals database encoding length.

If the number of variables k is also allowed to grow with the input, the same enumeration performs N^k checks. The exponent is no longer fixed. An analysis that hides k cannot describe that combined growth adequately. Better evaluation algorithms may exist, but they must be analyzed under the same clearly stated input conventions.

Illustrative case study

A fictional supplier-data service, Maple Relations, repeatedly evaluates a stable rule set over growing collections of product facts. Its team initially labels a slow run “high data complexity” without separating the causes.

A controlled comparison keeps the rules fixed and varies the data. A second comparison holds the data steady while adding rule conditions. The team discovers that its earlier benchmark changed both at once, making the result unsuitable for explaining either dimension separately.

It reports the exact rule version, data-size measure, output size and observed runtime alongside any formal analysis. The service uses the findings to choose representative performance tests rather than claiming that a complexity class predicts a specific response time on its hardware.

Common misconceptions and mistakes

Data complexity means the number of fields or data formats. In this context it is resource growth with data size under a fixed query or theory.
Polynomial data complexity means every practical instance is fast. Constants, polynomial degree, output size and implementation all matter.
A result for a fixed rule set automatically covers arbitrarily growing rule sets. That changes what counts as input.
A slow benchmark proves a formal lower bound. Measurements of one implementation do not establish what every possible algorithm must require.

Business use

The distinction helps scope performance claims for database-backed AI and symbolic reasoning systems. Ask whether a vendor's scalability statement assumes fixed rules, fixed queries or bounded query shapes.

Separate query compilation, index construction, evaluation and answer delivery where those costs matter. Producing millions of answers necessarily involves work beyond deciding that at least one answer exists. For operational planning, combine the formal perspective with workload measurements that preserve the assumptions of the claim being tested.

Check your understanding

A benchmark increases both database size and the number of query clauses. Does it isolate data complexity?

Answer: No. It varies the logical description as well as the data. A data-complexity study must state and preserve the fixed-query assumptions.

Related terms

Computational complexity
Datalog
Knowledge representation
Asymptotic analysis
Combined complexity
query evaluation
output-sensitive algorithm

Learn next

Choose one fixed query and define its input-size measure. Write down which rules and schema elements remain unchanged, then design a separate experiment for query growth. Distinguish a Boolean existence test from listing every matching record.

Sources

Inria VALDA, Scientific Foundations, explains the distinction between fixed-query data complexity and combined complexity in query evaluation: https://radar.inria.fr/report/2018/valda/uid13.html

The enumeration calculation, benchmarking exercise and Maple Relations case are original explanatory examples; they are not empirical performance claims.

Previous: Data colonialism Next: Data compression