pith. sign in

arxiv: 1907.10492 · v1 · pith:RNYUVCTKnew · submitted 2019-07-22 · 💻 cs.LO · cs.AI· cs.DB· cs.GT

Social Choice Methods for Database Aggregation

Francesco Belardinelli (Department of Computing , Imperial College London , UK , Laboratoire IBISC , University of Evry , France) , Umberto Grandi (IRIT , University of Toulouse This is my paper

Pith reviewed 2026-05-24 18:12 UTC · model grok-4.3

classification 💻 cs.LO cs.AIcs.DBcs.GT
keywords social choicedatabase aggregationintegrity constraintsfirst-order logicquery languagesknowledge representationrelational databases
0
0 comments X

The pith

Social choice aggregators can merge first-order databases while preserving integrity constraints and commuting with certain queries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper explores how to aggregate multiple databases, each represented as a first-order relational structure, using techniques from social choice theory. It finds classes of aggregators that keep integrity constraints intact in the result if they hold in every input database. It also identifies query languages where the result of a query on the merged database matches the merge of the individual query results. This matters for handling data from multiple sources without introducing violations. The contribution opens a path for systematic combination of knowledge in database settings.

Core claim

We identify classes of aggregators that respect integrity constraints in the aggregated database, provided these are satisfied in all individual databases. We also characterise languages for first-order queries on which the answer to a query on the aggregated database coincides with the aggregation of the answers to the query obtained on each individual database. This is a first step on the application of techniques from social choice theory to knowledge representation in databases.

What carries the argument

Aggregators from social choice theory applied directly to first-order relational database structures.

If this is right

  • If the aggregator respects constraints in inputs, the output database satisfies them too.
  • For characterized query languages, aggregation and querying commute.
  • Multiple sources can contribute data without violating shared rules.
  • This allows consistent integration of distributed or conflicting knowledge bases modeled as databases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Such methods might handle cases where not all sources satisfy constraints by using different aggregator properties.
  • Applications could include merging ontologies or RDF data from web sources.
  • Implementation in query engines could test the commutation property on real datasets.

Load-bearing premise

That databases are faithfully modeled as first-order relational structures and that the chosen aggregators interact with integrity constraints and queries through required closure properties.

What would settle it

Finding an integrity constraint and aggregator in the identified class where all input databases satisfy the constraint but the output does not, or a query in the characterized language where the two ways of computing the answer differ.

read the original abstract

Knowledge can be represented compactly in multiple ways, from a set of propositional formulas, to a Kripke model, to a database. In this paper we study the aggregation of information coming from multiple sources, each source submitting a database modelled as a first-order relational structure. In the presence of integrity constraints, we identify classes of aggregators that respect them in the aggregated database, provided these are satisfied in all individual databases. We also characterise languages for first-order queries on which the answer to a query on the aggregated database coincides with the aggregation of the answers to the query obtained on each individual database. This contribution is meant to be a first step on the application of techniques from social choice theory to knowledge representation in databases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper applies social choice theory to aggregate databases modeled as first-order relational structures. It identifies classes of aggregators that respect integrity constraints in the aggregated database whenever all input databases satisfy them, and characterizes first-order query languages such that the answer to a query on the aggregated database equals the aggregation of the answers to that query on each individual database.

Significance. If the characterizations hold, the work establishes a clean theoretical bridge between social choice and database theory for multi-source aggregation under constraints and for commuting aggregation with querying. It builds directly on standard relational-structure modeling and first-order logic without introducing free parameters, ad-hoc axioms, or domain-size restrictions, and the results are framed as a first step toward practical knowledge-representation applications.

minor comments (2)
  1. The abstract and introduction would benefit from a brief concrete example (e.g., a small relational schema with an integrity constraint and two source databases) to illustrate the aggregator classes and the query-commutation property before the general statements.
  2. Notation for the aggregator operations and the relational structures could be introduced with an explicit table or diagram in the preliminaries section to improve readability for readers coming from only one of the two fields.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of the paper, the assessment of its significance, and the recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; characterizations are self-contained

full rationale

The paper's central results are characterizations of aggregator classes preserving integrity constraints (when all inputs satisfy them) and FO query languages where query(aggregate(DBs)) equals aggregate(query(DBs)). These are proved from standard definitions of relational structures, social choice aggregators, and first-order logic closure properties. No equations reduce results to fitted inputs or self-definitions; no load-bearing self-citations or imported uniqueness theorems appear; the modeling choice is external to the field and the theorems are the target rather than premises. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard modeling assumptions from first-order logic and social choice theory rather than new free parameters or invented entities.

axioms (2)
  • domain assumption Databases are modeled as first-order relational structures
    Explicit in abstract opening sentence
  • domain assumption Integrity constraints hold in every individual database
    Condition stated for the aggregator result to hold

pith-pipeline@v0.9.0 · 5672 in / 1211 out tokens · 44553 ms · 2026-05-24T18:12:58.582245+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Abiteboul, R

    S. Abiteboul, R. Hull & V . Vianu (1995): Foundations of Databases. Addison-Wesley

    work page 1995

  2. [2]

    Arieli, M

    O. Arieli, M. Denecker & M. Bruynooghe (2007): Distance semantics for database repair. Annals of Math- ematics and Artificial Intelligence 50(3), pp. 389–415, doi:10.1007/s10472-007-9074-1

    work page doi:10.1007/s10472-007-9074-1 2007

  3. [3]

    K. J. Arrow (1963): Social Choice and Individual Values, 2nd edition. John Wiley and Sons

    work page 1963

  4. [4]

    Baral, S

    C. Baral, S. Kraus & J. Minker (1991): Combining Multiple Knowledge Bases. IEEE Transactions on Knowl- edge and Data Engineering 3(2), pp. 208–220, doi:10.1109/69.88001

    work page doi:10.1109/69.88001 1991

  5. [5]

    Baral, S

    C. Baral, S. Kraus, J. Minker & V . S. Subrahmanian (1992): Combining knowledge bases consisting of first-order theories. Computational Intelligence 8(1), doi:10.1016/0004-3702(80)90014-4. 66 Social Choice Methods for Database Aggregation

    work page doi:10.1016/0004-3702(80)90014-4 1992

  6. [6]

    Belardinelli & U

    F. Belardinelli & U. Grandi (2019): A Social Choice Theoretic Perspective on Database Aggregation (Ex- tended Abstract). In: Proceedings of the 18th International Conference on Autonomous Agents and Multia- gent Systems (AAMAS)

    work page 2019

  7. [7]

    H. A. Blair & V . S. Subrahmanian (1989): Paraconsistent Logic Programming. Theoretical Computer Sci- ence 68(2), pp. 135–154, doi:10.1016/0304-3975(89)90126-6

    work page doi:10.1016/0304-3975(89)90126-6 1989

  8. [8]

    Booth, E

    R. Booth, E. Awad & I. Rahwan (2014): Interval Methods for Judgment Aggregation in Argumentation. In: Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR)

    work page 2014

  9. [9]

    Caminada & G

    M. Caminada & G. Pigozzi (2011): On judgment aggregation in abstract argumentation . Autonomous Agents and Multiagent Systems 22(1), pp. 64–102, doi:10.1007/s10458-009-9116-7

    work page doi:10.1007/s10458-009-9116-7 2011

  10. [10]

    Chandra & Philip M

    Ashok K. Chandra & Philip M. Merlin (1977): Optimal Implementation of Conjunctive Queries in Relational Data Bases. In: Proceedings of the Ninth Annual ACM Symposium on Theory of Computing , STOC ’77, ACM, New York, NY , USA, pp. 77–90, doi:10.1145/800105.803397

    work page doi:10.1145/800105.803397 1977

  11. [11]

    Chen & U

    W. Chen & U. Endriss (2017): Preservation of Semantic Properties during the Aggregation of Abstract Argumentation Frameworks. In: Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), doi:10.1007/978-3-540-77684-0 4

    work page doi:10.1007/978-3-540-77684-0 2017

  12. [12]

    Dietrich & C

    F. Dietrich & C. List (2007): Arrow’s Theorem in Judgment Aggregation. Social Choice and Welfare 29(1), pp. 19–33, doi:10.1007/s00355-006-0196-x

    work page doi:10.1007/s00355-006-0196-x 2007

  13. [13]

    Dietrich & C

    F. Dietrich & C. List (2007): Judgment Aggregation by Quota Rules: Majority Voting Generalized. Journal of Theoretical Politics 19(4), pp. 391–424, doi:10.1016/0022-0531(75)90062-9

    work page doi:10.1016/0022-0531(75)90062-9 2007

  14. [14]

    Dokow & R

    E. Dokow & R. Holzman (2010): Aggregation of binary evaluations. Journal of Economic Theory 145(2), pp. 495–511, doi:10.1016/j.jet.2007.10.004

    work page doi:10.1016/j.jet.2007.10.004 2010

  15. [15]

    Doyle & M

    J. Doyle & M. P. Wellman (1991): Impediments to Universal Preference-based Default Theories. Artificial Intelligence 49(1), pp. 97–128, doi:10.1016/0004-3702(91)90007-7

    work page doi:10.1016/0004-3702(91)90007-7 1991

  16. [16]

    Endriss (2016): Judgment Aggregation

    U. Endriss (2016): Judgment Aggregation . In F. Brandt, V . Conitzer, U. Endriss, J. Lang & A. D. Procaccia, editors: Handbook of Computational Social Choice , Cambridge University Press, doi:10.1017/CBO9781107446984.018

    work page doi:10.1017/cbo9781107446984.018 2016

  17. [17]

    Endriss & U

    U. Endriss & U. Grandi (2014): Binary Aggregation by Selection of the Most Representative Voter . In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI-2014)

    work page 2014

  18. [18]

    Endriss & U

    U. Endriss & U. Grandi (2017): Graph Aggregation . Artificial Intelligence 245, pp. 86–114, doi:10.1016/j.artint.2017.01.001

    work page doi:10.1016/j.artint.2017.01.001 2017

  19. [19]

    Everaere, S

    P. Everaere, S. Konieczny & P. Marquis (2015): Belief Merging versus Judgment Aggregation. In: Proceed- ings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

    work page 2015

  20. [20]

    Gionis, H

    A. Gionis, H. Mannila & P. Tsaparas (2007): Clustering aggregation. ACM Transactions on Knowledge Discovery from Data 1(1), p. 4, doi:10.1145/1217299.1217303

    work page doi:10.1145/1217299.1217303 2007

  21. [21]

    Grandi & U

    U. Grandi & U. Endriss (2011): Binary Aggregation with Integrity Constraints. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI)

    work page 2011

  22. [22]

    Grandi & U

    U. Grandi & U. Endriss (2013): Lifting Integrity Constraints in Binary Aggregation. Artificial Intelligence 199–200, pp. 45–66, doi:10.1016/j.artint.2013.05.001

    work page doi:10.1016/j.artint.2013.05.001 2013

  23. [23]

    Gregoire & S

    E. Gregoire & S. Konieczny (2006): Logic-based approaches to information fusion. Information Fusion 7(1), pp. 4 – 18, doi:10.1016/j.inffus.2005.08.001. Logic-based Approaches to Information Fusion

    work page doi:10.1016/j.inffus.2005.08.001 2006

  24. [24]

    van Harmelen, V

    F. van Harmelen, V . Lifschitz & B. Porter (2007):Handbook of Knowledge Representation. Elsevier Science, San Diego, USA

    work page 2007

  25. [25]

    Hintikka (1962): Knowledge and Belief: An Introduction to the Logic of the Two Notions

    J. Hintikka (1962): Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell Univer- sity Press. F. Belardinelli & U. Grandi 67

    work page 1962

  26. [26]

    Kimelfeld, P

    B. Kimelfeld, P. Kolaitis & J. Stoyanovich (2018): Computational Social Choice Meets Databases . In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , doi:10.24963/ijcai.2018/44

    work page doi:10.24963/ijcai.2018/44 2018

  27. [27]

    Konieczny (2000): On the Difference between Merging Knowledge Bases and Combining them

    S. Konieczny (2000): On the Difference between Merging Knowledge Bases and Combining them . In: Pro- ceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR)

    work page 2000

  28. [28]

    Artificial Intelligence 157(1), pp

    S Konieczny, J Lang & P Marquis (2004): DA2 merging operators. Artificial Intelligence 157(1), pp. 49 – 79

    work page 2004

  29. [29]

    Konieczny & R

    S. Konieczny & R. Pino P ´erez (2002): Merging Information Under Constraints: A Logical Framework . Journal of Logic and Computation 12(5), pp. 773–808, doi:10.1093/logcom/12.5.773

    work page doi:10.1093/logcom/12.5.773 2002

  30. [30]

    In: Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR)

    S ´ebastien Konieczny, J´erˆome Lang & Pierre Marquis (2002): Distance Based Merging: A General Frame- work and some Complexity Results. In: Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR)

    work page 2002

  31. [31]

    Liberatore & M

    P. Liberatore & M. Schaerf (1998): Arbitration (or How to Merge Knowledge Bases). IEEE Transactions on Knowledge and Data Engineering 10(1), pp. 76–90, doi:10.1109/69.667090

    work page doi:10.1109/69.667090 1998

  32. [32]

    Libkin (2015): How to Define Certain Answers

    L. Libkin (2015): How to Define Certain Answers. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI)

    work page 2015

  33. [33]

    Mendelzon (1996): Merging Databases under Constraints

    Jinxin Lin & Alberto O. Mendelzon (1996): Merging Databases under Constraints. International Journal of Cooperative Information Systems 7, pp. 55–76, doi:10.1142/S021821579200009X

    work page doi:10.1142/s021821579200009x 1996

  34. [34]

    Maier, J

    D. Maier, J. Ullman & M. Vardi (1984): On the Foundations of the Universal Relation Model. ACM Trans- actions on Database Systems 9(2), pp. 283–308, doi:10.1145/329.318580

    work page doi:10.1145/329.318580 1984

  35. [35]

    Maynard-Zhang & D

    P. Maynard-Zhang & D. J. Lehmann (2003): Representing and Aggregating Conflicting Beliefs. Journal of Artificial Intelligence Research 19, pp. 155–203, doi:10.1613/jair.1206

    work page doi:10.1613/jair.1206 2003

  36. [36]

    Miller & D

    M. Miller & D. Osherson (2009): Methods for distance-based judgment aggregation . Social Choice and Welfare 32(4), pp. 575–601, doi:10.1007/s00355-008-0340-x

    work page doi:10.1007/s00355-008-0340-x 2009

  37. [37]

    Porello & U

    D. Porello & U. Endriss (2012): Ontology merging as social choice: Judgment aggregation under the open world assumption. Journal of Logic and Computation 24, pp. 1229–1249, doi:10.1093/logcom/exs056

    work page doi:10.1093/logcom/exs056 2012

  38. [38]

    V . S. Subrahmanian (1992):Paraconsistent Disjunctive Deductive Databases. Theoretical Computer Science 93(1), pp. 115–141, doi:10.1016/0304-3975(92)90214-Z

    work page doi:10.1016/0304-3975(92)90214-z 1992