Query Planning under Input Binding Constraints

16 concepts12 papers1 proposal

In a traditional relational database, a query planner enjoys total visibility and unconstrained access to data. If you want to find all books written by authors living in Paris, the database engine can freely choose to scan the Authors table, filter by city, and join the result with a Books table. It assumes that any table can be scanned in its entirety at any time.

However, the modern data landscape is highly fragmented. Valuable data is frequently locked behind Web APIs, cloud data markets, and deep web forms. In this environment, you cannot execute an unconstrained table scan like SELECT * FROM Google_Books. Instead, data providers enforce input binding constraints: you must provide a specific input parameter (such as an author's name or an ISBN) just to unlock a specific set of output attributes.

As highlighted by Benedikt, these access patterns prevent bulk data downloads and completely break traditional query optimization. Query planning over restricted interfaces shifts from a set-theoretic optimization problem to a sequential orchestration problem, where the engine must discover a valid sequence of dependent calls to answer a user's query.

Knowledge Preconditions and Chaining

To understand why binding constraints change the nature of query planning, consider how a system must navigate inter-service dependencies. If you want to find the reviews for books written by a specific author, but the review API requires a Book_ID (which you do not have) rather than an Author_Name (which you do have), the query is not immediately executable. You must first find an intermediate service that maps an Author_Name to a Book_ID.

This requirement turns query planning into an AI planning problem governed by knowledge preconditions. This perspective dates back to early information-gathering systems like Occam, developed by Kwok et al., which modeled data source access constraints as mandatory inputs that dictate the valid ordering of operations. You cannot query a source until you have satisfied its knowledge preconditions using data retrieved from prior steps.

[User Input: Author Name] 
          │
          ▼
┌────────────────────────────────────────┐
│ Service A (Requires: Author Name)      │
│ Outputs: Book ID                       │
└────────────────────────────────────────┘
          │
          ▼
[Satisfied Precondition: Book ID]
          │
          ▼
┌────────────────────────────────────────┐
│ Service B (Requires: Book ID)          │
│ Outputs: Book Reviews                  │
└────────────────────────────────────────┘

Integrating these patterns directly into the query planner is essential for real-world autonomous systems. For example, the CALO Query Manager, detailed by Ambite et al., treats binding patterns as first-class constraints within its planning architecture. By doing so, the planner ensures that subgoals are only routed to specialized data sources when their specific input requirements are met, preventing the system from attempting invalid operations or unconstrained lookups on restricted endpoints.

Formalizing Access Paths and Realizability

When a system integrates dozens of web services—such as biological databases containing PubMed identifiers and ChEMBL compounds as discussed by Benedikt et al.—manually mapping these connections becomes impossible. We need a formal framework to answer a fundamental question: Given a set of restricted interfaces, is a user's query even answerable? This is known as the problem of query realizability.

To reason about these sequential access paths mathematically, Benedikt et al. and Leys et al. extended classical logic to incorporate API access patterns, introducing a framework called Access Linear Temporal Logic (AccLTL). They demonstrated that while verifying arbitrary data access paths can be computationally undecidable, a restricted "binding-positive" fragment of the logic (AccLTL+) remains decidable, providing a theoretical foundation for verifying whether a sequence of interface interactions can successfully retrieve the desired information.

When a query is realizable, the engine must perform query rewriting, translating a declarative query into an executable plan composed entirely of valid API calls. However, as shown by Romero et al., if data providers do not expose the necessary relational linkages through their APIs, certain queries become inherently unanswerable. Formal rewriting algorithms can mathematically prove this impossibility, allowing the system to fail gracefully rather than wasting resources on futile API calls.

Efficient Rewriting and Real-World Quirks

Even when a query is theoretically answerable, synthesizing the execution plan introduces severe algorithmic and practical challenges. Naive rewriting approaches often suffer from infinite recursion or exponential timeouts when trying to chain paths.

To overcome this, Romero et al. developed a polynomial-time (PTIME) algorithm that utilizes context-free grammars and regular expressions to find equivalent rewritings on path views. This approach guarantees that the synthesized chain of service calls will return the exact same results as a direct database query, without falling into infinite loops. To handle situations where global schema knowledge is missing, the authors also introduced "Smart Plans" (Romero et al.), which leverage the structural properties of API call sequences to guarantee result validity even when the underlying data is incomplete.

Beyond the pure logic of chaining inputs and outputs, practical query planners must also adapt to the technical and economic "quirks" of web interfaces:

  • Top-N and Ranking Limits: Many public web APIs do not return all matching records; instead, they return a limited number of top-ranked results for specific range queries. As Bienvenu et al. point out, these ranking mismatches break traditional database assumptions. To circumvent this, Asudeh et al. designed third-party reranking services that use on-the-fly indexing and virtual tuple pruning to minimize the number of expensive API calls needed to extract custom top-ranked items through restricted search interfaces.
  • Monetary and Rate Costs: In modern cloud data markets, every API transaction carries a financial cost or counts against a strict rate limit. Lo et al. demonstrate that under binding constraints, the order and granularity of your requests directly dictate the number of paid transactions required. A poorly planned query might pay for the same data twice or perform thousands of redundant lookups, making cost-based optimization an essential layer of the binding-constrained planning process.

Key Foundational Work

Planning to Gather Information (1996) — contributed 3 concept elements to this direction.
Design and Implementation of the CALO Query Manager (2006) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_binding_pattern_constraints_9b7fa146,
  title = {binding pattern constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binding-pattern-constraints/rdr_9b7fa146d1d24c0ebde23f1207dead79},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_binding_pattern_constraints_9b7fa146_v1,
  title = {binding pattern constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binding-pattern-constraints/rdr_9b7fa146d1d24c0ebde23f1207dead79/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake