0000000000022270

AUTHOR

Martin Grohe

showing 2 related works from this author

Locality of order-invariant first-order formulas

1998

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.

Discrete mathematicsRelational databaseComputer Science::Information RetrievalInformationSystems_INFORMATIONSTORAGEANDRETRIEVALLocalityStructure (category theory)InformationSystems_DATABASEMANAGEMENTFirst orderComplexity classOrder (group theory)Invariant (mathematics)TupleAlgorithmComputer Science::DatabasesMathematics
researchProduct

Locality of order-invariant first-order formulas

2000

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.

Discrete mathematicsGeneral Computer ScienceLogicLocalityStructure (category theory)InformationSystems_DATABASEMANAGEMENTFirst orderTheoretical Computer ScienceFirst-order logicCombinatoricsComputational MathematicsOrder (group theory)TupleInvariant (mathematics)MathematicsACM Transactions on Computational Logic
researchProduct