6533b82bfe1ef96bd128d498
RESEARCH PRODUCT
Locality of order-invariant first-order formulas
Martin GroheThomas Schwenticksubject
Discrete mathematicsRelational databaseComputer Science::Information RetrievalInformationSystems_INFORMATIONSTORAGEANDRETRIEVALLocalityStructure (category theory)InformationSystems_DATABASEMANAGEMENTFirst orderComplexity classOrder (group theory)Invariant (mathematics)TupleAlgorithmComputer Science::DatabasesMathematicsdescription
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-01-01 |