AI Glossary / Data engineering and architecture / Advanced
Imieliński - Lipski algebra
Definition
Imieliński - Lipski algebra refers to a family of theoretical treatments that extend relational querying to databases containing incomplete information. The work of Tomasz Imieliński and Witold Lipski explains how representations of unknown values and supported query operations must fit together to produce justified answers. It is a foundation for reasoning about missing data, rather than a single command available in every SQL database.
What it means
A blank cell can conceal several different situations. A value may be unknown, or two cells may be known to contain the same unknown value. A database representation needs to preserve such distinctions if queries are to use them correctly. The central concern is not guessing a missing value. It is determining what follows from the information actually represented, and which conclusions remain valid across the possible complete databases compatible with that information.
How it works
The original research considers representations including ordinary nulls, marked nulls and conditional tables. A marked null can act like a shared variable, while a conditional table attaches conditions to represented rows. The supported query language matters: properties established for one set of operations do not automatically extend to arbitrary negation or difference. Safety concerns avoiding incorrect conclusions, and completeness concerns obtaining the valid conclusions expressible within the specified framework. These are semantic guarantees under assumptions, not promises to recover facts absent from the data.
Three practical examples
- A data-integration researcher represents a shared but unidentified supplier across several records without inventing a supplier name.
- A query designer distinguishes answers that hold under every allowed completion from answers that hold under only some completions.
- An AI-assisted data-cleaning team keeps unresolved values explicit rather than turning a model's proposed completion into an asserted fact.
Think of it this way
Think of a puzzle with two spaces labeled x. You do not know what belongs in them, but the shared label says they must agree. Two unrelated blank spaces do not carry that same information. This analogy captures marked unknowns. Database theory goes further by defining query operations and the meaning of possible completions; solving a familiar puzzle by intuition is not a substitute for those formal rules.
Worked example
Consider two shipment records: shipment A has carrier x and shipment B has the same carrier x. For this illustration, x is constrained to be either Carrier Red or Carrier Blue. In one allowed completion both shipments use Red; in the other both use Blue. The statement “A and B have the same carrier” holds in both completions. The statement “A uses Red” holds in only one. If the records instead used independent unknowns x and y, mixed assignments would also be allowed and the same-carrier conclusion would no longer be certain. The example illustrates dependency between unknowns; it is not executable SQL or a full specification of conditional-table syntax.
Illustrative case study
In a fictional integration project, Ash Logistics receives partial records from two systems. An initial prototype fills missing carrier names with the most frequent carrier. Reviewers reject this because frequency is not evidence about a particular shipment. The revised research prototype records shared unknowns when supported by source evidence and distinguishes guaranteed conclusions from possible ones. The team documents the supported queries before using results in reports. This case demonstrates a reasoning discipline, not a production implementation or a claim that all uncertainty becomes easy to compute.
Common misconceptions and mistakes
The algebra does not make an unknown value known. Marked nulls are not simply ordinary SQL NULLs with prettier names; their intended interpretation can preserve relationships between occurrences. Safety does not mean cybersecurity, and completeness does not mean every field is populated. A theorem about a restricted query language must not be generalized to all SQL features. Open-world and closed-world assumptions also affect reasoning about absence. Treating “not present in this input” as “false everywhere” can introduce an unjustified conclusion.
Business use
Most business teams will encounter these ideas through data quality, integration and query semantics rather than implementing the algebra directly. The practical question is whether a report silently converts missing information into a definite claim. Ask system designers how unknown values are represented, whether correlations between unknowns survive transformation and which answers are guaranteed. In AI workflows, store predicted completions separately from observed values. This preserves the ability to revise a prediction and prevents uncertain enrichment from being mistaken for source evidence.
People also ask
Is this a missing-value prediction method?
No. It is about representing incomplete information and reasoning correctly with it.
Does every SQL query return all logically certain answers?
No. SQL null behavior and the semantics of incomplete databases must be analyzed for the particular query and representation.
Can every possible completion be listed?
Sometimes in a small example, but practical or theoretical domains may be too large. Compact representations and query restrictions are therefore important.
Check your understanding
Two records contain the same marked unknown x. May a completion replace one occurrence with Red and the other with Blue?
Answer: Not under the shared-variable interpretation. Every occurrence of that variable receives a consistent value in the completion. Using different variables would express different information.
Related terms
- Possible world
- Certain answer
- Relational algebra
- marked null
- conditional table
- incomplete database
- open-world assumption
Learn next
Start with a tiny table and list its allowed completions. Compare a certain answer with a merely possible answer. Then read the original paper's representation-system definitions before studying operator-specific results, because the guarantees depend on both the representation and query language.
More in Data engineering and architecture
- Identifier Domain - An identifier domain is the defined set and representation of values used to identify entities or records in a particular context.
- Identity column - An identity column is a database column whose values can be generated automatically when new rows are inserted.
- Imageability - Imageability is the capacity of something to evoke a mental image. The meaning depends on context.
- Impedance Mismatch - Impedance mismatch in database work describes friction between different data models or programming environments.
- Implicit parallelism - Implicit parallelism is parallel execution that a compiler, runtime or execution system discovers or manages without the programmer spelling out every...
- Incomplete join - Incomplete join is an informal description of a join whose conditions do not fully specify the intended relationship between its inputs.
Sources
Sources: Imieliński and Lipski, “Incomplete Information in Relational Databases,” Journal of the ACM, 1984, https://www.inf.unibz.it/~nutt/Teaching/FDBs1718/FDBsPapers/imielinskiLipski-JACM-84.pdf, DOI https://doi.org/10.1145/1634.1886; Libkin, “Incomplete Information and Certain Answers in General Data Models,” https://homepages.inf.ed.ac.uk/libkin/papers/pods11a.pdf. The original paper's abstract and introductory representation descriptions were opened and read; Libkin source search excerpts were consulted. Full theorem-level and editorial review remain pending. The shipment example is original and deliberately informal.
Previous: Imageability Next: Imitation learning